Social influence analysis in large-scale networks

ABSTRACT

In large social networks, nodes (users, entities) are influenced by others for various reasons. For example, the colleagues have strong influence on one's work, while the friends have strong influence on one's daily life. How to differentiate the social influences from different angles(topics)? How to quantify the strength of those social influences? How to estimate the model on real large networks?

To address these fundamental questions, we propose Topical Affinity Propagation (TAP) to model the topic-level social influence on large networks. In particular, TAP can take results of any topic modeling and the existing network structure to perform topic-level influence propagation. With the help of the influence analysis, we present several important applications on real data sets such as 1) what are the representative nodes on a given topic? 2) how to identify the social influences of neighboring nodes on a particular node?

To scale to real large networks, TAP is designed with efficient distributed learning algorithms that is implemented and tested under the Map-Reduce framework. We further present the common characteristics of distributed learning algorithms for Map-Reduce. Finally, we demonstrate the effectiveness and efficiency of TAP on real large data sets.

REFERENCES

• 1: R. Albert and A. L. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1), 2002.
• 2: Aris Anagnostopoulos , Ravi Kumar , Mohammad Mahdian, Influence and correlation in social networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401897]
• 3: David M. Blei , Andrew Y. Ng , Michael I. Jordan, Latent dirichlet allocation, The Journal of Machine Learning Research, 3, p.993-1022, 3/1/2003 [doi>10.1162/jmlr.2003.3.4-5.993]
• 4: Chris Buckley , Ellen M. Voorhees, Retrieval evaluation with incomplete information, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009000]
• 5: C.-T. Chu, S. K. Kim, Y.-A. Lin, Y. Yu, G. R. Bradski, A. Y. Ng, and K. Olukotun. Map-Reduce for machine learning on multicore. In Proceedings of the 18th Neural Information Processing Systems (NIPS'06), 2006.
• 6: David Crandall , Dan Cosley , Daniel Huttenlocher , Jon Kleinberg , Siddharth Suri, Feedback effects between similarity and social influence in online communities, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401914]
• 7: N. Craswell, A. P. de Vries, and I. Soboroff. Overview of the trec-2005 enterprise track. In TREC 2005 Conference Notebook, pages 199--205, 2005.
• 8: Abhinandan S. Das , Mayur Datar , Ashutosh Garg , Shyam Rajaram, Google news personalization: scalable online collaborative filtering, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242610]
• 9: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 10: Yon Dourisboure , Filippo Geraci , Marco Pellegrini, Extraction and classification of dense communities in the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242635]
• 11: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 12: Gary William Flake , Steve Lawrence , C. Lee Giles, Efficient identification of Web communities, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.150-160, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347121]
• 13: B. J. Frey and D. Dueck. Mixture modeling by affinity propagation. In Proceedings of the 18th Neural Information Processing Systems (NIPS'06), pages 379--386, 2006.
• 14: M. Granovetter. The strength of weak ties. American Journal of Sociology, 78(6):1360--1380, 1973.
• 15: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 16: D. Krackhardt. The Strength of Strong ties: the importance of philos in networks and organization in Book of Nitin Nohria and Robert G. Eccles (Ed.), Networks and Organizations. Harvard Business School Press, Boston, MA, 1992.
• 17: F. R. Kschischang, S. Member, B. J. Frey, and H. andrea Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47:498--519, 2001.
• 18: Qiaozhu Mei , Deng Cai , Duo Zhang , ChengXiang Zhai, Topic modeling with network regularization, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367512]
• 19: M. E. J. Newman. The structure and function of complex networks. SIAM Reviews, 45, 2003.
• 20: Spiros Papadimitriou , Jimeng Sun, DisCo: Distributed Co-clustering with Map-Reduce: A Case Study towards Petabyte-Scale End-to-End Mining, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.512-521, December 15-19, 2008 [doi>10.1109/ICDM.2008.142]
• 21: Parag Singla , Matthew Richardson, Yes, there is a correlation: - from social networks to personal behavior on the web, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367586]
• 22: P. Smolensky, Information processing in dynamical systems: foundations of harmony theory, Parallel distributed processing: explorations in the microstructure of cognition, vol. 1: foundations, MIT Press, Cambridge, MA, 1986
• 23: S. H. Strogatz. Exploring complex networks. Nature, 410:268--276, 2003.
• 24: Jie Tang , Ruoming Jin , Jing Zhang, A Topic Modeling Approach and Its Integration into the Random Walk Framework for Academic Search, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.1055-1060, December 15-19, 2008 [doi>10.1109/ICDM.2008.71]
• 25: Jie Tang , Jing Zhang , Limin Yao , Juanzi Li , Li Zhang , Zhong Su, ArnetMiner: extraction and mining of academic social networks, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1402008]
• 26: S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.
• 27: Max Welling , Geoffrey E. Hinton, A New Learning Algorithm for Mean Field Boltzmann Machines, Proceedings of the International Conference on Artificial Neural Networks, p.351-357, August 28-30, 2002

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Experimentation

Keywords:
large-scale network, social influence analysis, social networks, topical analysis propagation