期刊
INFORMATION SCIENCES
卷 316, 期 -, 页码 107-122出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2015.04.024
关键词
Top-k nodes selection; Social network; Greedy deprecation strategy; Influence maximization; Big data; Target set selection
资金
- Department of Science and Technology, Govt. of India
- J.C. Bose National Fellowship
- INAE Chair Professorship
The problem of target set selection for large scale social networks is addressed in the paper. We describe a novel deprecation based greedy strategy to be applied over a pre-ordered (as obtained with any heuristic influence function) set of nodes. The proposed algorithm runs in iteration and has two stages, (i) Estimation: where the performance of each node is evaluated and (ii) Marking: where the nodes to be deprecated in later iterations are marked. We have theoretically proved that for any monotonic and sub-modular influence function, the algorithm correctly identifies the nodes to be deprecated. For any finite set of input nodes it is shown that the algorithm can meet the ending criteria. The worst case performance of the algorithm, both in terms of time and performance, is also analyzed. Experimental results on seven un-weighted as well as weighted social networks show that the proposed strategy improves the ranking of the input seeds in terms of the total number of nodes influenced. (C) 2015 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据