计算机科学
搜索引擎索引
最大化
估计员
集合(抽象数据类型)
启发式
修剪
社交网络(社会语言学)
数据挖掘
整数(计算机科学)
数学优化
社会化媒体
人工智能
统计
数学
万维网
生物
程序设计语言
农学
作者
Xiaoyang Wang,Ying Zhang,Wenjie Zhang,Xuemin Lin
出处
期刊:IEEE Transactions on Knowledge and Data Engineering
[Institute of Electrical and Electronics Engineers]
日期:2017-03-01
卷期号:29 (3): 599-612
被引量:77
标识
DOI:10.1109/tkde.2016.2633472
摘要
Given a social network and a positive integer k, the influence maximization problem aims to identify a set of k nodes in that can maximize the influence spread under a certain propagation model. As the proliferation of geo-social networks, location-aware promotion is becoming more necessary in real applications. In this paper, we study the distance-aware influence maximization (DAIM) problem, which advocates the importance of the distance between users and the promoted location. Unlike the traditional influence maximization problem, DAIM treats users differently based on their distances from the promoted location. In this situation, the k nodes selected are different when the promoted location varies. In order to handle the large number of queries and meet the online requirement, we develop two novel index-based approaches, MIA-DA and RIS-DA, by utilizing the information over some pre-sampled query locations. MIA-DA is a heuristic method which adopts the maximum influence arborescence (MIA) model to approximate the influence calculation. In addition, different pruning strategies as well as a priority-based algorithm are proposed to significantly reduce the searching space. To improve the effectiveness, in RIS-DA, we extend the reverse influence sampling (RIS) model and come up with an unbiased estimator for the DAIM problem. Through carefully analyzing the sample size needed for indexing, RIS-DA is able to return a 1 - 1=e - ε approximate solution with at least 1 - δ probability for any given query. Finally, we demonstrate the efficiency and effectiveness of proposed methods over real geo-social networks.
科研通智能强力驱动
Strongly Powered by AbleSci AI