Разделение сообщества двусторонней сети на основе увеличения модульности

Аннотация

Двудольные сети представляют собой особый тип графа, состоящий из двух разных типов узлов. Ребра между узлами существуют только между узлами разных типов. Разделение сообществ является важным звеном в сетевом анализе, которое предполагает разделение узлов сети на несколько кластеров или сообществ, чтобы лучше понять и выявить структурные и функциональные характеристики сети. Для двусторонних сетей разделение сообщества может помочь понять, насколько тесные взаимосвязи формируются между различными типами узлов.
Структура двусторонней сети используется во многих областях. Из-за ее уникальных структурных характеристик традиционные методы разделения сообществ часто не могут быть напрямую применены к двусторонним сетям, что делает предлагаемое исследование разделения сообществ двусторонних сетей более значимым. Основная задача этого исследования — разработать новый алгоритм разделения сообщества, основанный на приращении модульности. Этот алгоритм призван преодолеть ограничения существующих методов BRIM и повысить точность и эффективность разделения сообщества в двудольных сетях. Модульность является важным индикатором качества разделения сети, а степень модульности принимает значение от -1 до 1. Когда значение положительное, структура сообщества более плотная, чем случайная сеть, а когда значение отрицательное, структура сообщества менее плотная, чем случайная сеть.
В ходе работы решались следующие проблемы: во-первых, как определить и рассчитать приращение модульности в двудольных сетях; во-вторых, как разработать эффективный алгоритм для максимизации приращения модульности для достижения наилучшего эффекта разделения сообщества; наконец, как проверить эффективность и превосходство нового алгоритма в разделении сообществ двудольных сетей.
Результаты исследований показывают, что новый алгоритм хорошо работает при разделении двусторонних сетевых сообществ, повышает точность и эффективность разделения сообществ и может более эффективно выявлять структурные характеристики сети, тем самым предоставив мощный инструмент анализа в смежных областях.

Сведения об авторах

Irina Nikolaevna Polyakova, Московский государственный университет имени М.В. Ломоносова

доцент кафедры алгоритмических языков факультета вычислительной математики и кибернетики, кандидат физико-математических наук, доцент

Long Chen, Московский государственный университет имени М.В. Ломоносова

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

Литература

1. Calderer G., Kuijjer M.L. Community Detection in Large-Scale Bipartite Biological Networks. Frontiers in Genetics. 2021;12:649440. https://doi.org/10.3389/fgene.2021.649440
2. Newman M.E.J., Cantwell G.T., Young J.-G. Improved mutual information measure for clustering, classification, and community detection. Physical Review E. 2020;101:042304. https://doi.org/10.1103/PhysRevE.101.042304
3. Riolo M.A., Newman M.E.J. Consistency of community structure in complex networks. Physical Review E. 2020;101:052306. https://doi.org/10.1103/PhysRevE.101.052306
4. Newman M.E.J. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America. 2006;103(23):8577-8582. https://doi.org/10.1073/pnas.0601602103
5. Girvan M., Newman M.E.J. Community structure in social and biological networks. Proceedings of the National Academy of Sciences of the United States of America. 2002;99(12):7821-7826. https://doi.org/10.1073/pnas.122653799
6. Cai Z.M. Networkcommunitypartition based on intelligent clustering algorithm. Computer Optics. 2020;44(6):985-989. https://doi.org/10.18287/2412-6179-CO-724
7. Zhang H., Wu Y. Optimization and Application of Clustering Algorithm in Community Discovery. Wireless Personal Communications. 2018;102(4):2443-2454. https://doi.org/10.1007/s11277-018-5264-x
8. Peixoto T.P. Revealing Consensus and Dissensus between Network Partitions. Physical Review X. 2021;11:021003. https://doi.org/10.1103/PhysRevX.11.021003
9. Filho D.V., O Neale D.R.J. Degree distributions of bipartite networks and their projections. Physical Review E. 2018;98(2):022307. https://doi.org/10.1103/PhysRevE.98.022307
10. Arthur R. Modularity and projection ofbipartitenetworks. Physica A: Statistical Mechanics and its Applications. 2020;549:124341. https://doi.org/10.1016/j.physa.2020.124341
11. Valejo A., Góes F., Romanetto L. A benchmarking tool for the generation of bipartite network models with overlapping communities. Knowledge and Information Systems. 2020;62:1641-1669. https://doi.org/10.1007/s10115-019-01411-9
12. Bolorunduro J.O., Zou Z. Community DetectionOn Multi-layer Graph using Intra-layer and Inter-layer Linkage Graphs (CDMIILG). Expert Systems with Applications. 2024;238(A):121713. https://doi.org/10.1016/j.eswa.2023.121713
13. Peng Y., Zhang B., Chang F. Overlapping Community Detection of Bipartite Networks Based on a Novel Community Density. Future Internet. 2021;13(4):89. https://doi.org/10.3390/fi13040089
14. Radicchi F., Castellano C., Cecconi F., Loreto V., Parisi D. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences. 2004;101(9):2658-2663. https://doi.org/10.1073/pnas.0400054101
15. Liu X., Murata T. Community Detection in Large-Scale Bipartite Networks. In: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology. Vol. 01 (WI-IAT '09). IEEE Computer Society, USA; 2009. p. 50-57. https://doi.org/10.1109/WI-IAT.2009.15
16. Xu Y., Chen L. Community Detection on Bipartite Networks Based on Ant Colony Optimization. Journal of Frontiers of Computer Science and Technology. 2014;8(3):296-304.
17. Calatayud J., Bernardo-Madrid R., Neuman M., Rojas A., Rosvall M. Exploring the solution landscape enables more reliable network community detection. Physical Review E. 2019;100:052308. https://doi.org/10.1103/PhysRevE.100.052308
18. Gregori E., Lenzini L., Mainardi S. Parallel K-Clique Community Detection on Large-Scale Networks. IEEE Transactions on Parallel and Distributed Systems. 2013;24(8):1651-1660. https://doi.org/10.1109/TPDS.2012.229
19. Shao J., Han Z., Yang Q., Zhou T. Community Detection based on Distance Dynamics. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15). New York, NY, USA: Association for Computing Machinery; 2015. p. 1075-1084. https://doi.org/10.1145/2783258.2783301
20. Gupta S., Kumar P. A constrained agglomerative clustering approach for unipartite andbipartitenetworkswith application to creditnetworks. Information Sciences. 2021;557:332-354. https://doi.org/10.1016/j.ins.2019.12.085
21. Che S., Yang W., Wang W. A Memetic Algorithm for Community Detection in Bipartite Networks. IEEE Access. 2019;7:126897-126912. https://doi.org/10.1109/ACCESS.2019.2938982
22. Barber M.J. Modularity and community detection in bipartite networks. Physical Review E. 2007;76(6):066102. https://doi.org/10.1103/PhysRevE.76.066102
23. Taguchi H., Murata T., Liu X. BiMLPA: Community Detection in Bipartite Networks by Multi-Label Propagation. In: Masuda N., Goh K.I., Jia T., Yamanoi J., Sayama H. (eds.) Proceedings of NetSci-X 2020: Sixth International Winter School and Conference on Network Science. NetSci-X 2020. Springer Proceedings in Complexity. Cham: Springer; 2020. p. 17-31. https://doi.org/10.1007/978-3-030-38965-9_2
24. Staudt C.L., Meyerhenke H. Engineering Parallel Algorithms for Community Detection in Massive Networks. IEEE Transactions on Parallel and Distributed Systems. 2016;27(1):171-184. https://doi.org/10.1109/TPDS.2015.2390633
25. Lehmann S., Schwartz M., Hansen L.K. Biclique communities. Physical Review E. 2008;78(1):016108. https://doi.org/10.1103/PhysRevE.78.016108
26. Setio A.A.A.,et al.Validation, comparison,and combination of algorithms for automatic detection of pulmonary nodules in computed tomography images: the LUNA16 challenge. Medical Image Analysis. 2017;42:1-13. https://doi.org/10.1016/j.media.2017.06.015
27. Zhao J., You X., Duan Q., Liu S. Multiple Ant Colony Algorithm Combining Community Relationship Network. Arabian Journal for Science and Engineering. 2022;47:10531-10546. https://doi.org/10.1007/s13369-022-06579-x
28. Yen T.C., Larremore D.B. Community detection in bipartite networks with stochastic block models. Physical Review E. 2020;102(3):032309. https://doi.org/10.1103/PhysRevE.102.032309
29. Wu G., Gu C., Yang H. A spectral method of modularity for community detection in bipartite networks. Europhysics Letters. 2022;137(3):31001. https://dx.doi.org/10.1209/0295-5075/ac5506
Опубликована
2024-07-28
Как цитировать
POLYAKOVA, Irina Nikolaevna; CHEN, Long. Разделение сообщества двусторонней сети на основе увеличения модульности. Современные информационные технологии и ИТ-образование, [S.l.], v. 20, n. 2, p. 445-454, july 2024. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/1034>. Дата доступа: 24 aug. 2025 doi: https://doi.org/10.25559/SITITO.020.202402.445-454.
Раздел
Исследования и разработки в области новых ИТ и их приложений