Paper Info
Title
On approximation of real-world influence spread
Abstract
To find the most influential nodes for viral marketing, several models have been proposed to describe the influence propagation process. Among them, the Independent Cascade (IC) Model is most widely-studied. However, under IC model, computing influence spread (i.e., the expected number of nodes that will be influenced) for each given seed set has been proved to be #P-hard. To that end, in this paper, we propose GS algorithm for quick approximation of influence spread by solving a linear system, based on the fact that propagation probabilities in real-world social networks are usually quite small. Furthermore, for better approximation, we study the structural defect problem existing in networks, and correspondingly, propose enhanced algorithms, GSbyStep and SSSbyStep, by incorporating the Maximum Influence Path heuristic. Our algorithms are evaluated by extensive experiments on four social networks. Experimental results show that our algorithms can get better approximations to the IC model than the state-of-the-arts.
Year
DOI
Venue
2012
10.1007/978-3-642-33486-3_35
ECML/PKDD
Keywords
Field
DocType
social network,real-world influence spread,real-world social network,influence propagation process,computing influence spread,quick approximation,propagation probability,better approximation,influence spread,ic model,gs algorithm
Heuristic,Viral marketing,Mathematical optimization,Influence propagation,Social network,Linear system,Computer science,Expected value,Cascade
Conference
Citations 
PageRank 
References 
18
0.71
8
Authors
6
Name
Order
Citations
PageRank
Yu Yang111914.30
Enhong Chen22106165.57
Liu Qi31027106.48
Biao Xiang420610.95
Tong Xu521836.15
Shafqat Ali Shad6385.27