• Home
  • Community Detection in Complex Networks Using Minimum Spanning Tree and Modularity Maximization

Share To

Article Url


Manuscript ID : 1402042543289 Visit : 1097 Page: 100 - 108

Article Type: Original Research

Community Detection in Complex Networks Using Minimum Spanning Tree and Modularity Maximization

Subject Areas : electrical and computer engineering

sondos bahadori 1 * , maryam nooraei 2

1 - Faculty of Engineering, Islamic Azad University, Ilam, Ir
2 - faculty member

Received: 2023-07-17 Accepted : 2024-03-10 Published : 2024-09-24

Keywords: Complex networks, community, minimum spanning tree, increasing modularity,

Abstract :

Modularity is one of the prominent features of complex networks that divides the structure of these networks into community groups. So far, many methods have been used to identify communities in complex networks, but some of these methods have local optimizations that affect the order of processing nodes and the final solution. In this paper, a new method for finding communities in complex networks using split and merge is proposed. In this method, minimum spanning tree is used as a tool to detect dissimilarity between nodes. In the partitioning process, the edges that show the most dissimilarity are removed in the minimum spanning tree to create smaller groups of nodes in a community. In the merging process, each group is merged with the neighboring group whose combination has the highest increase in modularity compared to other neighboring groups. The results of experiments conducted on real networks and artificial networks show that the method proposed in this article has a good accuracy for identifying communities in complex networks. 

References:

[1] D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-worldl networks," Nature, vol. 393, pp. 440-442, 1998.
[2] A. L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509-512, 15 Oct. 1999.
[3] M. Girvan and M. E. Newman, "Community structure in social and biological networks," Proc. Natl. Acad. Sci., vol. 99, no. 12, pp. 7821-7826, 2002.
[4] M. E. Newman and M. Girvan, "Finding and evaluating community structure in networks," Phys. Rev. E, vol. 69, no. 2, Article ID: 026113, 2004.
[5] M. E. Newman, "The structure and function of complex networks," SIAM Rev., vol. 45, no. 2, pp. 167-256, 2003.
[6] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A. L. Barabási, "Hierarchical organization of modularity in metabolic networks," Science, vol. 297, no. 5586, pp. 1551-1555, 2002.
[7] D. M. Wilkinson and B. A. Huberman, "A method for finding communities of related genes," in Proc. Natl. Acad. Sci. vol. 101, suppl 1, pp. 5241-5248, 2004.
[8] R. Guimera and L. A. N. Amaral, "Functional cartography of complex metabolic networks," Nature vol. 433, no. 7028, pp. 895-900, 2005.
[9] G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, "Self-organization and identification of web communities," Computer, vol. 35, no. 3, pp. 66-70, Mar. 2002.
[10] Y. Dourisboure, F. Geraci, and M. Pellegrini, "Extraction and classification of dense communities in the web," in Proc. of the 16th Int. Conf. on World Wide Web, pp. 461-470, Banff, Canada, 8-12 May 2007.
[11] A. Perianes-Rodríguez, C. Olmeda-Gómez, and F. Moya-Anegón, "Detecting, identifying and visualizing research groups in co-authorship networks," Scientometrics, vol. 82, no. 2, pp. 307-319, 2010.
[12] B. He, Y. Ding, J. Tang, V. Reguramalingam, and J. Bollen, "Mining diversity subgraph in multidisciplinary scientific collaboration networks, a meso perspective," J. Informetrics, vol. 7, no. 1, pp. 117-128, Jan. 2013.
[13] M. A. Porter, J. P. Onnela, and P. J. Mucha, "Communities in networks," Notices of the American Mathematical Society. vol. 56, no. 9, pp. 1082-1097, 2009.
[14] S. Fortunato, "Community detection in graphs," Phys. Rep., vol. 486, no. 3-5, pp. 75-174, Feb. 2010.
[15] M. E. J. Newman, "Communities, modules and large-scale structure in networks," Nature Physics, vol. 8, pp. 25-31, 2012.
[16] M. Coscia, F. Giannotti, and D. Pedreschi, "A classification for community discovery methods in complex networks," Statistical Analysis and Data Mining, vol. 4, no. 5, pp. 512-546, Oct. 2011.
[17] Z. Shi, Y. Liu, and J. Liang, "PSO-based community detection in complex networks," in Proc. 2nd Int. Symp. on Knowledge Acquisition and Modeling, KAM'09, vol. 3, pp. 114-119, Wuhan, China, 30 Nov.-1 Dec. 2009.
[18] M. E. J. Newman, "Detecting community structure in networks," the European Physical J. B-Condensed Matter and Complex Systems, vol. 38, no. 2, pp. 321-330, 2004.
[19] A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," Physical Review E, vol. 70, no. 6, Article ID: 066111, 2004.
[20] C. Shi, Y. Wang, B. Wu, and C. Zhong, "A new genetic algorithm for community detection," Complex Sciences, vol. 535, Article ID: 122259, 2009.
[21] C. Pizzuti, "GA-Net: a genetic algorithm for community detection in social networks," in Proc. of the 10th Parallel Problem Solving from Nature-PPSN X, pp. 1081-1090, Dortmund, Germany, 13-17 Sept. 2008.
[22] M. E. J. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical Review E, vol. 74, no. 3, Article ID: 36104, 2006.
[23] J. Reichardt and S. Bornholdt, "Statistical mechanics of community detection," Phys. Rev., vol. E 74, no. 1, Article ID: 016110, 2006.
[24] U. Brandes, et al., "On finding graph clusterings with maximum modularity," in Proc. of the 33rd Int. Workshop on Graph-Theoretic Concepts in Computer Science, pp. 121-132, Dornburg, Germany, 21-23 Jun. 2007.
[25] P. J. Bickel and A. Chen, "A nonparametric view of network models and Newman-Girvan and other modularities," Proc. Natl. Acad. Sci., vol. 106, pp. 21068-21073, 15 Dec. 2009.
[26] V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," J. Stat. Mech., vol. 2008, Article ID: P10008, Oct. 2008.
[27] B. Saouda and A. Moussaoui, "Community detection in networks based on minimum spanning tree and modularity," Physica A, vol. 460, pp. 230-234, 15 Oct. 2016.
[28] D. Lusseau, "The emergent properties of a dolphin social network," in Proc. R. Soc. London. Ser. B: Biol. Sci., Suppl. 2, vol. 270, pp. S86-S188, 7 Nov. 2003.
[29] J. Eustace, X. Wang, and Y. Cui, "Community detection using local neighborhood in complex networks," Physica A., vol. 436, pp. 665-677, 15 Oct. 2015.
[30] A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, "Finding statistically significant communities in networks," PLoS One, vol. 6, no. 4, Article ID: e18961, 2011.
[31] A. Lancichinetti and S. Fortunato, "Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities," Phys. Rev., vol. E80, no. 1, Article ID: 016118, Jul. 2009.
[32] F. Meng, et al., "Incremental density-based link clustering algorithm for community detection in dynamic networks," Mathematical Problems in Engineering, vol. 2016, no. 1, Article ID: 1873504, 11 pp., Jan. 2016.
[33] K. Nath, R. Shanmugam, and V. Varadaranjan, "ma-CODE: a multi-phase approach on community detection in evolving networks," Information Sciences, vol. 569, pp. 326-343, Aug. 2021.
[34] X. Xu, N. Yuruk, Z. Feng, and T. A. Schweiger, "Scan: a structural clustering algorithm for networks," in Proc. of the 13th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, KDD'07, pp. 824-833, San Jose, CA, USA, 12-15 Aug. 2007.
[35] I. B. El Kouni, W. Karoui, and L. B. Romdhane, "Node importance based label propagation algorithm for overlapping community detection in networks," Expert Systems with Applications, vol. 162, Article ID: 113020, 30 Dec. 2020.
[36] N. Chen, Y. Liu, H. Chen, and J. Cheng, "Detecting communities in social networks using label propagation with information entropy," Physica A: Statistical Mechanics and its Applications, vol. 471, pp. 788-798, 1 Apr. 2017.
[37] G. Yang, W. Zheng, C. Che, and W. Wang, "Graph-based label propagation algorithm for community detection," International J. of Machine Learning and Cybernetics, vol. 11, pp. 1319-1329, 2020.
[38] B. Saoud and A. Moussaoui, "Community detection in networks based on minimum spanning tree and modularity," Physica A: Statistical Mechanics and its Applications, vol. 460, pp. 230-234, 15 Oct. 2016.
[39] J. Wu, X. Li, L. Jiao, X. Wang, and B. Sun, "Minimum spanning trees for community detection," Physica A: Statistical Mechanics and its Applications, vol. 392, no. 9, pp. 2265-2277, 1 May 2013.
[40] J. Zhu, B. Chen, and Y. Zeng, "Community detection based on modularity and k-plexes," Information Sciences, vol. 513, pp. 127-142, Mar. 2020.
[41] X. Zhou, K. Yang, Y. Xie, C. Yang, and T. Huang, "A novel modularity-based discrete state transition algorithm for community detection in networks," Neurocomputing, vol. 334, pp. 89-99, 21 Mar. 2019.
[42] J. Xie, M. Chen, and B. K. Szymanski, "LabelrankT: incremental community detection in dynamic networks via label propagation," in Proc. of the Workshop on Dynamic Networks Management and Mining, pp. 25-32, New York, NY, USA, 22-27 Jun. 2013.
[43] H. Shen, X. Cheng, K. Cai, and M. B. Hu, "Detect overlapping and hierarchical community structure in networks," Physica A: Statistical Mechanics and its Applications, vol. 388, no. 8, pp. 1706-1712, 15 Apr. 2009.
[44] C. L. Staudt and H. Meyerhenke, "Engineering parallel algorithms for community detection in massive networks," IEEE Trans. on Parallel and Distributed Systems, vol. 27, no. 1, pp. 171-184, Jan. 2015.
[45] K. Nath, S. Roy, and S. Nandi, "InOvIn: a fuzzy-rough approach for detecting overlapping communities with intrinsic structures in evolving networks," Applied Soft Computing, vol. 89, Article ID: 106096, Apr. 2020.
Full-Text:
معرفي يک روش جديد خوشه‌يابي خودکار

100                                                                                         نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 22، شماره 2، تابستان 1403

مقاله پژوهشی

شناسایی جامعه در شبکه‌های پیچیده با استفاده از درخت پوشای مینیمم و بیشینه‌سازی ماژولاریتی

سندس بهادری و مریم نورائی آباده

 

 

1 

چکیده: ماژولاریتی، یکی از ویژگی‌های برجسته شبکه‌های پیچیده است که ساختار این شبکه‌ها را به‌صورت گروه‌های جامعه‌ای تقسیم می‌کند. تاکنون روش‌های زیادی برای شناسایی جوامع در شبکه‌های پیچیده به کار گرفته شده است؛ اما برخی از این روش‌ها بهینه‌سازی‌های محلی دارند که ترتیب پردازش نودها، جواب نهایی را تحت تأثیر قرار می‌دهد. در این مقاله، یک روش جدید برای یافتن جوامع در شبکه‌های پیچیده با استفاده از تقسیم و ادغام پیشنهاد شده که در آن از درخت پوشای کمینه به‌عنوان ابزاری برای تشخیص عدم تشابه بین نودها استفاده می‌شود. در فرایند تقسیم، یال‌هایی که بیشترین عدم تشابه را نشان می‌دهند در درخت پوشای کمینه حذف می‌شوند تا گروه‌های کوچک‌تری از نودهای یک جامعه ایجاد شوند. در فرایند ادغام، هر گروه با گروه همسایه ادغام می‌شود که ترکیب آنها بیشترین افزایش ماژولاریتی را نسبت به گروه‌های همسایه دیگر داشته باشند. نتایج آزمایش‌های انجام‌شده بر روی شبکه‌های واقعی و شبکه‌های ساختگی نشان می‌دهند روش پیشنهادی در این مقاله، دقت مطلوبی برای شناسایی جوامع در شبکه‌های پیچیده دارد.

 

کلیدواژه: شبکه‌های پیچیده، جامعه، درخت پوشای مینیمم، افزایش ماژولاریتی.

1-       مقدمه

امروزه شبکه‌ها به‌صورت گسترده برای مدل‌کردن ارتباطات پیچیده بین افراد یا سازمان‌هایی که به دلایل مختلف از قبیل دوستی، خویشاوندی و غیره به هم وابسته هستند، استفاده می‌شوند. در یک شبکه، ساختار جامعه در میان ویژگی‌های خاص شبکه مانند دنیای کوچک [1]، مقیاس مستقل [2] و پیمانه‌ای‌بودن [3] مهم‌ترین ویژگی است. یک جامعه مجموعه‌ای از گره‌هاست که ارتباط‌های داخلی بیشتری نسبت به ارتباط با گره‌های دیگر دارند. جامعه، کلاستر یا ماژول نیز نامیده می‌شود. شناسایی جامعه‌ها برای درک ساختار، وظایف و تکامل شبکه‌های پیچیده مختلف بسیار مهم است [4] و [5] و در کاربردهای گسترده‌ای مانند شناسایی ماژول‌های وظیفه‌ای در شبکه‌های زیستی [6] تا [8]، جمع‌آوری صفحات وب مرتبط با یک موضوع خاص [9] و [10]، گروه‌بندی نویسندگان بر اساس موضوع تحقیق در شبکه‌های همکاری نویسنده‌ها [11] و [12] و ... بسیار مورد توجه قرار گرفته است. در ادامه مقاله، شبکه پیچیده را به‌صورت گراف img0 در نظر گرفته‌ایم که img0 مجموعه نودها img0 و img0 مجموعه یال‌ها img0 را نشان می‌دهند.

تلاش‌های زیادی برای استخراج جامعه‌ها در شبکه‌های پیچیده صورت گرفته است. روش‌ها و الگوریتم‌های یافتن جامعه در شبکه‌ها، موضوع مورد علاقه محققان علوم مختلف از جمله فیزیک، ریاضی، آمار و علم کامپیوتر است و تاکنون تعداد زیادی الگوریتم برای یافتن جامعه در دهه‌های اخیر ارائه شده است [13] تا [16]. الگوریتم‌های تقسیم‌بندی طیفی2 [17] و [18]، روش‌های مبتنی بر تقسیم و ترکیب3 [4] و [19]، الگوریتم‌های تکاملی [20] و [21] و ماکسیمم‌کردن ماژولاریتی نمونه‌هایی از این الگوریتم‌ها هستند.

روش‌های طیفی بر اساس تحلیل مقادیر ویژه ماتریس‌های مربوط به شبکه هستند که توسط نیومن در [22] بررسی شده‌اند. در روش‌های مبتنی بر تقسیم، سعی بر یافتن یال‌های بین جامعه‌ای و حذف آنهاست. بعد از حذف یال‌های بین جامعه‌ای، آنچه که باقی می‌ماند جامعه‌هاست. الگوریتم پیشگام در این زمینه الگوریتم گرون- نیومن است [3] که در آن از معیار مرکزیت بینابینی4 برای شناسایی یال‌های بین جامعه‌ها استفاده می‌شود. این معیار، تعداد مسیرهای کوتاه بین نودها را که از هر یال می‌گذرد تعیین می‌کند. این الگوریتم در بسیاری از شبکه‌ها توانسته است به‌صورت موفقیت‌آمیزی جامعه‌ها را شناسایی کند؛ اما مشکل اصلی این روش پیچیدگی زمانی img0 است که بسیار بالاست. در متدهای مبتنی بر ترکیب، هر نود به‌عنوان یک جامعه در نظر گرفته شده و سپس بر اساس بعضی معیارهای شباهت، این جامعه‌ها با هم ادغام می‌شوند. یکی از معروف‌ترین الگوریتم‌های این دسته، روش پیشنهادشده توسط گرون- نیومن [22] است که بر اساس مقدار ماژولاریتی است.

ماکسیمم‌نمودن ماژولاریتی، مهم‌ترین روش برای شناسایی جامعه در شبکه‌هاست. این روش بر اساس تابع مفید ماژولاریتی است که کیفیت تقسیم‌بندی شبکه به جامعه‌ها را اندازه‌گیری می‌کند. این تابع را می‌توان بر همه تقسیم‌بندی‌های ممکن شبکه اعمال نمود و آن تقسیم‌بندی را که بیشترین مقدار ماژولاریتی را داشته باشد، برگزید. تعداد تقسیم‌بندی‌های مختلف جامعه به‌صورت نمایی است؛ بنابراین به‌دست آوردن بهینه مطلق امکان‌پذیر نیست. در نتیجه به‌جای پیدانمودن بهینه مطلق از روش‌های بهینه نسبی مانند الگوریتم‌های حریصانه از قبیل [3]، [19] و [23] تا [25] استفاده می‌شود.

یک الگوریتم مشهور برای یافتن جامعه، Louvain [26] است که در چندین بسته نرم‌افزاری تحلیل شبکه وجود دارد. Louvain یک الگوریتم اکتشافی بر اساس افزایش ماژولاریتی و در عمل یکی از سریع‌ترین الگوریتم‌های شناسایی جامعه است. در این الگوریتم ابتدا هر نود به‌عنوان یک جامعه در نظر گرفته می‌شود؛ سپس هر جامعه با جامعه‌ای که همسایه آن باشد و میزان افزایش ماژولاریتی ترکیب این دو جامعه، بیشتر از جامعه‌های همسایه دیگر باشد ترکیب می‌شوند و این روند تا جایی تکرار می‌شود که ترکیب جامعه‌ها امکان‌پذیر نباشد. همان طور که نویسنده در [26] گفته است، نتیجه نهایی در این الگوریتم به ترتیب پردازش نودها بستگی دارد. برای به‌دست آوردن یک جواب بهینه مناسب، در این مقاله روشی جدید پیشنهاد شده که در آن به‌جای این که هر نود به‌عنوان یک جامعه اولیه در نظر گرفته شود از ساختار درخت پوشای مینیمم به‌عنوان عدم تشابه در بین نودها و سپس از تجزیه این درخت برای به‌دست آوردن جامعه‌های اولیه استفاده می‌شود و نهایتاً این جامعه‌ها بر اساس افزایش ماژولاریتی با جامعه همسایه‌ای که بیشترین افزایش ماژولاریتی را دارد ترکیب شود. این روش پیشنهادی را 5MST&MM می‌نامیم. نتایج آزمایش‌های مختلف روی شبکه‌های واقعی و شبکه‌های ساختگی نشان می‌دهند که خروجی روش پیشنهادشده بهتر از الگوریتم Louvain و الگوریتم‌های دیگر است.

در این مقاله، یک روش تقسیم و ادغام جدید برای تشخیص جامعه بر اساس درخت پوشای کمینه و ماژولاریتی پیشنهاد می‌شود. درخت پوشای کمینه پس از وزن‌دهی گراف بر اساس حداقل شباهت گره‌های نقطه پایانی برای هر یال ساخته می‌شود. در مرحله بعد و در شرایطی که بهینه‌سازی ماژولاریتی امکان‌پذیر نباشد، این گروه از گره‌ها به‌طور مکرر با استفاده از الگوریتم Louvain ادغام می‌شوند. از این رو مزایای روش پیشنهادی از دو جنبه قابل بررسی است. یکی از مزایای این روش، استفاده از اولین گام بهینه‌سازی گره‌های اولیه با استفاده از درخت پوشای کمینه است که سبب بهبود دقت و زمان اجرا در مقایسه با روش‌های دارای انتخاب تصادفی می‌شود. بهبود دوم در استفاده از معیار ماژولاریتی به‌عنوان معیار کیفیت برای ساختار جوامع است. در بیشتر الگوریتم‌های تشخیص جامعه، ماژولاریتی به‌عنوان معیار کیفیت برای ساختار جامعه انتخاب شده است؛ اما هیچ یک از الگوریتم‌های موجود، گره‌های نامرتبط موجود در زیر جوامع را در نظر نگرفته‌اند. از این کمیت می‌توان برای تشخیص جوامع با دقت بیشتری استفاده کرد.

ادامه مباحث این مقاله به این شرح است: در بخش 2، روش پیشنهادی و الگوریتم مربوط با جزئیات کامل بررسی شده و در بخش 3 نیز تحلیل‌ها و نتایج آزمایش‌ها آمده است. در بخش چهارم به بررسی کارهای مشابه پرداخته شده و نهایتاً در بخش 5 نتیجه‌گیری آمده است.

2-       راهکار پیشنهادشده

یک دسته از تکنیک‌های به‌دست آوردن جامعه‌ها در شبکه‌های پیچیده، تکنیک‌های توسعه محلی و بهینه‌سازی هستند که جواب نهایی در این روش‌ها به ترتیب پردازش نودها بستگی دارد. در این مقاله برای به‌دست آوردن یک جواب بهینه مناسب، روشی جدید بر اساس تقسیم 
و ادغام برای یافتن جامعه‌ها در شبکه‌های پیچیده پیشنهاد شده که 
در آن از ساختار درخت پوشای مینیمم به‌عنوان عدم تشابه در بین نودها استفاده می‌شود. در فرایند تقسیم، یال‌هایی که عدم تشابه بیشتری دارند در درخت پوشای مینیمم حذف می‌شوند تا زیرگروه‌های گسسته کوچکی از نودهای یک جامعه ایجاد شوند. در فرایند ادغام، زیرگروه‌ها به‌گونه‌ای با هم ادغام می‌شوند که جامعه‌های اصلی با حداکثرنمودن مقدار ماژولاریتی به‌دست آیند.

فرض کنید img0 یک شبکه بدون جهت و بدون وزن باشد که img0 مجموعه نودها و img0 مجموعه یال‌هاست. هدف این مقاله، پیدانمودن img0 جامعه img0 است که img0، img0 و img0. از آنجا که به‌دنبال حذف یال‌های بین رئوسی هستیم که تشابه کمتری دارند برای این منظور از یک معیار عدم تشابه برای برچسب‌زدن یال‌ها استفاده می‌شود [27]. وزن یال‌ها را می‌توان به‌صورت تابع img0 تعریف نمود که مقدار وزن هر یال img0 نشان‌دهنده عدم تشابه بین دو یال است. عبارت عدم تشابه را می‌توان به‌صورت زیر تعریف نمود

img0        (1)

که img0 مجموعه نودهای همسایه نود img0 است. با توجه به (1) اگر دو رأس تشابه کمتری داشته باشند یال بین آنها وزن بیشتری می‌گیرد و بنابراین احتمال بیشتری برای حذف آن یال هنگام یافتن درخت پوشای مینیمم وجود دارد.

به‌منظور انجام فرایند تقسیم، در گرافی که وزن یال‌های آن با استفاده از تابع img0 محاسبه می‌شود ابتدا درخت پوشای مینیمم ایجاد می‌شود. درخت پوشای مینیمم برای گراف img0، درخت img0 است  که img0 مینیمم  باشد  که img0 و 

img0 است. در درخت پوشای مینیمم img0، مجموعه img0 را انتخاب نموده که img0 مجموعه‌ای با img0 از یال‌های درخت img0 با وزن بیشتر است. با حذف‌کردن یال‌های مجموعه img0 از درخت img0، در واقع img0 مؤلفه جدا در img0 ایجاد می‌گردند و هر یک از این مؤلفه‌ها به‌عنوان یک جامعه اولیه در نظر گرفته می‌شوند؛ در نتیجه تعداد img0 img0 جامعه اولیه ایجاد می‌شود.

بعد از تقسیم درخت پوشای مینیمم به img0 جامعه، فاز ادغام برای به‌دست آوردن جامعه‌های نهایی ساختار گراف اعمال می‌شود. گام اساسی در فاز ادغام این است که جامعه‌ها بر چه اساسی با هم ادغام شوند. چون هدف، افزایش ماژولاریتی است در فاز ادغام بدین صورت عمل می‌شود که برای جامعه img0، تمام جامعه‌های همسایه آن مانند img0 را در نظر گرفته و مقدار افزایش ماژولاریتی در اثر ادغام جامعه img0 با هر یک از جامعه‌های همسایه img0 را محاسبه نموده و جامعه img0 با جامعه‌ای که مقدار افزایش ماژولاریتی بیشتری دارد ادغام می‌شود. این عمل را آن قدر تکرار نموده تا مقدار ماژولاریتی تغییر نکند. برای محاسبه افزایش مقدار ماژولاریتی از عبارت زیر استفاده می‌شود [26]

img0        (2)

که img0 تعداد  یال‌های  درون  جامعه img0، img0 مجموع  درجه  نودهای 

جامعه img0، img0 مجموع درجه نودهای جامعه img0، img0 تعداد یال‌های بین دو جامعه img0 و img0 و img0 تعداد یال‌های گراف است.

الگوریتم پیشنهادی را می‌توان به‌صورت شکل 1 بیان نمود.

img0 

شکل 1:  الگوریتم روش پیشنهادی.

 

2-1 مثال حل‌شده

در شکل 2- الف گرافی آمده که از آن برای نمایش مراحل اجرای روش پیشنهادی در این مقاله استفاده می‌شود. همان طور که در شکل 
1- الف نشان داده شده است، این گراف دارای دو جامعه جدا از هم است. بعد از اجرای گام 1 و 2 از روش پیشنهادی، خروجی برنامه درخت پوشای مینیمم img0 می‌باشد که در شکل 2- ب نشان داده شده است. پس از اجرای گام 3، شکل 2- ج ایجاد می‌شود که نهایتاً با اجرای گام 4 جامعه‌های نهایی نشان داده شده در شکل 2- د حاصل می‌گردد. همان طور که در شکل 2 نشان داده شده است بر روی گراف شکل الف، ابتدا با استفاده از معیار عدم تشابه، یال‌ها را وزن‌دار و سپس درخت پوشای مینیمم را مانند شکل ب پیدا می‌کنیم. در گام بعدی img0 از یال‌های با بیشترین برچسب حذف شده و شکل ج حاصل می‌گردد و در گام آخر، زیرجامعه‌های به‌دست آمده با استفاده از افزایش ماژولاریتی با هم ادغام شده تا جوامع نهایی حاصل شوند (مانند شکل د).

2-2 تحلیل پیچیدگی زمانی الگوریتم پیشنهادشده

برای تحلیل پیچیدگی زمانی الگوریتم پیشنهادشده باید همه گام‌های اساسی آن را در نظر گرفت. محاسبه ماتریس عدم تشابه دارای پیچیدگی زمانی img0 و پیداکردن درخت پوشای مینیمم دارای پیچیدگی زمانی img0 است. حذف مجموعه img0 از مجموعه یال‌های درخت پوشای مینیمم img0 دارای حداکثر پیچیدگی زمانی img0 است. ادغام زیرگراف‌های به‌دست آمده بر اساس حداکثر مقدار افزایش ماژولاریتی دارای پیچیدگی زمانی img0 است.

3-       نتایج آزمایش‌ها و تحلیل

3-1 معیارهای ارزیابی

معیارهای ارزیابی جامعه‌های به‌دست آمده را می‌توان به دو دسته کلی معیارهای کیفیت و معیارهای دقت دسته‌بندی نمود. از معیارهای کیفیت معمولاً زمانی استفاده می‌شود که زمینه اصلی گراف در دسترس نباشد مانند شبکه‌های دنیای واقعی. ازجمله مهم‌ترین معیارهای کیفیت می‌توان معیار ماژولاریتی و معیار چگالی را نام برد. معیارهای دقت زمانی استفاده می‌شوند که زمینه اصلی گراف موجود باشد و یکی از مهم‌ترین معیارهای دقت معیار img0 است. برای ارزیابی الگوریتم پیشنهادشده در این مقاله از سه معیار ماژولاریتی img0، چگالی img0 و img0 استفاده شده که به‌صورت زیر تعریف می‌شوند:

-        ماژولاریتی img0: از این معیار برای ارزیابی روش پیشنهادشده بر روی گراف‌های واقعی استفاده می‌شود. این معیار به‌صورت زیر تعریف می‌گردد

img0 

(الف)

img0 

(ب)

img0 

(ج)

img0 

(د)

شکل 2:  مراحل اجرای الگوریتم پیشنهادی.

 

img0        (3)

        که img0 تعداد یال‌های درون جامعه img0، img0 تعداد کل یال‌های گراف و img0 مجموع درجه نودهای موجود در جامعه img0 است.

-        چگالی img0: این معیار به‌صورت زیر تعریف می‌شود

img0        (4)

        که img0 تعداد یال‌ها، img0 تعداد یال‌های درون جامعه‌ای، img0 تعداد نودهای هر جامعه و img0 تعداد جامعه‌هاست.

-        img0 به‌صورت زیر تعریف می‌شود

img0        (5)

        که در این عبارت img0 برچسب جامعه در زمینه اصلی، img0 برچسب جامعه به‌دست آمده، img0 تعداد جامعه‌ها، img0 تعداد نودهای زمینه اصلی در جامعه img0ام، img0 تعداد نودهای به‌دست آمده برای جامعه img0 و img0 تعداد نودهای جامعه img0 در زمینه اصلی است که برچسب img0 با استفاده از الگوریتم استفاده‌شده به آنها نسبت داده شده است. اگر نتایج به‌دست آمده با زمینه اصلی یکسان باشد img0 ماکسیمم مقدار یعنی یک و در شرایطی که نتایج به‌دست آمده با زمینه اصلی کاملاً متفاوت باشد img0 صفر می‌شود. بر اساس مفاهیم تئوری اطلاعات، صورت کسر مطابق با اطلاعات انحصاری  بین  نتایج  جامعه‌های  دو  پارتیشن  و  مخرج  کسر  آنتروپی 

img0 

(الف)

img0 

(ب)

 

[1] این مقاله در تاریخ 25 تیر ماه 1402 دریافت و در تاریخ 10 بهمن ماه 1402 بازنگری شد.

سندس بهادری (نویسنده مسئول)، گروه مهندسی کامپیوتر، واحد ایلام، دانشگاه آزاد اسلامی، ایلام، ایران، (email: sondos.bahadori@iau.ac.ir).

مریم نورائی آباده، گروه مهندسی کامپیوتر، واحد آبادان، دانشگاه آزاد اسلامی، آبادان، ایران، (email: ma.nooraei@iau.ac.ir).

[2] . Spectral Partitioning

[3] . Divisive and Agglomeration

[4] . Betweenness

[5] . Minimum Spanning Tree and Modularity Maximization

شکل 3:  (الف) زمینه اصلی گراف کاراته و (ب) جامعه‌های به‌دست آمده با استفاده از روش پیشنهادی.

 

جدول 1: مقایسه معیار ماژولاریتی روش پیشنهادی با روش‌های OSLOM، Lovain، Local community detection و MST&modulatity بر روی گراف‌های واقعی.

 

گراف‌های واقعی

الگوریتم

MST&MM

MST&Modulatity [27]

Local community detection [29]

Louvain [28]

OSLOM [30]

Football

5070/0

49307/0

393/0

4969/0

477/0

Karate

4117/0

415/0

3814/0

433/0

3595/0

Dolphin

50142/0

4789/0

2973/0

496/0

436/0

Book

507/0

4946/0

4485/0

496/0

507/0

 

جدول 2: مقایسه معیار Density روش پیشنهادی با روش‌های OSLOM، Louvain، Local community detection و MST&modularity بر روی گراف‌های واقعی.

 

گراف‌های واقعی

الگوریتم

MST&MM

MST&Modularity [27]

Local community detection [29]

Louvain [28]

OSLOM [30]

Football

3183/0

0240/0

0076/0

0159/0

2824/0

Karate

0797/0

0655/0

0301/0

0587/0 

0017/0

Dolphin

08562/0

0387/0

0133/0

0366/0

0892/0

Book

1626/0

0132/0

0070/0

0124/0

1537/0

 

 

        است. هرچه مقدار دو معیار img0 و img0 بیشتر باشد کارایی الگوریتم مطلوب‌تر است. در ادامه ابتدا نتایج آزمایش را بر روی گراف‌های واقعی و سپس نتایج آزمایش را بر روی گراف‌های کامپیوتری بررسی می‌کنیم.

3-2 شبکه‌های دنیای واقعی

کارایی روش پیشنهادشده در این مقاله از نظر معیار ماژولاریتی و چگالی بر روی گراف‌های واقعی با روش پیشنهادی در [29] و روش‌های Louvain [28] و OSLOM [30] مقایسه شده است. همچنین کارایی روش این مقاله با روش پیشنهادی [27] مقایسه شده است. در این مقاله از درخت پوشای مینیمم برای تجزیه شبکه استفاده شده است؛ اما برای ترکیب، هر بار جامعه‌ها را با هم ترکیب نموده و ترکیبی را که ماژولاریتی بیشتری داشته باشد انتخاب می‌کند. این روش را MST&modulatity می‌نامیم. در ادامه ابتدا گراف‌های واقعی معرفی شده‌اند و نتیجه ارزیابی در جداول 1 و 2 آمده‌اند.

3-2-1 فوتبال

شبکه فوتبال1 یک شبکه معروف برای تعیین جامعه‌هاست [4]. این شبکه دارای 115 تیم است که به 11 باشگاه تقسیم می‌شوند. تیم‌های داخل یک باشگاه، بازی بیشتری با هم دارند. در واقع تیم‌های داخل یک باشگاه، یک جامعه را تشکیل می‌دهند و هر باشگاه یک جامعه است. از این 115 تیم، 4 تیم عضو هیچ باشگاهی نیستند. روش پیشنهادشده در این مقاله برای این دیتاست 7 جامعه را شناسایی می‌کند. از آنجا که یکی از اهداف این مقاله، تقسیم‌بندی شبکه با افزایش ماژولاریتی است، ماژولاریتی این تقسیم‌بندی 570/0 است؛ در حالی که ماژولاریتی زمینه اصلی این شبکه 554/0 است.

3-2-2 باشگاه کاراته

باشگاه کاراته2 یک شبکه اجتماعی است که ارتباط بین 34 نفر در یک باشگاه دانشگاهی آمریکا را نشان می‌دهد. باشگاه به علت اختلاف بین یکی از مدرسین و مسئول باشگاه به دو جامعه تقسیم شده و زمینه اصلی این گراف در شکل 3- الف نشان داده شده است. روش پیشنهادشده در این مقاله برای این دیتاست، 4 جامعه را شناسایی می‌کند که این جامعه‌های شناسایی‌شده در شکل 3- ب نشان داده شده است. ماژولاریتی این تقسیم‌بندی 4117/0 می‌باشد؛ در حالی که ماژولاریتی زمینه اصلی شبکه 371/0 است.

 

[1] . American College Football

[2] . Zachary's Karate Club

جدول 3: مشخصات گراف‌های ایجادشده به‌وسیله LFR Benchmark.

 

Network

img0 

img0 

img0 

img0 

img0 

img0 

img0 

img0 

img0 

1000

20

50

8/0- 1/0

1

2

20

50

img0 

2000

40

100

8/0- 1/0

1

2

40

100

 

جدول 4: نتیجه مقایسه مقدار پارامتر img0 بر روی گراف‌های img0 با تغییر مقدار پارامتر img0 برای روش پیشنهادی در این مقاله 
با روش‌های OSLOM، Louvain، Local community detection و MST&Modularity.

 

الگوریتم

img0 

8/0

7/0

6/0

5/0

4/0

3/0

2/0

1/0

OSLOM

0158/0

0802/0

1980/0

1

1

1

1

1

Louvain

269/0

387/0

54/0

62/0

667/0

715/0

718/0

83/0

Local community detection

015/0

032/0

043/0

255/0

29/0

555/0

1

1

MST&Modularity

003/0

003/0

002/0

006/0

877/0

948/0

975/0

989/0

MST&MM

2/0

55/0

93/0

1

1

1

1

1

 

جدول 5: نتیجه مقایسه مقدار پارامتر img0 بر روی گراف‌های img0 با تغییر مقدار پارامتر img0 برای روش پیشنهادی در این مقاله 
با روش‌های OSLOM، Louvain، Local community detection و MST&Modularity.

 

الگوریتم

img0 

8/0

7/0

6/0

5/0

4/0

3/0

2/0

1/0

OSLOM

205/0

41/0

798/0

905/0

908/0

912/0

940/0

956/0

Louvain

236/0

3589/0

5337/0

6379/0

7087/0

761/0

7869/0

827/0

Local community detection

0

0

0

0

0

0

684/0

7679/0

MST&Modularity

0

0

0

0

9148/0

96/0

991/0

9974/0

MST&MM

223/0

4986/0

8998/0

9539/0

976/0

9879/0

993/0

9992/0

 

 

3-2-3 شبکه دلفین

این شبکه از مشاهداتی که 7 سال بر روی 62 دلفین صورت گرفته ایجاد شده است [28]. نودها در این شبکه نشان‌دهنده دلفین‌هاست و نودهایی که بین آنها یال وجود دارد دارای تعاملات بیشتری نسبت به سایر نودها هستند. مطالعات قبلی بر روی این گراف، 2 و 4 جامعه را تشخیص داده‌اند. روش پیشنهادشده در این مقاله برای این دیتاست 5 جامعه را شناسایی می‌کند و ماژولاریتی این تقسیم‌بندی 5142/0 است؛ این در حالی است که مقدار این پارامتر برای زمینه اصلی این گراف 3735/0 می‌باشد.

3-2-4 شبکه کتاب

شبکه کتاب1 خرید چندین عنوان کتاب را درباره سیاست‌های آمریکا مدل می‌کند که در طول انتخابات سال 2004 ریاست جمهوری چاپ شده‌اند. این گراف شامل 105 کتاب (نود) و 441 یال بین کتاب‌های خریداری‌شده با هم است [27]. مقدار ماژولاریتی به‌دست آمده برای این گراف با استفاده از روش پیشنهادی این مقاله 507/0 است.

3-3 گراف‌های ساختگی

3-3-1 گراف‌های ایجادشده با LFR Benchmark

یک دسته از گراف‌های ساختگی که برای ارزیابی کارایی روش پیشنهادی در این مقاله مورد استفاده قرار گرفته‌اند، گراف‌های ساختگی با استفاده از LFR Benchmark [31] است. گراف‌های ایجادشده به‌وسیله LFR از نظر ساختاری و توزیع درجه نودها مشابه گراف‌های واقعی هستند. در دو دسته گراف‌های ایجادشده، تعداد نودها را 1000 و 2000 در نظر گرفتیم؛ این گراف‌ها را به‌ترتیب img0 و img0 نامیدیم و مقدار پارامتر img0 را که میزان تداخل جامعه‌هاست از 1/0 تا 8/0 تغییر دادیم. پارامتر img0 که میانگین درجه نودهاست برای img0 و img0 به‌ترتیب 20 و 40 در نظر گرفته شده است. حداقل اندازه هر جامعه را در img0 مقدار 20 و در img0 مقدار 40 و حداکثر اندازه هر جامعه را در img0 مقدار 50 و در img0 مقدار 100 نود در نظر گرفتیم. در جدول 3 مشخصات گراف‌های ایجادشده آمده است. img0 حداکثر درجه هر نود است. img0 حداقل تعداد نودهای هر جامعه و img0 حداکثر تعداد نودهای هر جامعه است. برای هر مقدار پارامتر img0، 10 گراف ایجاد نموده و مقدار پارامتر img0، میانگین مقدار این پارامتر برای گراف‌های ایجادشده است. از پارامتر img0 برای ارزیابی روش پیشنهادی بر روی گراف‌های LFR Benchmark استفاده شده است. مانند گراف‌های واقعی نتیجه این روش با روش پیشنهادی در [29] و روش‌های Louvain [28]، OSLOM [30] و MST&Modularity [27] مقایسه شده و نتیجه این مقایسه‌ها در جداول 4 و 5 آمده است. همان طور که نشان داده شده است، کارایی روش پیشنهادی در این مقاله در همه گراف‌های LFR از سایر روش‌ها به‌جز روش OSLOM بهتر است.

3-3-2 گراف‌های ایجادشده با استفاده از مدل گرون- نیومن

گراف‌هایی که به‌وسیله این مدل تولید می‌شوند به این صورت هستند که دارای 32، 64 و 128 نود می‌باشند. رئوس این گراف‌ها به 4 جامعه با اندازه یکسان به‌ترتیب با اندازه‌های 8، 16 و 32 نود تقسیم شده‌اند. هر رأس دارای img0 یال به رئوسی است که با هم در یک جامعه قرار دارند. همچنین هر رأس دارای img0 یال به رئوسی است که عضو جامعه‌های دیگر  هستند.  در  گراف‌های  با  64  و  128  نود  مقادیر  img0  و  img0  را 

جدول 6: درصدی از نودها که در گراف با 32 نود با تغییر img0 درست خوشه‌بندی شده‌اند.

 

الگوریتم

img0 

3

2

1

0

OSLOM

%100

%100

%100

%100

Louvain

%100

%100

%100

%100

Local community detection

%13

%16

%100

%100

MST&Modularity

%28

%50

%100

%100

MST&MM

%100

%100

%100

%100

 

به‌گونه‌ای تغییر می‌دهیم که img0 باشد. در گراف با 32 نود، مقادیر img0 و img0 را به‌گونه‌ای تغییر می‌دهیم که img0 باشد. با افزایش مقدار img0 از مقادیر کوچک‌تر به مقادیر بیشتر، تشخیص دقیق خوشه‌ها سخت‌تر می‌شود. در جداول 6 تا 8 کسری از نودها که به‌صورت صحیح توسط الگوریتم پیشنهادی این مقاله و روش شناسایی جامعه‌ها با استفاده از همسایگی محلی [29] روش‌های Louvain [28]، OSLOM [30] و MST&Modularity [27] خوشه‌بندی شده‌اند به‌صورت تابعی از img0 نمایش داده شده است. همان طور که در این جداول نشان داده شده است، عملکرد الگوریتم پیشنهادشده خوب بوده و از هر دو الگوریتم Louvain و MST&Modularity بهتر است.

کارایی روش پیشنهادی بر اساس مقدار معیار img0 در مقایسه با روش شناسایی جامعه‌ها با استفاده از همسایگی محلی [29] روش‌های Louvain [28] و OSLOM [30] برای گراف با 32، 64 و 128 نود به ترتیب در جداول 9 تا 11 آمده است. همان طور که در این شکل‌ها نشان داده شده، کارایی روش پیشنهادی در این مقاله در همه این گراف‌ها از سایر روش‌ها به‌جز روش OSLOM بهتر است.

4-       کارهای مرتبط

در سال‌های اخیر تلاش‌های زیادی برای کشف این موضوع صورت گرفته است. روش گیروان و نیومن [3] یک رویکرد تشخیص جامعه را بر اساس تعداد کوتاه‌ترین مسیرهایی که از لبه‌ای به نام مرکزیت بین‌المللی عبور می‌کنند، معرفی کرد. دونتی و همکاران [3] یک رویکرد خوشه‌بندی سلسله‌مراتبی را پیشنهاد کردند که در آن شباهت بین گره‌ها توسط بردارهای ویژه ماتریس لاپلاسی اندازه‌گیری می‌شود. iDBLINK [32] یک الگوریتم خوشه‌بندی پیوند مبتنی بر چگالی افزایشی برای تشخیص جامعه در شبکه‌های پویاست. این الگوریتم تراکم پیوند را در هر شبکه برای هر موردی مانند ایجاد، رشد، ادغام، حذف، انقباض و تقسیم جوامع پیوندها تنظیم می‌کند که می‌تواند ساختار جامعه فعلی را با توجه به ساختار قبلی جامعه به‌سرعت و کارآمد به‌روز کند. InOrder [33] یک الگوریتم تشخیص جامعه مبتنی بر چگالی در شبکه‌های پویاست که شامل دو مرحله است؛ یک فاز آنلاین که در آن توالی پیمایش شبکه حفظ می‌شود و یک فاز آفلاین که در آن جوامع مورد نظر از دنباله استخراج می‌شوند. SCAN [34] خوشه‌ها،‌‌ هاب‌ها و نقاط پرت را در شبکه‌ها تشخیص می‌دهد. این روش یک گره خاص را با توجه به مشارکت همسایگانش در آن زیرگروه به یک زیرگروه اختصاص می‌دهد. الگوریتم انتشار برچسب مبتنی بر اهمیت گره (NI-LPA) [35] برای شناسایی جوامع همپوشانی در نمودارها پیشنهاد شده و یک مکانیسم استنتاج اطلاعاتی از ویژگی‌های گره‌ها را معرفی می‌کند تا یک فرایند انتشار و فیلترکردن خاص را درک کند. چن و همکاران [36] یک تکنیک انتشار برچسب مبتنی بر آنتروپی اطلاعات را برای شناسایی جوامع در شبکه‌های اجتماعی پیشنهاد کردند. در این رویکرد، ضریب خاصی برای به‌روزرسانی برچسب گره‌ها اعمال می‌شود. رغوان و همکاران [15] یک الگوریتم تشخیص جامعه مبتنی بر انتشار برچسب را معرفی کردند که در آن، یک برچسب منحصربه‌فرد به هر گره اختصاص داده می‌شود و پس از هر مرحله، برچسب گره بر اساس برچسبی که اکثر همسایگان آن در حال حاضر دارند به‌روز می‌شود. GLPA [37]، الگوریتم انتشار برچسب مبتنی بر گراف، جوامع را در دو مرحله تشخیص می‌دهد. ابتدا هر برچسب گره بر اساس شباهت گره بین همسایگان اختصاص داده شده و در مرحله دوم، یک نمودار وزنی از اجزای متصل (یا گره‌های فوق‌العاده) برای شناسایی جوامع نهایی ساخته می‌شود. بلال سعود و همکارش [38] یک رویکرد جدید تشخیص جامعه را بر اساس درخت پوشای حداقل و ماژولاریتی پیشنهاد کردند. این رویکرد، ابتدا زیرگروه‌های کوچک جداشده از یک شبکه را با پارامتر عدم تشابه گره مبتنی بر MST تولید می‌کند. پس از آن، ادغام جامعه در میان زیرگروه‌های مختلف، تنها زمانی انجام می‌شود که افزایش قابل توجهی در ماژولاریتی پس از ترکیب وجود داشته باشد. وو و همکاران [39] یک روش درخت پوشای حداقل دو دور را بر اساس یک ماتریس فاصله برای شناسایی ساختار جامعه در شبکه‌ها پیشنهاد کردند. ژو و همکاران [40] یک رویکرد بهینه‌سازی ماژولاریتی با K-plexes (MOKP) را برای شناسایی جوامع در شبکه‌های پیچیده پیشنهاد کرد. در فاز اول، MOKP با استفاده از k-plexes، دانه‌های جامعه را تولید می‌کند و در فاز دوم، گره‌های باقیمانده بر اساس بهینه‌سازی ماژولاریتی به گروه‌های مربوط اختصاص داده می‌شوند. الگوریتم انتقال حالت گسسته مبتنی بر ماژولاریتی [41] (MDSTA) برای مشکل تشخیص جامعه از عملگرهای رأس و جایگزین جامعه برای جستجوی سراسری استفاده می‌کند. علاوه بر این، یک عملیات متقاطع دوطرفه بر روی افراد نخبه بهینه‌شده انجام می‌شود تا از راه حل‌های بهینه محلی فرار کنند. از سوی دیگر در گذشته نه چندان دور، تعداد زیادی روش تشخیص جامعه پیشنهاد شده که بر تابع نقشه‌برداری مبتنی بر دانش ساختاری محلی یا جهانی مانند LabelRank [42]، EAGLE [43] و الگوریتم Louvain [44] تکیه دارند. یک رویکرد چندمرحله‌ای به نام ma-CODE [33] برای یافتن جوامع بر اساس تداعی‌های ذاتی آنها بدون اینکه از قبل بدانیم چند جامعه وجود دارد استفاده می‌شود. تشخیص جامعه همپوشانی ذاتی در شبکه‌های افزایشی [45] (InOvIn) یک رویکرد مبتنی بر فازی خشن برای تشخیص جوامع غیرمتشابه، همپوشانی و سلسله‌مراتبی (ذاتی) در شبکه‌های در حال تکامل است. در این روش، نویسنده از خوشه‌بندی فازی خشن برای یافتن جوامع همپوشانی استفاده می‌کند. علاوه بر این برای آشکارساختن ساختارهای جامعه ذاتی در داخل یک جامعه، یک تغییر چگالی در طول یک دوره زمانی خاص بر اساس میانگین و انحراف استاندارد محاسبه می‌شود. کارهای مشابه بر اساس تکنیک اصلی روش در جدول 12 آمده است.

5-       نتیجه‌گیری و راهکارهای آتی

از آنجا که در بعضی از تکنیک‌های به‌دست آوردن جامعه‌ها در شبکه‌های پیچیده، جواب نهایی به ترتیب پردازش نودها بستگی دارد، برای به‌دست آوردن یک جواب بهینه مناسب در این مقاله روشی بدون پارامتر برای شناسایی جامعه‌ها در شبکه‌های پیچیده ارائه شده که از معیار عدم تشابه نودها برای تجزیه گراف به زیرگراف‌های مناسبی استفاده می‌کند که نودهای این زیرگراف‌ها دارای بیشترین تشابه هستند. سپس در فرایند ادغام، این زیرگراف‌ها بر اساس افزایش ماژولاریتی با زیرگراف‌های همسایه ترکیب می‌شوند. نتایج اعمال این روش بر روی انواع مختلف 

[1] . Books

جدول 7: درصدی از نودها که در گراف با 64 نود با تغییر img0 درست خوشه‌بندی شده‌اند.

 

الگوریتم

img0 

8

7

6

5

4

3

2

1

0

OSLOM

%100

%100

%100

%100

%100

%100

%100

%100

%100

Louvain

%32

%39

%39

%39

%39

%100

%100

%100

%100

Local community detection

%25

%25

%25

%25

%25

%25

%84

%84

%84

MST&Modularity

%25

%25

%25

%25

%25

%25

%25

%25

%50

MST&MM

%100

%100

%100

%100

%100

%100

%100

%100

%100

 

جدول 8: درصدی از نودها که در گراف با 128 نود با تغییر img0 درست خوشه‌بندی شده‌اند.

 

الگوریتم

img0 

8

7

6

5

4

3

2

1

0

OSLOM

%53

%56

%57

%74

%74

%80

%80

%100

%100

Louvain

%12

%14

%12

%14

%40

%80

%80

%100

%100

Local community detection

%22

%25

%55

%73

%70

%76

%75

%100

%100

MST&Modularity

%25

%25

%25

%25

%25

%25

%25

%50

%100

MST&MM

%60

%60

%60

%74

%77

%80

%80

%100

%100

 

 

جدول 9: مقدار پارامتر img0 با تغییر img0 در گراف با 32 نود.

 

الگوریتم

img0 

3

2

1

0

OSLOM

1

1

1

1

Louvain

1

1

1

1

Local community detection

591/0

512/0

1

1

MST&Modularity

58/0

1

1

1

MST&MM

1

1

1

1

 

گراف‌های ساختگی و گراف‌های واقعی نشان می‌دهند که این روش 
در مقایسه با روش‌های دیگر شناسایی جامعه‌ها، کارایی بالایی دارد. این روش به دلیل عدم وابستگی به ترتیب پردازش نودها و همچنین عدم نیاز به تعیین پارامترهای خاص می‌تواند به‌عنوان یک روش مؤثر و مناسب برای شناسایی جامعه‌ها در شبکه‌های پیچیده مورد استفاده قرار گیرد. در آینده می‌توان به بهبود و بهینه‌سازی این روش و همچنین اعمال آن به شبکه‌های بزرگ‌تر و پیچیده‌تر پرداخت. در کارهای آتی با توسعه روش پیشنهادی تلاش خواهیم کرد تا چندین شکل از جوامع مانند جوامع همپوشانی، چندنمایه و جاسازی‌شده را در هر دو حالت همگن و ناهمگن شناسایی کنیم.

مراجع

[1]       D. J. Watts and S. H. Strogatz, "Collective dynamics of 'small-worldl networks," Nature, vol. 393, pp. 440-442, 1998.

[2]       A. L. Barabási and R. Albert, "Emergence of scaling in random networks," Science, vol. 286, no. 5439, pp. 509-512, 15 Oct. 1999.

[3]       M. Girvan and M. E. Newman, "Community structure in social and biological networks," Proc. Natl. Acad. Sci., vol. 99, no. 12, pp. 7821-7826, 2002.

[4]       M. E. Newman and M. Girvan, "Finding and evaluating community structure in networks," Phys. Rev. E, vol. 69, no. 2, Article ID: 026113, 2004.

[5]       M. E. Newman, "The structure and function of complex networks," SIAM Rev., vol. 45, no. 2, pp. 167-256, 2003.

[6]       E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A. L. Barabási, "Hierarchical organization of modularity in metabolic networks," Science, vol. 297, no. 5586, pp. 1551-1555, 2002.

[7]       D. M. Wilkinson and B. A. Huberman, "A method for finding communities of related genes," in Proc. Natl. Acad. Sci. vol. 101, suppl 1, pp. 5241-5248, 2004.

[8]       R. Guimera and L. A. N. Amaral, "Functional cartography of complex metabolic networks," Nature vol. 433, no. 7028, pp. 895-900, 2005.

[9]       G. W. Flake, S. Lawrence, C. L. Giles, and F. M. Coetzee, "Self-organization and identification of web communities," Computer, vol. 35, no. 3, pp. 66-70, Mar. 2002.

[10]       Y. Dourisboure, F. Geraci, and M. Pellegrini, "Extraction and classification of dense communities in the web," in Proc. of the 16th Int. Conf. on World Wide Web, pp. 461-470, Banff, Canada, 8-12 May 2007.

[11]       A. Perianes-Rodríguez, C. Olmeda-Gómez, and F. Moya-Anegón, "Detecting, identifying and visualizing research groups in co-authorship networks," Scientometrics, vol. 82, no. 2, pp. 307-319, 2010.

[12]       B. He, Y. Ding, J. Tang, V. Reguramalingam, and J. Bollen, "Mining diversity subgraph in multidisciplinary scientific collaboration networks, a meso perspective," J. Informetrics, vol. 7, no. 1, pp. 117-128, Jan. 2013.

[13]       M. A. Porter, J. P. Onnela, and P. J. Mucha, "Communities in networks," Notices of the American Mathematical Society. vol. 56, no. 9, pp. 1082-1097, 2009.

[14]       S. Fortunato, "Community detection in graphs," Phys. Rep., vol. 486, no. 3-5, pp. 75-174, Feb. 2010.

[15]       M. E. J. Newman, "Communities, modules and large-scale structure in networks," Nature Physics, vol. 8, pp. 25-31, 2012.

[16]       M. Coscia, F. Giannotti, and D. Pedreschi, "A classification for community discovery methods in complex networks," Statistical Analysis and Data Mining, vol. 4, no. 5, pp. 512-546, Oct. 2011.

[17]       Z. Shi, Y. Liu, and J. Liang, "PSO-based community detection in complex networks," in Proc. 2nd Int. Symp. on Knowledge Acquisition and Modeling, KAM'09, vol. 3, pp. 114-119, Wuhan, China, 30 Nov.-1 Dec. 2009.

[18]       M. E. J. Newman, "Detecting community structure in networks," the European Physical J. B-Condensed Matter and Complex Systems, vol. 38, no. 2, pp. 321-330, 2004.

[19]       A. Clauset, M. E. J. Newman, and C. Moore, "Finding community structure in very large networks," Physical Review E, vol. 70, no. 6, Article ID: 066111, 2004.

[20]       C. Shi, Y. Wang, B. Wu, and C. Zhong, "A new genetic algorithm for community detection," Complex Sciences, vol. 535, Article ID: 122259, 2009.

[21]       C. Pizzuti, "GA-Net: a genetic algorithm for community detection in social networks," in Proc. of the 10th Parallel Problem Solving from Nature-PPSN X, pp. 1081-1090, Dortmund, Germany, 13-17 Sept. 2008.

[22]       M. E. J. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical Review E, vol. 74, no. 3, Article ID: 36104, 2006.

 

جدول 10: مقدار پارامتر img0 با تغییر img0 در گراف با 64 نود.

 

الگوریتم

img0 

8

7

6

5

4

3

2

1

0

OSLOM

1

1

1

1

1

1

1

1

1

Louvain

482/0

605/0

605/0

605/0

605/0

1

1

1

1

Local community detection

0

0

0

0

0

0

827/0

827/0

827/0

MST&Modularity

557/0

557/0

557/0

557/0

557/0

557/0

557/0

8357/0

1

MST&MM

1

1

1

1

1

1

1

1

1

 

جدول 11: مقدار پارامتر img0 با تغییر img0 در گراف با 128 نود.

 

الگوریتم

img0 

8

7

6

5

4

3

2

1

0

OSLOM

70/0

70/0

76/0

80/0

80/0

81/0

83/0

1

1

Louvain

52/0

46/0

52/0

46/0

41/0

1

1

1

1

Local community detection

55/0

59/0

65/0

73/0

80/0

78/0

80/0

1

1

MST&Modularity

0

0

0

0

0

55/0

55/0

82/0

1

MST&MM

81/0

81/0

81/0

87/0

87/0

848/0

848/0

1

1

 

 

جدول 12: کارهای مشابه.

 

تکنیک مورد استفاده

الگوریتم

Betweenness centrality

[3] (2002) Girvan and Newman

Nodes similarity

[32] (2004) Donetti, et al.

Density-based link clustering

[33] (2016) iDBLINK

Density-based

[34] (2014) IncOrder-

Structural similarity measure

[35] (2007) SCAN

Parallel Louvain method

[36] (2016) PLMR

Label propagation

[37] (2020) NI-LPA

Label propagation with information entropy

[38] (2017) Naiyue Chen

Partitioning approach

[39] (2016) PMEP

Graph-based label propagation

[40] (2019) GLPA

Label propagation

[41] (2018) PLPAC

Louvain method

[42] (2015) Hao Lu

Modularity optimization

[43] (2020) MOKP

Modularity

[44] (2019) MDSTA

Distance dynamics model

[2018] (45) Tingqin He

 

[23]       J. Reichardt and S. Bornholdt, "Statistical mechanics of community detection," Phys. Rev., vol. E 74, no. 1, Article ID: 016110, 2006.

[24]       U. Brandes, et al., "On finding graph clusterings with maximum modularity," in Proc. of the 33rd Int. Workshop on Graph-Theoretic Concepts in Computer Science, pp. 121-132, Dornburg, Germany, 21-23 Jun. 2007.

[25]       P. J. Bickel and A. Chen, "A nonparametric view of network models and Newman-Girvan and other modularities," Proc. Natl. Acad. Sci., vol. 106, pp. 21068-21073, 15 Dec. 2009.

[26]       V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, "Fast unfolding of communities in large networks," J. Stat. Mech., vol. 2008, Article ID: P10008, Oct. 2008.

[27]       B. Saouda and A. Moussaoui, "Community detection in networks based on minimum spanning tree and modularity," Physica A, vol. 460, pp. 230-234, 15 Oct. 2016.

[28]       D. Lusseau, "The emergent properties of a dolphin social network," in Proc. R. Soc. London. Ser. B: Biol. Sci., Suppl. 2, vol. 270, pp. S86-S188, 7 Nov. 2003.

[29]       J. Eustace, X. Wang, and Y. Cui, "Community detection using local neighborhood in complex networks," Physica A., vol. 436, pp. 665-677, 15 Oct. 2015.

[30]       A. Lancichinetti, F. Radicchi, J. J. Ramasco, and S. Fortunato, "Finding statistically significant communities in networks," PLoS One, vol. 6, no. 4, Article ID: e18961, 2011.

[31]       A. Lancichinetti and S. Fortunato, "Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities," Phys. Rev., vol. E80, no. 1, Article ID: 016118, Jul. 2009.

[32]       F. Meng, et al., "Incremental density-based link clustering algorithm for community detection in dynamic networks," Mathematical Problems in Engineering, vol. 2016, no. 1, Article ID: 1873504, 11 pp., Jan. 2016.

[33]       K. Nath, R. Shanmugam, and V. Varadaranjan, "ma-CODE: a multi-phase approach on community detection in evolving networks," Information Sciences, vol. 569, pp. 326-343, Aug. 2021.

[34]       X. Xu, N. Yuruk, Z. Feng, and T. A. Schweiger, "Scan: a structural clustering algorithm for networks," in Proc. of the 13th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, KDD'07, pp. 824-833, San Jose, CA, USA, 12-15 Aug. 2007.

[35]       I. B. El Kouni, W. Karoui, and L. B. Romdhane, "Node importance based label propagation algorithm for overlapping community detection in networks," Expert Systems with Applications, vol. 162, Article ID: 113020, 30 Dec. 2020.

[36]       N. Chen, Y. Liu, H. Chen, and J. Cheng, "Detecting communities in social networks using label propagation with information entropy," Physica A: Statistical Mechanics and its Applications, vol. 471, pp. 788-798, 1 Apr. 2017.

[37]       G. Yang, W. Zheng, C. Che, and W. Wang, "Graph-based label propagation algorithm for community detection," International J. of Machine Learning and Cybernetics, vol. 11, pp. 1319-1329, 2020.

[38]       B. Saoud and A. Moussaoui, "Community detection in networks based on minimum spanning tree and modularity," Physica A: Statistical Mechanics and its Applications, vol. 460, pp. 230-234, 15 Oct. 2016.

[39]       J. Wu, X. Li, L. Jiao, X. Wang, and B. Sun, "Minimum spanning trees for community detection," Physica A: Statistical Mechanics and its Applications, vol. 392, no. 9, pp. 2265-2277, 1 May 2013.

[40]       J. Zhu, B. Chen, and Y. Zeng, "Community detection based on modularity and k-plexes," Information Sciences, vol. 513, pp. 127-142, Mar. 2020.

[41]       X. Zhou, K. Yang, Y. Xie, C. Yang, and T. Huang, "A novel modularity-based discrete state transition algorithm for community detection in networks," Neurocomputing, vol. 334, pp. 89-99, 21 Mar. 2019.

[42]       J. Xie, M. Chen, and B. K. Szymanski, "LabelrankT: incremental community detection in dynamic networks via label propagation,"
in Proc. of the Workshop on Dynamic Networks Management and Mining, pp. 25-32, New York, NY, USA, 22-27 Jun. 2013.

[43]       H. Shen, X. Cheng, K. Cai, and M. B. Hu, "Detect overlapping and hierarchical community structure in networks," Physica A: Statistical Mechanics and its Applications, vol. 388, no. 8, pp. 1706-1712, 15 Apr. 2009.

[44]       C. L. Staudt and H. Meyerhenke, "Engineering parallel algorithms for community detection in massive networks," IEEE Trans. on Parallel and Distributed Systems, vol. 27, no. 1, pp. 171-184, Jan. 2015.

[45]       K. Nath, S. Roy, and S. Nandi, "InOvIn: a fuzzy-rough approach for detecting overlapping communities with intrinsic structures in evolving networks," Applied Soft Computing, vol. 89, Article ID: 106096, Apr. 2020.

 

سندی بهادری تحصيلات مقاطع كارشناسي و كارشناسي ارشد و دکتری خود در رشته سیستم­های نرم افزاری در سال­هاي 1384 و 1387 و 1397 از دانشگاه بوعلی همدان، و دانشگاه آزاد اسلامی به پايان رسانده است و هم­اكنون استادیار دانشكده مهندسي كامپيوتر دانشگاه آزاد اسلامی واحد ایلام مي‎باشد. زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: تحلیل شبکه­های پیجیده، محاسبات نرم و كاربردهاي آن در توسعه نرم­افزارهای بزرگ.

 

مریم نورائی آباده تحصيلات مقاطع كارشناسي و كارشناسي ارشد و دکتری خود در رشته سیستم­های نرم افزاری در سال­هاي 1384 و 1387 و 1394 از دانشگاه اصفهان، و دانشگاه آزاد اسلامی واحد علوم و تحقیقات به پايان رسانده است و هم­اكنون استادیار دانشكده مهندسي كامپيوتر دانشگاه آزاد اسلامی واحد آبادان مي‎باشد. زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: آزمون نرم­افزار، تحلیل شبکه های پیجیده و ارتقاء توسعه سیستم­های نرم­افزاری با هوش مصنوعی.

 

 

 

 

 

 


Related articles

The rights to this website are owned by the Raimag Press Management System.
Copyright © 2017-2024

Home| Login| About Rimag| Contact Us|
[فارسی] [العربية] [fa] [ar]