Keywords
graph for interacting objects
implicit community detection
social networks analysis
How to Cite
Abstract
the paper considers the problems of analyzing graphs that represent complex networks of interacting objects. The relevant domains are described, social network graph analysis and implicit community detection are considered. The key graph-based community detection algorithms and the quality assessment of their results are discussed. The author proposed promising development trends using the graphs representing actual social networks. The relevance of the approaches proposed in the author’s previous works is also highlighted.
References
Евин И. А. Введение в теорию сложных сетей. Компьютерные исследования и моделирование. 2010;2(2):121–141. DOI: 10.20537/2076-7633-2010-2-2-121-141.
Newman M. E. J. Networks: An Introduction. Oxford University Press; 2010. 784 p.
Fortunato S. Community Detection in Graphs. Physics Reports. 2010;486(3):75–174.
Aggarwal C. Social Network Data Analytics. NY:Springer New York; 2011. 502 p. DOI: 10.1007/978-14419-8462-3.
Рабинович Б. И. Кластерный анализ детализаций телефонных переговоров. Системы и средства информатики. 2007;17:52–78.
Себякин А. Г. Анализ информации о соединениях между абонентами, использование его результатов в раскрытии и расследовании преступлений. Полицейская и следственная деятельность. 2018;4:29-38. DOI: 10.25136/2409-7810.2018.4.27992.
Семенищев И. А., Синадский А. Н., Синадский Н. И., Сушков П. В. Синтез массивов биллинговой информации на основе статистико-событийной модели взаимодействия абонентов сетей сотовой связи. Вестник УРФО. Безопасность в информационной сфере. 2018;1(27):47–56.
Еремеев И. Ю., Татарка М. В., Шуваев Ф. Л., Цыганов А. С. Анализ мер центральности вершин сетей на основе метода главных компонент. Труды СПИИРАН. 2020;19(6):1307-1331. DOI: 10.15622/ia.2020.19.6.7.
Кириченко Л., Радивилова Т., Барановский А. Обнаружение киберугроз с помощью анализа социальных сетей. International Journal “Information Technologies & Knowledge”. 2017;11(1):23–48.
Rahiminejad S., Maurya M. R., Subramaniam S. Topological and Functional Comparison of Community Detection Algorithms in Biological Networks. BMC Bioinformatics. 2019;20:212.
Wu F., Chen L., Wang J., Li M., Wang H. Biomolecular Networks for Complex Diseases. Complexity. 2018:4210160.
Subelj L., Bajec M. Ubiquitousness of Link-Density and Link-Pattern Communities in Real-World Networks. The European Physical Journal B. 2012;85(1):32.
Subelj L., Bajec M. Group Detection in Complex Networks: an Algorithm and Comparison of the State of the Art. Physica A: Statistical Mechanics and Its Applications. 2014;397:144–156.
Landsman D., Kats P., Nenko A. Sobolevsky S. Zoning of St. Petersburg Through the Prism of Social Activity Networks. Procedia Computer Science. 2020;178:125–133.
Ser-Giacomi E., Legrand T., Hernandez-Carrasco I., Rossi V. Explicit and Implicit Network Connectivity:´ Analytical Formulation and Application to Transport Processes. Physical Review E. 2021;103(4).
Banerjee S. Designing and Connectivity Checking of Implicit Social Networks from the User-Item Rating Data. Multimedia Tools and Applications. 2021;80(17):26615–26635.
Castillo-de Mesa J., Gomez-Jacinto L. Connectedness, Engagement, and Learning through Social Work´ Communities on LinkedIn. Psychosocial Intervention. 2020;29(2):103–112.
Skobtsov Y. A., Obolensky D. M., Shevchenko V. I., Chengar O. V. Building And Analysing A
Skills Graph Using Data From Job Portals. Economic and Social Trends for Sustainability of Modern Society (ICEST-III 2022). European Proceedings of Social and Behavioural Sciences. European Publisher. 2022;127:147-162. DOI: 10.15405/epsbs.2022.08.17.
Райгородский А. М. Модели Интернета: Учебное пособие. Долгопрудный: Интеллект; 2019. 64 с.
Ермолин Н. А., Мазалов В. В., Печников А. А. Теоретико-игровые методы нахождения сообществ в академическом Вебе. Труды СПИИРАН. 2017;6(55):237–254. DOI 10.15622/sp.55.10.
Мазалов В. В., Никитина Н. Н., Печников А. А. О сообществах в коммуникационных графах. Вероятностные методы в дискретной математике: расширенные тезисы докладов X Международной Петрозаводской конференции. 2019. Петрозаводск: Федеральное государственное бюджетное учреждение науки Федеральный исследовательский центр «Карельский научный центр Российской академии наук»; 2019:99–100.
Черемисинов Д. И., Черемисинова Л. Д. Поиск часто встречающихся подграфов. BIG DATA Advanced Analytics: Collection of Materials of the Fourth International Scientific and Practical Conference, Minsk, Belarus, May 3–4, 2018. Minsk: BSUIR. 2018:171–176.
Rehman S. U., Kexing Liu K., Tariq Ali T., Nawaz A., Fong S. J. A Graph Mining Approach for Ranking and Discovering the Interesting Frequent Subgraph Patterns. International Journal of Computational Intelligence Systems. 2021;14(152). DOI: 10.1007/s44196-021-00001-4.
Базенков Н. И., Губанов Д. А. Обзор информационных систем анализа социальных сетей. Управление большими системами: сб. трудов. 2013:357–394.
Батура Т. В. Методы анализа компьютерных социальных сетей. Вестник НГУ. Серия: Информационные технологии. 2012;10(4):13–28.
Батура Т. В., Копылова Н. С., Мурзин Ф. А., Проскуряков А. В. Методы анализа данных из социальных сетей. Вестник НГУ. Серия: Информационные технологии. 2013;11(3):5–21.
Губанов Д. А., Новиков Д. А., Чхартишвили А. Г. Социальные сети: модели информационного влияния, управления и противоборства. М.: Физматлит; 2010. 228 с.
Borgatti S. P., Everett M. G., Johnson J. C. Analyzing Social Networks. SAGE Publications Limited; 2013. 304 p.
Coscia M., Rossetti G., Giannotti F., Pedreschi D. Demon: a Local-First Discovery Method for Overlapping Communities. Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2012:615–623.
Gaisbauer F., Pournaki A., Banisch S., Olbrich E. Ideological Differences in Engagement in Public Debate on Twitter. Plos One. 2021;16(3):e0249241. DOI: https://doi.org/10.1371/journal.pone.0249241.
Kanavos A., Voutos Y., Grivokostopoulou F., Mylonas P. Evaluating Methods for Efficient Community Detection in Social Networks. Information. 2022;13(5), 209.
Yang J., Leskovec J. Defining and Evaluating Network Communities Based on Ground-Truth. Knowledge and Information Systems. 2015;42(1):181–213.
Гусарова Н. Ф. Анализ социальных сетей. Основные понятия и метрики. СПб.: Университет ИТМО; 2016. 67 с.
Newman M. E. J. The Structure and Function of Complex Networks. SIAM Review. 2003;45(10):167– 256.
Евин И. А., Хабибуллин Т. Ф. Социальные сети. Компьютерные исследования и моделирование. 2012;4(2):423–430. DOI: 10.20537/2076-7633-2012-4-2-423-430.
Проноза А. А., Виткова Л. А., Чечулин А. А., Котенко И. В., Сахаров Д. В. Методика выявления каналов распространения информации в социальных сетях. Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2018;14(4):362–377. DOI: 10.21638/11702/spbu10.2018.409.
Градосельская Г. В., Щеглова Т. Е., Карпов И. А. Картирование политически активных групп в Фейсбуке1: динамика 2013–2018 гг. Вопросы кибербезопасности. 2019;32(4):94–104. DOI: 10.21681/2311-3456-2019-4-94-104.
Borgatti S. P. Centrality and Network Flow. Social Networks. 2005;27(1):55–71. DOI: 10.1016/j.socnet.2004.11.008.
Щербакова Н. Г. Меры центральности в сетях. Проблемы информатики. 2015;2(27):18–30.
Печенкин В. В., Королев М. С., Димитров Л. В. Прикладные аспекты использования алгоритмов ранжирования для ориентированных взвешенных графов (на примере графов социальных сетей). Труды СПИИРАН. 2018;6(61):94–118. DOI: 10.15622/sp.61.4.
Rajeh S., Savonnet M., Leclercq E. et al. Comparative Evaluation of Community-Aware Centrality Measures. Qual Quant. 2022. DOI: 10.1007/s11135-022-01416-7.
Girvan M., Newman M. E. J. Community Structure in Social and Biological Networks. Proc. Natl. Acad. Sci. USA. 2002;99(12):7821–7827.
Clauset A., Newman M. E. J., Moore C. Finding Community Structure in Very Large Networks. Physical Review E. 2004;70:066111.
Radicchi F., Castellano C., Loreto V., Cecconi F., Parisi D. Defining and Identifying Communities in Networks. Proc. Natl. Acad. Sci. USA. 2004;101(9):2658–2663.
Palla G., Derenyi I., Farkas I., Vicsek T. Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature. 2005;435:814–818.
Newman M. E. J., Girvan M. Finding and Evaluating Community Structure in Networks. Physical Review E. 2004;69:026113.
Newman M. E. J. Fast Algorithm for Detecting Community Structure in Networks. Physical Review E. 2004;69:066133.
Newman M. E. J. Modularity and Community Structure in Networks. Proc. Natl. Acad. Sci. USA. 2006;103(23):8577–8582.
Fortunato S., Newman M. E. J. 20 years of Network Community Detection. Nat. Phys. 2022;18:848–850.
Blondel V. D., Guillaume J.-L., Lambiotte R., Lefebvre E. Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics: Theory and Experiment. 2008;10:P10008.
Rosvall M., Bergstrom C. T. An Information-Theoretic Framework for Resolving Community Structure in Complex Networks. Proc. Natl. Acad. Sci. USA. 2007;104(18):7327–7331.
Rosvall M., Bergstrom C. T. Maps of Information Flow Reveal Community Structure in Complex Networks. Proc. Natl. Acad. Sci. USA. 2008;105(4):1118–1123.
Rosvall M., Bergstrom C. T., Axelsson D. The Map Equation. The European Physical Journal Special Topics. 2009;178(1):13–23.
Esquivel A., Rosvall M. Compression of Flow Can Reveal Overlapping Modular Organization in Networks. Physical Review X. 2011;1:021025.
Rosvall M., Esquivel A., Lancichinetti A., West J., Lambiotte R. Memory in Network Flows and Its Effects on Spreading Dynamics and Community. Nature Communications. 2014;5:4630.
Domenico M., Lancichinetti A., Arenas A., Rosvall M. Identifying Modular Flows on Multilayer Networks Reveals Highly Overlapping Organization in Interconnected Systems. Physical Review X. 2015;5:011027.
Мазалов В. В., Никитина Н. Н. Метод максимального правдоподобия для выделения сообществ в коммуникационных сетях. Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2018;14(3):200–214.
Fortunato S., Barthelemy M. Resolution Limit in Community Detection.´ Proc. Natl. Acad. Sci. USA. 2007;104:36–41.
Lancichinetti A., Fortunato S., Radicchi F. Benchmark Graphs for Testing Community Detection Algorithms. Physical Review E. 2008;78:046110.
Danon L., D´iaz-Guilera A., Duch J., Arenas A. Comparing Community Structure Identification. J. Stat. Mech. 2005;P09008.
Amelio A., Pizzuti C. Is Normalized Mutual Information a Fair Measure for Comparing Community Detection Methods? Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015. Association for Computing; 2015.
Коломейченко М. И., Поляков И. В., Чеповский А. А., Чеповский А. М. Методы визуального анализа графов. М.: Национальный открытый университет «ИНТУИТ»; 2016. 167 с.
Лещев Д. А., Сучков Д. В., Хайкова С. П., Чеповский А. А. Алгоритмы выделения групп общения. Вопросы кибербезопасности. 2019;32(4):61–71. DOI: 10.21681/2311-3456-2019-4-61-71.
Попов В. А., Чеповский А. А. Модели импорта данных из Твиттера. Вестник НГУ. Серия: Информационные технологии. 2021;19(2):76–91. DOI: 10.25205/1818-7900-2021-19-2-76-91.
Воронин А. Н., Ковалева Ю. В., Чеповский А. А. Взаимосвязь сетевых характеристик и субъектности сетевых сообществ в социальной сети Твиттер. Вопросы кибербезопасности. 2020;37(3):40–57. DOI: 10.21681/2311-3456-2020-03-40-57.
Попов В. А., Чеповский А. А. Модели импорта данных из мессенджера Telegram. Вестник Новосибирского государственного университета. Серия: Информационные технологии. 2022;20(2):60–71. DOI: 10.25205/1818-7900-2022-20-2-60-71.
Попов В. А., Чеповский А. А. Выделение неявных сообществ на графе взаимодействия Telegram-каналов с помощью «метода Галактик». Труды ИСА РАН. 2022;72(4):39-50. DOI: 10.14357/20790279220405.
Чеповский А. А., Лобанова С. Ю. Комбинированный алгоритм выделения сообществ в графах взаимодействующих объектов. Бизнес-информатика. 2017;42(4):64–73. DOI: 10.17323/19980663.2017.4.64.73.
Chepovskiy A. A., Leshchev D. A., Khaykova S. P. Core Method for Community Detection. Complex Networks & Their Applications IX. Volume 1: Proceedings of the Ninth International Conference on Complex Networks and Their Applications COMPLEX NETWORKS 2020. Springer. 2021:38–50.