TY - GEN
T1 - On Approximation of Real-World Influence Spread
AU - Yang, Yu
AU - Chen, Enhong
AU - Liu, Qi
AU - Xiang, Biao
AU - Xu, Tong
AU - Shad, Shafqat Ali
PY - 2012/9
Y1 - 2012/9
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84866882322
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84866882322&origin=recordpage
U2 - 10.1007/978-3-642-33486-3_35
DO - 10.1007/978-3-642-33486-3_35
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9783642334856
VL - Part II
T3 - Lecture Notes in Computer Science
SP - 548
EP - 564
BT - Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2012, Proceedings
A2 - Flach, Peter A.
A2 - Bie, Tijl De
A2 - Cristianini, Nello
T2 - 2012 European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD 2012)
Y2 - 24 September 2012 through 28 September 2012
ER -