research-article

Social influence analysis in large-scale networks

Authors:

Zi YangAuthors Info & Claims

KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 807 - 816

https://doi.org/10.1145/1557019.1557108

Published: 28 June 2009 Publication History

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.

Supplementary Material

JPG File (p807-tang.jpg)

Download
10.22 KB

MP4 File (p807-tang.mp4)

Download
84.28 MB

References

[1]

R. Albert and A. L. Barabasi. Statistical mechanics of complex networks. Reviews of Modern Physics, 74(1), 2002.

[2]

A. Anagnostopoulos, R. Kumar, and M. Mahdian. Influence and correlation in social networks. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD'08), pages 7--15, 2008.

Digital Library

[3]

D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent dirichlet allocation. Journal of Machine Learning Research, 3:993--1022, 2003.

Digital Library

[4]

C. Buckley and E. M. Voorhees. Retrieval evaluation with incomplete information. In SIGIR'04, pages 25--32, 2004.

Digital Library

[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]

D. Crandall, D. Cosley, D. Huttenlocher, J. Kleinberg, and S. Suri. Feedback effects between similarity and social influence in online communities. In Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD'08), pages 160--168, 2008.

Digital Library

[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]

A. Das, M. Datar, A. Garg, and S. Rajaram. Google news personalization: Scalable online collaborative filtering. In Proceeding of the 16th international conference on World Wide Web (WWW'07), 2007.

Digital Library

[9]

J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters. In Proceedings of the 6th conference on Symposium on Opearting Systems Design&Implementation (OSDI'04), pages 10--10, 2004.

Digital Library

[10]

Y. Dourisboure, F. Geraci, and M. Pellegrini. Extraction and classification of dense communities in the web. In WWW'07, pages 461--470, 2007.

Digital Library

[11]

M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the internet topology. In SIGCOMM, pages 251--262, New York, NY, USA, 1999. ACM.

Digital Library

[12]

G. W. Flake, S. Lawrence, and C. L. Giles. Efficient identification of web communities. In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining (KDD'00), pages 150--160, 2000.

Digital Library

[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]

T. Hofmann. Probabilistic latent semantic indexing. In Proceedings of the 22nd International Conference on Research and Development in Information Retrieval (SIGIR'99), pages 50--57, 1999.

Digital Library

[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.

Digital Library

[18]

Q. Mei, D. Cai, D. Zhang, and C. Zhai. Topic modeling with network regularization. In Proceedings of the 17th International World Wide Web Conference (WWW'08), pages 101--110, 2008.

Digital Library

[19]

M. E. J. Newman. The structure and function of complex networks. SIAM Reviews, 45, 2003.

[20]

S. Papadimitriou and J. Sun. Disco: Distributed co-clustering with map-reduce. In Proceedings of IEEE International Conference on Data Mining (ICDM'08), 2008.

Digital Library

[21]

P. Singla and M. Richardson. Yes, there is a correlation: - from social networks to personal behavior on the web. In Proceeding of the 17th international conference on World Wide Web (WWW'08), pages 655--664, 2008.

Digital Library

[22]

P. Smolensky. Information processing in dynamical systems: foundations of harmony theory. pages 194--281, 1986.

Digital Library

[23]

S. H. Strogatz. Exploring complex networks. Nature, 410:268--276, 2003.

[24]

J. Tang, R. Jin, and J. Zhang. A topic modeling approach and its integration into the random walk framework for academic search. In Proceedings of IEEE International Conference on Data Mining (ICDM'08), pages 1055--1060, 2008.

Digital Library

[25]

J. Tang, J. Zhang, L. Yao, J. Li, L. Zhang, and Z. Su. Arnetminer: Extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD'08), pages 990--998, 2008.

Digital Library

[26]

S. Wasserman and K. Faust. Social Network Analysis: Methods and Applications. Cambridge: Cambridge University Press, 1994.

[27]

M. Welling and G. E. Hinton. A new learning algorithm for mean field boltzmann machines. In Proceedings of International Conference on Artificial Neural Network (ICANN'01), pages 351--357, 2001.

Digital Library

Cited By

Quan PZheng LZhang WXiao YNiu LShi Y(2025)ExGAT: Context extended graph attention neural networkNeural Networks10.1016/j.neunet.2024.106784181(106784)Online publication date: Jan-2025
https://doi.org/10.1016/j.neunet.2024.106784
Liu SHe DYu ZJin DFeng Z(2025)Beyond Homophily: Neighborhood Distribution-guided Graph Convolutional NetworksExpert Systems with Applications10.1016/j.eswa.2024.125274259(125274)Online publication date: Jan-2025
https://doi.org/10.1016/j.eswa.2024.125274
Wu XWu HWang RZhou XLu K(2024)Towards adaptive graph neural networks via solving prior-data conflicts通过解决先验数据冲突实现自适应图神经网络Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.230019425:3(369-383)Online publication date: 23-Mar-2024
https://doi.org/10.1631/FITEE.2300194
Show More Cited By

Index Terms

Social influence analysis in large-scale networks
1. Information systems
  1. Information retrieval
  2. Information systems applications

Recommendations

A Topic Aware-based Approach to Maximize Social Influence
WebMedia '14: Proceedings of the 20th Brazilian Symposium on Multimedia and the Web

The use of social networks has shown great potential for information diffusion and formation of public opinion. One key problem that has attracted researchers interest is Topic-based Influence Maximization, that refers to finding a small set of users on ...
Estimating influence of social media users from sampled social networks
ASONAM '16: Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Several indices for estimating the influence of social media users have been proposed. Most such indices are obtained from the topological structure of a social network that represents relations among social media users. However, several errors are ...
An approximate framework for scaling social influence computation in large networks
SAC '14: Proceedings of the 29th Annual ACM Symposium on Applied Computing

Social networking service platforms have gained a great success in recent years. Analyzing the social network data from the platforms presents new opportunities for various applications. Among the applications, the social influence analysis has gained ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '09: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining

June 2009

1426 pages

ISBN:9781605584959

DOI:10.1145/1557019

General Chairs:
John Elder
Elder Research, Inc., USA
,
Françoise Soulié Fogelman
KXEN, France
,
Program Chairs:
Peter Flach
University of Bristol, UK
,
Mohammed Zaki
RPI, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

KDD09

Sponsor:

KDD09: The 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

June 28 - July 1, 2009

Paris, France

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

649
Total Citations
View Citations
7,584
Total Downloads

Downloads (Last 12 months)342
Downloads (Last 6 weeks)47

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Quan PZheng LZhang WXiao YNiu LShi Y(2025)ExGAT: Context extended graph attention neural networkNeural Networks10.1016/j.neunet.2024.106784181(106784)Online publication date: Jan-2025
https://doi.org/10.1016/j.neunet.2024.106784
Liu SHe DYu ZJin DFeng Z(2025)Beyond Homophily: Neighborhood Distribution-guided Graph Convolutional NetworksExpert Systems with Applications10.1016/j.eswa.2024.125274259(125274)Online publication date: Jan-2025
https://doi.org/10.1016/j.eswa.2024.125274
Wu XWu HWang RZhou XLu K(2024)Towards adaptive graph neural networks via solving prior-data conflicts通过解决先验数据冲突实现自适应图神经网络Frontiers of Information Technology & Electronic Engineering10.1631/FITEE.230019425:3(369-383)Online publication date: 23-Mar-2024
https://doi.org/10.1631/FITEE.2300194
Wang XWang YLin XYu JGao HCheng XYu D(2024)Efficient Betweenness Centrality Computation over Large Heterogeneous Information NetworksProceedings of the VLDB Endowment10.14778/3681954.368200617:11(3360-3372)Online publication date: 30-Aug-2024
https://doi.org/10.14778/3681954.3682006
Li YMao YYang YZou DBaeza-Yates RBonchi F(2024)Improving Robustness of Hyperbolic Neural Networks by Lipschitz AnalysisProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671875(1713-1724)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671875
Wo ZShao MWang WGuo XLin LChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Graph Contrastive Learning via Interventional View GenerationProceedings of the ACM Web Conference 202410.1145/3589334.3645687(1024-1034)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645687
Huang CLi HZhang YLei WLv JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Cross-Space Adaptive Filter: Integrating Graph Topology and Node Attributes for Alleviating the Over-smoothing ProblemProceedings of the ACM Web Conference 202410.1145/3589334.3645583(803-814)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645583
Dong ZChen YTricco TLi CHu T(2024)Ego-Aware Graph Neural NetworkIEEE Transactions on Network Science and Engineering10.1109/TNSE.2023.333045011:2(1756-1770)Online publication date: Mar-2024
https://doi.org/10.1109/TNSE.2023.3330450
Chen JChen SGao JHuang ZZhang JPu J(2024)Exploiting Neighbor Effect: Conv-Agnostic GNN Framework for Graphs With HeterophilyIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.326790235:10(13383-13396)Online publication date: Oct-2024
https://doi.org/10.1109/TNNLS.2023.3267902
Wu LLin HLiu ZLiu ZHuang YLi S(2024)Homophily-Enhanced Self-Supervision for Graph Structure Learning: Insights and DirectionsIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.325732535:9(12358-12372)Online publication date: Sep-2024
https://doi.org/10.1109/TNNLS.2023.3257325
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents