Ключевые слова
граф взаимодействующих объектов
выделение неявных сообществ
анализ социальных сетей
Как цитировать
Аннотация
в работе рассматриваются текущие и перспективные задачи анализа графов, представляющих сложные сети взаимодействующих объектов. Описаны предметные области, для которых актуальны данные модели, рассматриваются практика, проблемы анализа графов социальных сетей и выделения на них неявных сообществ. Обсуждаются основные алгоритмы выделения сообществ на графах и проблема тестирования качества получаемых разбиений. Автором предложены перспективные, на его взгляд, направления развития данной тематики для графов, полученных при импорте данных из реальных социальных сетей. Показана актуальность подходов, предложенных в предыдущих работах автора.
Литература
Евин И. А. Введение в теорию сложных сетей. Компьютерные исследования и моделирование. 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.