Определение влиятельных пользователей социальной сети по двудольному графу комментариев

С развитием онлайновых социальных сетей все большую актуальность приобретают задачи выявления пользователей, которые оказывает большое влияние на других участников социальных сетей. Важным источником информации служат данные о комментировании пользователями контента, создаваемого другими пользователями. В работе предлагается метод определения влиятельности, основанный на двудольном графе пользователь-комментарий-контент, а также использующий информацию о текстовых сообщениях и реакции на них других пользователей. Кроме того, предложен метод выявления сообществ пользователей в таком графе на основе общих интересов. Результаты тестирования на коллекциях данных сетей ВКонтакте и YouTube показывают корреляцию активности и влиятельности пользователя, однако самые активные комментаторы не обязательно являются самыми влиятельными. Анализ сообществ показывает положительную корреляцию между размером сообщества, числом наиболее влиятельных пользователей в нем и средней влиятельностью пользователей сообщества.

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.