Inferring the Underlying Structure of Information Cascades
作者： Bo Zong , Yinghui Wu , Ambuj K. Singh , Xifeng Yan
关键词:
摘要: In social networks, information and influence diffuse among users as cascades. While the importance of studying cascades has been recognized in various applications, it is difficult to observe complete structure practice. this paper we study cascade inference problem following independent model, provide a full treatment from complexity algorithms: (a) propose idea consistent trees inferred structures for cascades, these connect source nodes observed with paths satisfying constraints temporal information. (b) We introduce metrics measure likelihood well several optimization problems finding them. (c) show that decision are general NP-complete, hard approximate. (d) approximation algorithms performance guarantees on quality heuristics. experimentally verify efficiency effectiveness our algorithms, using real synthetic data.
arxiv.org
ucsb.edu
ieeecomputersociety.org
computer.org参考文章(35)
Mary McGlohon, Jure Leskovec, Christos Faloutsos, Natalie S. Glance, Matthew Hurst, Patterns of Cascading Behavior in Large Blog Graphs. siam international conference on data mining. pp. 551- 556 ,(2007)
Jacob Goldenberg, Barak Libai, Eitan Muller, Talk of the Network: A Complex Systems Look at the Underlying Process of Word-of-Mouth Marketing Letters. ,vol. 12, pp. 211- 223 ,(2001) , 10.1023/A:1011122126881
Gregory Z. Gutin, Jrgen Bang-Jensen, Digraphs: Theory, Algorithms and Applications ,(2002)
David Kempe, Jon Kleinberg, Éva Tardos, Influential Nodes in a Diffusion Model for Social Networks Automata, Languages and Programming. pp. 1127- 1138 ,(2005) , 10.1007/11523468_91
Jure Leskovec, Ajit Singh, Jon Kleinberg, None, Patterns of influence in a recommendation network knowledge discovery and data mining. pp. 380- 389 ,(2006) , 10.1007/11731139_44
Kazumi Saito, Ryohei Nakano, Masahiro Kimura, Prediction of Information Diffusion Probabilities for Independent Cascade Model international conference on knowledge based and intelligent information and engineering systems. pp. 67- 75 ,(2008) , 10.1007/978-3-540-85567-5_9
Masahiro Kimura, Kazumi Saito, Tractable Models for Information Diffusion in Social Networks Lecture Notes in Computer Science. pp. 259- 271 ,(2006) , 10.1007/11871637_27
Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, Antti Ukkonen, Sparsification of influence networks Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '11. pp. 529- 537 ,(2011) , 10.1145/2020408.2020492
Wei Chen, Chi Wang, Yajun Wang, Scalable influence maximization for prevalent viral marketing in large-scale social networks knowledge discovery and data mining. pp. 1029- 1038 ,(2010) , 10.1145/1835804.1835934
Gabriel Robins, Alexander Zelikovsky, Tighter Bounds for Graph Steiner Tree Approximation SIAM Journal on Discrete Mathematics. ,vol. 19, pp. 122- 134 ,(2005) , 10.1137/S0895480101393155