Кластеризация сетей с использованием алгоритма поиска косяков рыб

Обложка

Цитировать

Полный текст

Аннотация

Сеть представляет собой совокупность узлов, соединенных ребрами, которые представляют сущности и их взаимосвязи. В кластеризации социальных сетей узлы организованы в кластеры в соответствии с их шаблонами соединений с целью обнаружения сообществ. Выявление структур сообществ в сетях является важным. Однако существующие методы обнаружения сообществ еще не использовали потенциал алгоритма поиска косяков рыб (FSS) и принципов модулярности. Мы предложили новый метод, основанный на кластеризации с использованием алгоритма поиска рыбной школы и функции модулярности (FSC), который улучшает модулярность в кластеризации сети путем итерационного разбиения сети и оптимизации функции модулярности. Этот подход облегчает обнаружение высокомодулярных структур сообществ, улучшая разрешение и эффективность кластеризации сети. Мы протестировали FSC на известных и неизвестных структурах сетей. Также мы протестировали его на сети, сгенерированной с использованием модели LFR, чтобы проверить его производительность на сетях с различными структурами сообществ. Наша методология демонстрирует высокую эффективность в выявлении структур сообществ, что указывает на ее способность эффективно захватывать сплоченные сообщества и точно определять фактические структуры сообществ.

Об авторах

А. Х Ибрагим

Университет Буира – Акли Моханд Улхадж

Автор, ответственный за переписку.
Email: h.abouzer@univ-bouira.dz
Рю Дрисси Яхья Буира -

М. А Будреф

Университет Буира – Акли Моханд Улхадж

Email: m.boudref@univ-bouira.dz
Рю Дрисси Яхья Буира -

Л. Бадис

Университет Буира – Акли Моханд Улхадж

Email: l.badis@univ-bouira.dz
Рю Дрисси Яхья Буира -

Список литературы

  1. Pavlopoulos G. Using graph theory to analyze biological networks. Pavlopoulos et al. BioData Mining. 2011. vol. 4. pp. 1–27.
  2. Sorokina M., Medigue C., Vallenet D. A new network representation of the metabolism to detect chemical transformation modules. BMC Bioinformatics. 2015. vol. 16. doi: 10.1186/s12859-015-0809-4.
  3. Clauset A., et al. The Structure and Function of Complex Networks. Trends in Ecology and Evolution. 2011. vol. 45. no. 2. p. 78.
  4. Mathew J., Rejikumar K. Communication Structures, its graph representation and decomposition possibilities. Journal of Physics: Conference Series. 2020. doi: 10.1088/1742-6596/1706/1/012050.
  5. Sarker I. Data Science and Analytics: An Overview from Data-Driven Smart Computing, Decision-Making and Applications Perspective. SN Computer Science. 2021. vol. 2. no. 5. doi: 10.1007/s42979-021-00765-8.
  6. Lee M., Buckley C., Zhang X., Louhivuori L., Uhlen P., Wilson C., McCarron J. Small-world connectivity dictates collective endothelial cell signaling. Proceedings of the National Academy of Sciences. 2022. vol. 119. no. 18. doi: 10.1073/PNAS.2118927119.
  7. Hoffman M., Steinley D., Gates K., Prinstein M., Brusco M. Detecting Clusters/Communities in Social Networks. Multivariate behavioral research. 2018. vol. 53. no. 1. p. 57–73. doi: 10.1080/00273171.2017.1391682.
  8. Felmlee D., Kreager D. The invisible contours of online dating communities: A social network perspective. Journal of Social Structure. 2017. vol. 18. no. 1. pp. 1–28. doi: 10.21307/JOSS-2018-004.
  9. Inuwa-Dutse I., Liptrott M., Korkontzelos I. A multilevel clustering technique for community detection. Neurocomputing. 2021. vol. 441. pp. 64–78. doi: 10.1016/J.NEUCOM.2021.01.059.
  10. Bramson A., Hori M., Zha B., Inamoto H. Scoring and classifying regions via multimodal transportation networks. Applied Network Science. 2019. vol. 4. no. 1. doi: 10.1007/S41109-019-0191-7.
  11. Copic J., Jackson M., Kirman A. Identifying Community Structures from Network Data via Maximum Likelihood Methods. The BE Journal of Theoretical Economics. 2009. vol. 9. no. 1. doi: 10.2202/1935-1704.1523.
  12. Yang L., Cao X., He D., Wang C., Wang X., Zhang W. Modularity based community detection with deep learning. International Joint Conference on Artificial Intelligence. 2016. vol. 2016. pp. 2252–2258.
  13. Roy S. Spectral clustering of graphs. 2018. pp. 1–65.
  14. Cohen-Addad V., Kanade V., Mallmann-trenn F., Mathieu C., Hierarchical Clustering: Objective Functions and Algorithms. Journal of the ACM. 2019. vol. 66. no. 4. doi: 10.1145/3321386.
  15. Ghosh S., Halappanavar M., Tumeo A., Kalyanaraman A. Scaling and Quality of Modularity Optimization Methods for Graph Clustering. 2019. pp. 1–6. doi: 10.1109/HPEC.2019.8916299.
  16. Zhang X. et al. Modularity optimization in community detection of complex networks. Europhysics Letters. 2009. vol. 87. no. 3. doi: 10.1209/0295-5075/87/38002.
  17. Brandes U., Delling D., Gaertler M., Gorke R., Hoefer M., Nikoloski Z., Wagner D. Maximizing Modularity is hard. arXiv preprint physics/0608255. 2006.
  18. Bastos Filho C., de Lima Neto F., Lins A., Nascimento A., Lima M. Fish school search. Nature-inspired algorithms for optimisation. 2009. vol. 193. pp. 261–277. doi: 10.1007/978-3-642-00267-0_9.
  19. Bastos-Filho C., Guimarães A. Multi-Objective Fish School Search. International Journal of Swarm Intelligence Research. 2015. vol. 6. no. 1. pp. 23–40. doi: 10.4018/IJSIR.2015010102.
  20. Newman M., Girvan M. Finding and evaluating community structure in networks. Physical Review E. 2004. vol. 69. no. 2. doi: 10.1103/PhysRevE.69.026113.
  21. Lukac Z. Metaheuristic optimization. Proceedings of the 11th International Symposium on Operational Research in Slovenia, SOR 2011. 2011. pp. 17–22. doi: 10.4249/SCHOLARPEDIA.11472.
  22. Kim J., Luo S., Cong G., Yu W. DMCS : Density Modularity based Community Search. Proceedings of the ACM SIGMOD International Conference on Management of Data. 2022. pp. 889–903. doi: 10.1145/3514221.3526137.
  23. Tantardini M., Ieva F., Tajoli L., Piccardi C. Comparing methods for comparing networks. Scientific Reports 2019vol. 9. no. 1. doi: 10.1038/s41598-019-53708-y.
  24. Rustamaji H., Kusuma W., Nurdiati S., Batubara I. Community detection with greedy modularity disassembly strategy. Scientific Reports. 2024. vol. 14. no. 1. doi: 10.1038/s41598-024-55190-7.
  25. Drazdilová P., Prokop P., Platoš J., Snášel V. A hierarchical overlapping community detection method based on closed trail distance and maximal cliques. Information Sciences. 2024. vol. 662. doi: 10.1016/J.INS.2024.120271.
  26. Newman M. Fast algorithm for detecting community structure in networks. Physical Review E – Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics. 2004. vol. 69. no. 6. doi: 10.1103/PhysRevE.69.066133.
  27. Dorfler F., Bullo F. Kron reduction of graphs with applications to electrical networks. IEEE Transactions on Circuits and Systems I: Regular Papers. 2012. vol. 60. no. 1. pp. 150–163. doi: 10.1109/TCSI.2012.2215780.
  28. Bickel P., Chen A. A nonparametric view of network models and Newman-Girvan and other modularities. Proceedings of the National Academy of Sciences. 2009. vol. 106. no. 50. pp. 21068–21073. doi: 10.1073/pnas.0907096106.
  29. Brandes U., Delling D., Gaertler M., Hoefer R., M Nikoloski Z., Wagner D. On Modularity Clustering. IEEE Transactions on knowledge and data engineering. 2008. vol. 20. no. 2. pp. 172–188. doi: 10.1109/TKDE.2007.190689.
  30. Hu Y. Swarm intelligence Ant colony optimization algorithms. 2012. pp. 1–11.
  31. Dehuri S., Ghosh S., Coello C. An introduction to swarm intelligence for multi-objective problems. Swarm Intelligence for Multi-objective Problems in Data Mining. Studies in Computational Intelligence. 2009. vol. 242. doi: 10.1007/978-3-642-03625-5_1.
  32. Herbert-Read J., Perna A., Mann R., Schaerf T., Sumpter D., Ward A. Inferring the rules of interaction of shoaling fish. Proceedings of the National Academy of Sciences. 2011. vol. 108. no. 46. pp. 18726–18731. doi: 10.1073/PNAS.1109355108.
  33. A novel search algorithm based on fish school behavior. 2008 IEEE International Conference on Systems, Man and Cybernetics. Available at: https://sci-hub.se/10.1109/ICSMC.2008.4811695 (accessed: 14/05/2024).
  34. Molina D., Poyatos J., Del Ser J., García S., Hussain A., Herrera F. Comprehensive Taxonomies of Nature- and Bio-inspired Optimization: Inspiration Versus Algorithmic Behavior, Critical Analysis Recommendations. Cognitive Computation. 2020. vol. 12. pp. 897–939. doi: 10.1007/S12559-020-09730-8.
  35. Abangan A., Kopp D., Faillettaz R. Artificial intelligence for fish behavior recognition may unlock fishing gear selectivity. Front Mar Sci. 2023. vol. 10. doi: 10.3389/FMARS.2023.1010761.
  36. Krongauz D., Lazebnik T. Collective evolution learning model for visionbased collective motion with collision avoidance. PLoS One. 2023. vol. 18. no. 5. doi: 10.1371/JOURNAL.PONE.0270318.
  37. Malone T. Collective intelligence. 2007 International Symposium on Collaborative Technologies and Systems. 2008. doi: 10.1109/CTS.2007.4621716.
  38. Huang Z., Application of the Artificial Fish School Algorithm and Particle Filter Algorithm in the Industrial Process Control Particle Filtering Algorithm for Industrial Process Control. Math Probl Eng. 2020. vol. 2020. doi: 10.1155/2020/3070539.
  39. Liu Z., Zhong P., Liu H., Jia W., Sa G., Tan J. Module partition for complex products based on stable overlapping community detection and overlapping component allocation. Research in Engineering Design. 2024. vol. 35. pp. 269–288. doi: 10.1007/S00163-024-00432-Y.
  40. Sun Y., Sun Z., Chang X., Pan Z., Luo L. Community Detection Based on Fish School Effect. IEEE Access. 2022. vol. 10. pp. 48523–48538. doi: 10.1109/ACCESS.2022.3172298.
  41. Saoud B. Networks clustering with bee colony. Artificial Intelligence Review. 2019. vol. 52. no. 2. pp. 1297–1309. doi: 10.1007/s10462-018-9657-8.
  42. Encord E. Available at: https://encord.com/try-it-free/?&utm_campaign=cta-blog-medical-dark (accessed: 10/03/2024).
  43. Cetin P., Amrahov Ş. A new network-based community detection algorithm for disjoint communities. Turkish Journal of Electrical Engineering and Computer Sciences. 2022. vol. 30. no. 6. pp. 2190–2205. doi: 10.55730/1300-0632.3933.
  44. Bonchi F., García-Soriano D., Miyauchi A., Tsourakakis C. Finding densest k-connected subgraphs. Discrete Applied Mathematics. 2021. vol. 305. pp. 34–47. doi: 10.1016/J.DAM.2021.08.032.
  45. Oldham S., Fulcher B., Parkes L., Arnatkeviciute A., Suo C., Fornito A. Consistency and differences between centrality measures across distinct classes of networks. PLoS One. 2019. vol. 14. no. 7. doi: 10.1371/JOURNAL.PONE.0220061.
  46. Leskovec J., Lang K., Dasgupta A., Mahoney M. Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters. Internet Mathematics. 2008. vol. 6. no. 1. pp. 29–123.
  47. Adoni W., Nahhal T., Krichen M., El byed A., Assayad I. DHPV: a distributed algorithm for large-scale graph partitioning. Journal of Big Data. 2020. vol. 7. doi: 10.1186/S40537-020-00357-Y.
  48. Newman M. Modularity and community structure in networks. Available at: https://sci-hub.se/10.1073/pnas.0601602103 (accessed: 14/05/2024).
  49. Rosvall M., Bergstrom C. Maps of random walks on complex networks reveal community structure. Proc Natl Acad Sci U S A. 2008. vol. 105. no. 4. pp. 1118–1123. doi: 10.1073/PNAS.0706851105.
  50. Cordasco G., Gargano L. Label propagation algorithm: a semi-synchronous approach. International Journal of Social Network Mining. 2012. vol. 1. no. 1. doi: 10.1504/IJSNM.2012.045103.
  51. Blondel V., Guillaume J.-L., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment. 2008. vol. 2008. no. 10. doi: 10.1088/1742-5468/2008/10/P10008.
  52. Clauset A., Newman M., Moore C. Finding community structure in very large networks. Physical Review E – Statistical, Nonlinear, and Soft Matter Physics. 2004. vol. 70. no. 6. doi: 10.1103/PhysRevE.70.066111.
  53. Danon L., DIaz-Guilera A., Duch J., Arenas A. Comparing community structure identification. Journal of statistical mechanics: Theory and experiment. 2005. vol. 2005. no. 09. doi: 10.1088/1742-5468/2005/09/P09008.
  54. Lancichinetti A., Fortunato S., Radicchi F. Benchmark graphs for testing community detection algorithms. Physical Review E – Statistical, Nonlinear, and Soft Matter Physics. 2008. vol. 78. no. 4. doi: 10.1103/PHYSREVE.78.046110.
  55. Zachary W. An Information Flow Model for Conflict and Fission in Small Groups. Journal of anthropological research. 1977. vol. 33. no. 4. pp. 452–473. doi: 10.1086/JAR.33.4.3629752.
  56. Girvan M., Newman M. Community structure in social and biological networks. Proceedings of the national academy of sciences. 2002. vol. 99. no. 12. pp. 7821–7826. doi: 10.1073/pnas.122653799.
  57. Lusseau D., Schneider K., Boisseau O., Haase P., Slooten E., Dawson S. The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations: Can geographic isolation explain this unique trait? Behavioral Ecology and Sociobiology. 2003. vol. 54. pp. 396–405. doi: 10.1007/S00265-003-0651-Y.
  58. Newman M. Network data. Network data collection. 2013. Available at: http://www-personal.umich.edu/~mej. (accessed 26.10.2023).
  59. Leskovec J., Mcauley J. Learning to Discover Social Circles in Ego Networks. Advances in neural information processing systems. 2012. vol. 25.
  60. Leskovec J., Lada A., Huberman B. The Dynamics of Viral Marketing. ACM Transactions on the Web (TWEB). 2007. vol. 1. no. 1. doi: 10.1145/1232722.1232727.
  61. Knuth D. The Stanford GraphBase: a platform for combinatorial computing. New York: ACM Press, Addison-Wesley Publishing Company. 2009. 577 p.
  62. Gleiser P., Danon L. Community structure in jazz. Advances in complex systems. 2003. vol. 6. no. 04. pp. 565–573.
  63. Kunegis J. Konect: The Koblenz Network Collection. Proceedings of the 22nd international conference on world wide web. 2013. pp. 1343–1350. doi: 10.1145/2487788.248817.
  64. Knuth D. The Art of Computer Programming: Volume 4 Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. Addison-Wesley Professional, 2008. 228 p.
  65. Yang Z., Algesheimer R., Tessone C. A comparative analysis of community detection algorithms on artificial networks. Scientific reports. 2016. vol. 6. no. 1 doi: 10.1038/srep30750.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».