Сүлжээнээс бүлэг илрүүлэх Girvan-Newman алгоритмын өргөтгөл

Authors

  • Dalaijargal Purevsuren National University of Mongolia
  • Батцэнгэл Пүрэвдорж
  • Гантулга Гомбожав
  • Доржнамжирмаа Бадраа

DOI:

https://doi.org/10.22353/mjeas.v5i1.4212

Keywords:

Бүлэг бүтэц, комплекс сүлжээ, сүлжээнээс бүлэг илрүүлэх, Girvan-Newman алгоритм, хоорондын төв

Abstract

Сүлжээнээс бүлэг илрүүлэхэд (community detection) өргөн хэрэглэгддэг, стандарт алгоритм болох GirvanNewman (цаашид GN гэж товчлох) алгоритм, түүний хурдыг сайжруулах боломжуудыг энэ өгүүлэлд авч үзнэ. GN алгоритм нь сүлжээний ирмэгүүдийн хоорондын төв (betweenness centrality)-ийг бодож хамгийн өндөр оноо авсан нэг ирмэгийг устгах, дахин хоорондын төв (цаашид ХТ гэж товчлох) бодож өндөр оноотой ирмэгийг устгах гэх мэтээр ирмэгүүдийг устгаж, бүлгүүдийг илрүүлдэг. GN алгоритмын ажиллах хугацаа нь O(n · m^2) (m-нийт ирмэгийн тоо, n-нийт оройн тоо) учир олон ирмэгтэй том сүлжээнд ашиглахад хүндрэлтэй юм. Алгоритмын хурдыг сайжруулах зорилгоор нэг удаа бодсон ХТ-ийн оноог ашиглан нэгэн зэрэг олон ирмэг устгах, ХТ оноог ойролцоогоор бодох гэсэн хоёр санааг ашиглан GN алгоритмын өргөтгөл дөрвөн хувилбарыг үүсгэв. Сүлжээний ирмэгүүдийг ХТ-ийн оноогоор эрэмбэлж эхний √m (sqrt(m)) оройг нэгэн зэрэг устгах хоёр алгоритм (цаашид GN-2A, GN-2B гэж нэрлэсэн), GN-2A, GN-2B алгоритмуудыг ойролцоо ХТ-ийн оноог бодох аргатай хослуулсан (цаашид GN-3A, GN-3B гэж нэрлэсэн) мөн хоёр хувилбар зохиомжлов. Өргөн хэрэглэгддэг таван сүлжээний өгөгдлийг ашиглан GN-2A, GN-2B, GN-3A, GN-3B алгоритмыг тестэлж, GN алгоритмтай харьцуулан гүйцэтгэлийг үнэллээ. Том сүлжээний хувьд GN алгоритмтай харьцуулахад хурдыг 8-33 дахин сайжруулсан үр дүн харуулж байна. 

Downloads

Download data is not yet available.

References

Girvan M, Newman ME. Community structure in social and biological networks. Proceedings of the national academy of sciences. 2002;99(12):7821-6.

Fortunato S, Newman ME. 20 years of network community detection. Nature Physics. 2022;18(8):848-50.

Yang J, McAuley J, Leskovec J. Community detection in networks with node attributes. In: 2013 IEEE 13th international conference on data mining. IEEE; 2013. p. 1151-6.

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-63.

Rossi R, Ahmed N. The network data repository with interactive graph analytics and visualization. In: Proceedings of the AAAI conference on artificial intelligence. vol. 29; 2015. .

Freeman LC. A set of measures of centrality based on betweenness. Sociometry. 1977:35-41.

Tsalouchidou I, Baeza-Yates R, Bonchi F, Liao K, Sellis T. Temporal betweenness centrality in dynamic graphs. International Journal of Data Science and Analytics. 2020;9:257-72.

Brandes U. A faster algorithm for betweenness centrality. Journal of mathematical sociology. 2001;25(2):163-77.

Kong B, Zhou L, Liu W. Improved modularity based on Girvan-Newman modularity. In: 2012 Second International Conference on Intelligent System Design and Engineering Application. IEEE; 2012. p. 293-6.

Despalatovi´c L, Vojkovi´c T, Vukicevi´c D. Community structure in networks: GirvanNewman algorithm improvement. In: 2014 37th international convention on information and communication technology, electronics and microelectronics (MIPRO). IEEE; 2014. p.997-1002.

Devi S, Rajalakshmi M. Community Detection by Node Betweenness Using Optimized GirvanNewman Cuckoo Search Algorithm. Information Technology and Control. 2023;52(1):53-67.

Riondato M, Kornaropoulos EM. Fast approximation of betweenness centrality through sampling. In: Proceedings of the 7th ACM international conference on Web search and data mining; 2014. p. 413-22.

Riondato M, Upfal E. Abra: Approximating betweenness centrality in static and dynamic graphs with rademacher averages. ACM

Transactions on Knowledge Discovery from Data (TKDD). 2018;12(5):1-38.

Leskovec J, Mcauley J. Learning to discover social circles in ego networks. Advances in neural information processing systems. 2012;25.

Downloads

Published

2023-10-26

How to Cite

[1]
D. Purevsuren, Б. Пүрэвдорж, Г. Гомбожав, and Д. Бадраа, “Сүлжээнээс бүлэг илрүүлэх Girvan-Newman алгоритмын өргөтгөл”, MJEngApplS, vol. 5, no. 1, Oct. 2023.

Issue

Vol. 5 No. 1 (2023): Mongolian Journal of Engineering and Applied Science

Section

Судалгааны өгүүлэл

License

Copyright (c) 2023 Mongolian Journal of Engineering and Applied Sciences

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.