Utility-Aware Social Event-Participant Planning
Utility-Aware Social Event-Participant Planning
复制标题
DOI：
10.1145/2723372.2749446
复制
发表时间：
2015-05
期刊：
影响因子：
--
通讯作者：
Jieying She;Yongxin Tong;Lei Chen
中科院分区：
文献类型：
--
作者：
Jieying She;Yongxin Tong;Lei Chen
基于事件的在线社交网络（EBSN）平台如今越来越受欢迎。管理EBSN的一个重要任务是为感兴趣的用户安排适当的社交活动。现有的方法通常假设每个用户只参加一个事件或忽略位置信息。这种策略的整体效用在真实的世界中是有限的：1）每个用户可以参加多个事件; 2）参加多个事件将招致时空冲突和旅行费用。因此，需要为每个参与者提供个性化事件规划的更智能的EBSN平台。在本文中，我们首先正式定义了实用感知的社会事件参与者规划（USEP），这是被证明是NP-难的问题。为了解决USEP问题，我们首先设计了一种基于贪婪的启发式算法，该算法在某些情况下执行速度快，但没有近似保证。然后，我们提出了一个两步近似框架，它不仅保证了1/2的近似比，但也包括一系列的优化技术，以提高其空间/时间效率。最后，通过在真实的数据集和人工数据集上的实验，验证了所提方法的有效性。
Online event-based social network (EBSN) platforms are becoming popular these days. An important task of managing EBSNs is to arrange proper social events to interested users. Existing approaches usually assume that each user only attends one event or ignore location information. The overall utility of such strategy is limited in real world: 1) each user may attend multiple events; 2) attending multiple events will incur spatio-temporal conflicts and travel expenses. Thus, a more intelligent EBSN platform that provides personalized event planning for each participant is desired. In this paper, we first formally define the problem of Utility-aware Social Event-participant Planning (USEP), which is proven to be NP-hard. To solve the USEP problem, we first devise a greedy-based heuristic algorithm, which performs fast under certain circumstances but has no approximation guarantee. We then present a two-step approximation framework, which not only guarantees a 1/2-approximation ratio but also includes a series of optimization techniques to improve its space/time efficiency. Finally, we verify the efficiency and effectiveness of the proposed methods through extensive experiments on real and synthetic datasets.