Paper Info
Title
Time-Bounded Positive Influence in Social Networks.
Abstract
The appearance of social networks provides great opportunities for people to communicate, share and disseminate information. Meanwhile, it is quite challenge for utilizing a social networks efficiently in order to increase the commercial profit or alleviate social problems. One feasible solution is to select a subset of individuals that can positively influence the maximum other ones in the given social network, and some algorithms have been proposed to solve the optimal individual subset selection problem. However, most of the existing works ignored the constraint on time. They either assume that the time is infinite or only suitable to solve the snapshot selection problems. Obviously, both of them are impractical in the real system. Due to such reason, we study the problem of selecting the optimal individual subset to diffuse the positive influence when time is bounded. We proved that such a problem is NP-hard, and a heuristic algorithm based on greedy strategy is proposed. The experimental results on both simulation and real-world social networks based on the trace data in Shanghai show that our proposed algorithm outperforms the existing algorithms significantly, especially when the network structure is sparse.
Year
DOI
Venue
2015
10.1109/IIKI.2015.37
IIKI
Keywords
Field
DocType
social network,dominating set,influence
Approximation algorithm,Mathematical optimization,Dominating set,Social network,Heuristic (computer science),Computer science,Greedy algorithm,Dissemination,Snapshot (computer storage),Bounded function
Conference
Citations 
PageRank 
References 
1
0.35
15
Authors
6
Name
Order
Citations
PageRank
Tuo Shi1414.55
Jialin Wan210.69
Siyao Cheng343822.59
Zhipeng Cai41928132.81
Yingshu Li567153.71
Jianzhong Li63196304.46