رقم المقالة : 1402042543289 زيارة : 845 الصفحة: 100 - 108

نوع المخطوط: المحکّمة

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

الموضوعات :

1 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامي واحد آبادان، ایران
2 - گروه مهندسي كامپيوتر، دانشگاه آزاد اسلامي واحد آبادان، ایران

تاريخ الإرسال : 29 الإثنين , ذو الحجة, 1444 تاريخ التأكيد : 29 الأحد , شعبان, 1445 تاريخ الإصدار : 21 الثلاثاء , ربيع الأول, 1446

الکلمات المفتاحية: شبکه‌های پیچیده, جامعه, درخت پوشای مینیمم, افزایش ماژولاریتی,

ملخص المقالة :

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

المصادر:

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

نص كامل:

معرفي يک روش جديد خوشه‌يابي خودکار

مقاله پژوهشی

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

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

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

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

1- مقدمه

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

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

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

(الف)

(ب)

(ج)

(د)

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

(3)

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

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

(4)

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

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

(5)

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

(الف)

(ب)

[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

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

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

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

3-2-1 فوتبال

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

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

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

[1] . American College Football

[2] . Zachary's Karate Club

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

Network
	1000	20	50	8/0- 1/0	1	2	20	50
	2000	40	100	8/0- 1/0	1	2	40	100

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

الگوریتم
الگوریتم	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: نتیجه مقایسه مقدار پارامتر بر روی گراف‌های با تغییر مقدار پارامتر برای روش پیشنهادی در این مقاله
با روش‌های OSLOM، Louvain، Local community detection و MST&Modularity.

الگوریتم
الگوریتم	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 شبکه کتاب

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

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

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

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

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

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

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

الگوریتم
الگوریتم	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

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

کارایی روش پیشنهادی بر اساس مقدار معیار در مقایسه با روش شناسایی جامعه‌ها با استفاده از همسایگی محلی [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 نود با تغییر درست خوشه‌بندی شده‌اند.

الگوریتم
الگوریتم	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 نود با تغییر درست خوشه‌بندی شده‌اند.

الگوریتم
الگوریتم	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: مقدار پارامتر با تغییر در گراف با 32 نود.

الگوریتم
الگوریتم	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: مقدار پارامتر با تغییر در گراف با 64 نود.

الگوریتم
الگوریتم	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: مقدار پارامتر با تغییر در گراف با 128 نود.

الگوریتم
الگوریتم	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 از دانشگاه اصفهان، و دانشگاه آزاد اسلامی واحد علوم و تحقیقات به پايان رسانده است و هماكنون استادیار دانشكده مهندسي كامپيوتر دانشگاه آزاد اسلامی واحد آبادان مي‎باشد. زمينه‎هاي تحقيقاتي مورد علاقه ايشان عبارتند از: آزمون نرمافزار، تحلیل شبکه های پیجیده و ارتقاء توسعه سیستمهای نرمافزاری با هوش مصنوعی.

شارک

عنوان URL للمقالة

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

رایمگ

الروابط

المراكز ذات الصلة

دعامة

الصفحات الرسمية