Journal
INFORMATION SCIENCES
Volume 316, Issue -, Pages 107-122Publisher
ELSEVIER SCIENCE INC
DOI: 10.1016/j.ins.2015.04.024
Keywords
Top-k nodes selection; Social network; Greedy deprecation strategy; Influence maximization; Big data; Target set selection
Categories
Funding
- Department of Science and Technology, Govt. of India
- J.C. Bose National Fellowship
- INAE Chair Professorship
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available