Detecting Influential Users in Social Networks Based on Bipartite Comments Graph
https://doi.org/10.15514/ISPRAS-2022-34(5)-8
Abstract
With the development of online social networks, the task of identifying users who have a great influence on other participants in social networks is becoming increasingly important. An important source of information is user comments on content created by other users. The paper proposes a method for determining influence based on a bipartite user-comment-content graph. It incorporates information about text messages and the reactions of other users to them. In addition, we propose a method for identifying user communities in such a graph based on common interests. Experiments on data collections from VKontakte and YouTube networks show the correlation between user activity and influence, however, the most active commenters are not necessarily the most influential. Community analysis shows a positive correlation between the size of a community, the number of most influential users in it, and the average influence of community users.
Supporting agencies: This work was done under a scientific program of National center of physics and mathematics (project no. 9 “Artificial intelligence and big data in technical, industrial, natural, and social systems”.
About the Authors
Roman Konstantinivich PASTUKHOV
Ivannikov Institute for System Programming of the RAS
Russian Federation
Russian Federation
Researcher
Mikhail Dmitrievich DROBYSHEVSKIY
Ivannikov Institute for System Programming of the RAS
Russian Federation
Russian Federation
Ph.D., Researcher
Denis Yurievich TURDAKOV
Ivannikov Institute for System Programming of the RAS,
Lomonosov Moscow State University
Russian Federation
Russian Federation
Ph.D., Head of the Information Systems Department at ISP RAS, Associated Professor at MSU
References
1. Conrad Lee, Fergal Reid et al. Detecting highly overlapping community structure by greedy clique expansion. arXiv preprint arXiv:1002.1827, 2010, 10 p.
2. Andrea Lancichinetti, Filippo Radicchi et al. Finding statistically significant communities in networks. PloS one, vol. 6, issue 4, 2011, e18961.
3. Aaron McDaid and Neil Hurley. Detecting highly overlapping communities with model-based overlapping seed expansion. In Proc. of the International Conference on Advances in Social Networks Analysis and Mining, 2010, pp. 1120-119.
4. Morten Mørup and Mikkel N Schmidt. Bayesian community detection. Neural computation, vol. 24, issue 9, 2012, pp. 2434-2456.
5. Jaewon Yang and Jure Leskovec. Overlapping community detection at scale: a nonnegative matrix factorization approach. In Proc. of the Sixth ACM International Conference on Web Search and Data Mining, 2013, pages 587–596.
6. Jaewon Yang, Julian McAuley, and Jure Leskovec. Community detection in networks with node attributes. In Proc. of the IEEE 13th international conference on data mining, 2013, pp. 1151-1156.
7. Mark E.J. Newman and Michelle Girvan. Finding and evaluating community structure in networks. Physical review E, vol. 69, issue 2, 2004, artricle id 026113.
8. Mingming Chen, Konstantin Kuzmin, and Boleslaw K Szymanski. Community detection via maximization of modularity and its variants. IEEE Transactions on Computational Social Systems, vol. 1, issue 1, 2014, pp. 46-65.
9. Nicolas Dugué and Anthony Perez. Directed Louvain: maximizing modularity in directed networks. Research Report hal-01231784, Université d’Orléans. 2015, 15 p.
10. Vincent D. Blondel, Jean-Loup Guillaume et al. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008, artricle id P10008, 15 p.
11. Jierui Xie, Boleslaw K. Szymanski, and Xiaoming Liu. SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In Proc. of the IEEE 11th International Conference on Data Mining Workshops, 2011, pp. 344-349.
12. Zhi-Hao Wu, You-Fang Lin et al. Balanced multi-label propagation for overlapping community detection in social networks. Journal of Computer Science and Technology, vol. 27, issue 3, 2012, pp. 468-479.
13. Steve Gregory. Finding overlapping communities in networks by label propagation. New journal of Physics, vol. 12, issue 10, 2019, artricle id 103018.
14. Sucheta Soundarajan and John E Hopcroft. Use of local group information to identify communities in networks. ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 9, issue 3, 2015, pp. 1-27.
15. Michele Coscia, Giulio Rossetti et al. Demon: a local-first discovery method for overlapping communities. In Proc. of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 615-623.
16. Bradley S. Rees and Keith B. Gallagher. Egoclustering: overlapping community detection via merged friendship-groups. Lecture Notes in Social Networks, vol. 6, 2013, pp. 1-20.
17. Nazar Buzun, Anton Korshunov et al. Egolp: Fast and distributed community detection in billion-node social networks. In Proc. of the IEEE International Conference on Data Mining Workshops, 2014, pp. 533-540.
18. Mohammed Ali Al-Garadi, Kasturi Dewi Varathan et al. Analysis of online social network connections for identification of influential users: Survey and open research issues. ACM Computing Surveys (CSUR), vol. 51, issue 1, 2018, pp. 1-37.
19. Colin Cooper, Tomasz Radzik, and Yiannis Siantos. A fast algorithm to find all high degree vertices in power law graphs. In Proc. of the 21st International Conference on World Wide Web, 2012, pp. 1007-1016.
20. Konstantin Avrachenkov, Prithwish Basu et al. Online myopic network covering. UMass Technical Report UM-CS-2012-034, arXiv preprint arXiv:1212.5035, 2012, 18 p.
21. Konstantin Avrachenkov, Prithwish Basu et al. Pay few, influence most: Online myopic network covering. In Proc. of the IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2014, pp. 813-818.
22. Katja Filippova. User Demographics and Language in an Implicit Social Network. In Proc. of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, 2012, pp. 1478–1488.
23. Konstantin Avrachenkov, Nelly Litvak et al. Quick detection of nodes with large degrees. Internet Mathematics, 10(1-2):1–19, 2014.
24. Danil Shaikhelislamov, Mikhail Drobyshevskiy et al. Three-step algorithms for detection of high degree nodes in online social networks. In Proc. of the Ivannikov Memorial Workshop (IVMEM), 2020, pp. 43-48.
25. Daniel M Romero, Wojciech Galuba et al. Influence and passivity in social media. Lecture Notes in Computer Science, vol. 6913, 2011, pp. 18-33.
26. Zhiguo Zhu, Jingqin Su, and Liping Kong. Measuring influence in online social network based on the user-content bipartite graph. Computers in Human Behavior, vol. 52, 2015, pp. 184-189.
27. Weishu Hu, Zhiguo Gong et al. Identifying influential user communities on the social network. Enterprise Information Systems, vol. 9, issue 7, 2015, pp. 709-724.
28. David Darmon, Elisa Omodei, and Joshua Garland. Followers are not enough: A multifaceted approach to community detection in online social networks. PloS one, vol. 10, issue 8, 2015, artricle id e0134860.
Review
For citations:
PASTUKHOV R.K., DROBYSHEVSKIY M.D., TURDAKOV D.Yu. Detecting Influential Users in Social Networks Based on Bipartite Comments Graph. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2022;34(5):127-142. (In Russ.) https://doi.org/10.15514/ISPRAS-2022-34(5)-8
Email this article 