Community Detection in Bipartite Networks Using HellRank Centrality Measure
Subject Areas : ICTAli Khosrozadeh 1 , movaghar movaghar 2 , Mohammad Mehdi Gilanian Sadeghi 3 , Hamidreza Mahyar 4
1 - Department of Computer Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
2 -
3 - Department of Computer Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
4 - Department of Computer Engineering, McMaster University, Hamilton, Ontario, Canada
Keywords: Social Networks, Bipartite Graphs, Centrality Measure, Community Detection, Voting,
Abstract :
Community structure is a common and important feature in many complex networks, including bipartite networks. In recent years, community detection has received attention in many fields and many methods have been proposed for this purpose, but the heavy consumption of time in some methods limits their use in large-scale networks. There are methods with lower time complexity, but they are mostly non-deterministic, which greatly reduces their applicability in the real world. The usual approach that is adopted to community detection in bipartite networks is to first construct a unipartite projection of the network and then communities detect in that projection using methods related to unipartite networks, but these projections inherently lose information. In this paper, based on the bipartite modularity measure that quantifies the strength of partitions in bipartite networks and using the HellRank centrality measure, a quick and deterministic method for community detection from bipartite networks directly and without need to projection, proposed. The proposed method is inspired by the voting process in election activities in the social society and simulates it.
[1] M. J. Barber, "Modularity and Community Detection in Bipartite Networks," Physical Review E, vol. 76, 2007.
[2] S. Fortunato, "Community Detection in Graphs," Physics Reports, vol. 486, pp. 75-174, 2002.
[3] M. Newman and M. Girvan, "Finding and Evaluating Community Structure in Networks," Physical Review E, vol. 69, 2004.
[4] R. Guimera and M. Sales-Pardol, "Module Identification in Bipartite and Directed Networks," Physical Review E, vol. 76, 2007.
[5] M. J. Barber, "Detecting Network Communities by Propagating Labels Under Constraints," Physical Review E, vol. 80, 2009.
[6] A. Silva, S. Guimaraes, W. Meira and M. Zaki, "Profilerank: Finding Relevant Content and Influential Users," In Proceedings of the 7th Workshop on Social Network Mining and Analysis, 2013, pp. 1-9.
[7] H. Mahyar, "Detection of Top-k Central Nodes in Social Networks: A Compressive Sensing Approach," IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015, pp. 902-909.
[8] H. Mahyar, H. R. Rabiee, A. Movaghar, E. Ghalebi and A. Nazemian, "Cs-Comdet: A Compressive Sensing Approach for Intercommunity Detection in Social Networks," IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2015, pp. 89-96.
[9] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, and H. E. Stanley, "Identifying Influential Spreaders in Complex Networks," Nature Physics, vol. 6, pp. 888-893, 2010.
[10] S. M. Taheri and H. Mahyar, "Hellrank: A Hellinger-Based Centrality Measure for Bipartite Social Networks," Social Network Analysis and Mining, vol. 7, 2017.
[11] M. Nikulin, Hellinger distance, Encyclopedia of Mathematics, 2001.
[12] M. E. Newman, "Finding Community Structure in Networks Using the Eigenvectors of Matrices," Physical Review E, vol. 74, 2006.
[13] T. Opsahl, "Triadic Closure in Two-Mode Networks: Redefining the Global and Local Clustering Coefficients," Social Networks, vol. 35, pp. 159-167, 2013.
[14] A. Nematzadeh, E. Ferrara, A. Flammini and Y. Y. Ahn, "Optimal Network Modularity for Information Diffusion," Physical Review Letters, vol. 113, 2014.
[15] T. Zhou, M. Zhao, G. Chen, G. Yan and B. H. Wang, "Phase Synchronization on Scale-Free Networks with Community Structure," Physics Letters A, vol. 368, pp. 431-434, 2007.
[16] L. Y. Tang, S. N. Li, J. H. Lin and Q. Guo, "Community Structure Detection Based on the Neighbor Node Degree Information," International Journal of Modern Physics C, vol. 27, 2016.
[17] H. Peng, D. Zhao, L. Li and J. Lu, "An Improved Label Propagation Algorithm Using Average Node Energy in Complex," Physica A: Statistical Mechanics and its Applications, vol. 460, pp. 98-104, 2016.
[18] J. X. Yang and X. D. Zhang, "Finding Overlapping Communities Using Seed Set," Physica A: Statistical Mechanics and its Applications, vol. 467, pp. 96-106, 2017.
[19] S. Bilal and M. Abdelouahab, "Evolutionary Algorithm and Modularity for Detecting Communities in Networks," Physica A: Statistical Mechanics and its Applications, vol. 473, pp. 89-96, 2017.
[20] H. L. Sun, E. Ch’ng, X. Yong, J. M. Garibaldi and S. See, "An Improved Game-Theoretic Approach to Uncover Overlapping Communities," International Journal of Modern Physics C, vol. 28, 2017.
[21] T. S. Evans and R. Lambiotte, "Line Graphs, Link Partitions and Overlapping Communities," Physical Review E, vol. 80, 2009.
[22] V. D. Blondel, J. L. Guillaume, R. Lambiotte and E. Lefebvre, "Fast Unfolding of Communities in Large Networks," Journal of Statistical Mechanics: Theory and Experiment, vol. 10, 2008.
[23] A. Mukherjee, M. Choudhury and N. Ganguly, "Understanding How Both the Partitions of a Bipartite Network Affect its One-Mode Projection," Physica A: Statistical Mechanics and its Applications, vol. 390, pp. 3602-3607, 2011.
[24] X. Wang and X. Qin, "Asymmetric intimacy and algorithm for detecting communities in bipartite networks," Physica A: Statistical Mechanics and its Applications, vol. 462, pp. 569-578, 2016.
[25] M. E. Newman, "Modularity and Community Structure in Networks," In Proceedings of the National Academy of Sciences of USA, 2006, vol. 103, pp. 8577-8582.
[26] S. Fortunato and M. Barthelemy, "Resolution Limit in Community Detection," In Proceedings of the National Academy of Sciences of USA, 2007, vol. 104, pp. 36-41.
[27] S. Lehmann, M. Schwartz and L. K. Hansen, "Biclique Communities," Physical Review E, vol. 78, 2008.
[28] P. Zhang, J. Wang, X. Li, M. Li and Z. Di, "Clustering Coefficient and Community Structure of Bipartite Networks," Physica A: Statistical Mechanics and its Applications, vol. 387, pp. 6869-6875, 2008.
[29] Y. Cui and X. Wang, "Uncovering Overlapping Community Structures by the Key Bi-Community and Intimate Degree in Bipartite Networks," Physica A: Statistical Mechanics and its Applications, vol. 407, pp. 7-14, 2014.
[30] D. B. Larremore and A. Clauset, "Efficiently Inferring Community Structure in Bipartite Networks," Physical Review E, vol. 90, 2014.
[31] Y. Xu, L. Chen, B. Li and W. liu, "Density-Based Modularity for Evaluating Community Structure in Bipartite Networks," Information Sciences, vol. 317, pp. 278-294, 2015.
[32] J. G. Liu, L. Hou, X. Pan, Q. Guo and T. Zhou, "Stability of Similarity Measurements for Bipartite Networks," Nature, vol. 6, 2016.
[33] K. Li and Y. Pang, "A Unified Community Detection Algorithm in Complex Network," Neurocomputing, vol. 130, pp. 36-43, 2014.
[34] H. Liang Sun, E. Ch’ng, X. Yong, J. M. Garibaldi, S. See and D. Bing Chen, "A Fast Community Detection Method in Bipartite Networks by Distance Dynamics," Physica A: Statistical Mechanics and its Applications, vol. 496, pp. 108-120, 2018.
[35] C. Zhou, L. Feng and Q. Zhao, "A Novel Community Detection Method in Bipartite Networks," Physica A: Statistical Mechanics and its Applications, vol. 492, pp. 1679-1693, 2018.
[36] M. J. Barber, M. Faria and L. Streit, "Searching for Communities in Bipartite Networks," AIP Conference Proceedings, 2008, vol. 1021.
[37] H. Taguchi, T. Murata, X. Liu, "BiMPLA: Community Detection in Bipartite Networks by Multi-Label Propagation," In Proceedings of NetSciX 2020: 6th International Winter School and Conference on Network Science, 2020, pp. 17-31.
[38] M. Bouguessa, K. Nouri, "BiNeTClus: Bipartite Network Community Detection Based on Transactional Clustering," ACM Transactions on Intelligent Systems and Technology, vol. 12, pp. 1-26, 2020.
[39] T. C. Yen, D. B. Larremore, "Community Detection in Bipartite Networks with Stochastic Blockmodels," Physical Review E, vol. 102, 2020.
[40] S. Che, W. Yang, W. Wang, "An Improved Artificial Bee Colony Algorithm for Community Detection in Bipartite Networks," IEEE Access, vol. 9, pp. 10025-10040, 2021.
[41] G. Calderer, M. L. Kuijjer, "Community Detection in Large-Scale Bipartite Biological Networks," Frontiers in Genetics, vol. 12, 2021.
[42] G. Wu, C. Gu, H. Yang, "A Spectral Method of Modularity for Community Detection," EPL Journal, vol. 137, 2022.
[43] O. F. Robledo, M. Klepper, E. Boven, H. Wang, "Community Detection for Temporal Weighted Bipartite Networks," In Proceedings of the 11th International Conference on Complex Networks and their Applications, 2023, pp. 245-257.
[44] P. Zhang, "Evaluating Accuracy of Community Detection Using the Relative Normalized Mutual Information," Journal of Statistical Mechanics: Theory and Experiment, vol. 11, 2015.
Journal of Information and
Communication Technology
Volume 16, Issue 59-60, Spring and Summer 2024, pp. 179-194
Community Detection in Bipartite Networks Using HellRank Centrality Measure
Ali Khosrozadeh1, Ali Movaghar21, Mohammad Mehdi Gilanian Sadeghi1, and Hamidreza Mahyar3
1 Department of Computer and Information Technology Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran
2 Department of Computer Engineering, Sharif University of Technology, Tehran, Iran
3 Department of Computer Engineering, McMaster University, Hamilton, Ontario, Canada
Received: 06 April 2023, Revised: 21 April 2023, Accepted: 11 June 2023
Paper type: Research
Abstract
Community structure is a common and important feature in many complex networks, including bipartite networks. In recent years, community detection has received attention in many fields and many methods have been proposed for this purpose, but the heavy consumption of time in some methods limits their use in large-scale networks. There are methods with lower time complexity, but they are mostly non-deterministic, which greatly reduces their applicability in the real world. The usual approach that is adopted to community detection in bipartite networks is to first construct a unipartite projection of the network and then communities detect in that projection using methods related to unipartite networks, but these projections inherently lose information. In this paper, based on the bipartite modularity measure that quantifies the strength of partitions in bipartite networks and using the HellRank centrality measure, a quick and deterministic method for community detection from bipartite networks directly and without need to projection, proposed. The proposed method is inspired by the voting process in election activities in the social society and simulates it.
Keywords: Social Networks, Bipartite Graphs, Centrality Measure, Community Detection, Voting.
شناسائی انجمن در شبکههای دوبخشی با استفاده از معیار مرکزیت هلرنک
علی خسروزاده 1، علی موقر22، محمدمهدی گیلانیان صادقی1، حمیدرضا ماهیار3
1 گروه مهندسي کامپیوتر و فناوری اطلاعات، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران
2 گروه مهندسي کامپیوتر، دانشگاه صنعتی شریف، تهران، ایران
3 گروه مهندسي کامپیوتر، دانشگاه مکمستر، همیلتون، انتاریو، کانادا
تاریخ دریافت: 17/01/1402 تاریخ بازبینی: 01/02/1402 تاریخ پذیرش: 21/03/1402
نوع مقاله: پژوهشی
چکيده
ساختار انجمن ویژگی مشترک و مهمی در بسیاری از شبکههای پیچیده از جمله شبکههای دوبخشی است. شناسائی انجمنها در سالهای اخیر در بسیاری زمینهها مورد توجه قرار گرفته و روشهای زیادی برای این منظور پیشنهاد شده است، اما مصرف سنگین زمان در برخی روشها، استفاده از آنها را در شبکههای بزرگ مقیاس محدود میکند. روشهائی با پیچیدگی کمتر وجود دارند اما اکثراً غیرقطعی هستند که کاربرد آنها در دنیای واقعی را کاهش میدهد. رویکرد معمول اتخاذ شده برای شناسائی انجمنها در شبکههای دوبخشی این است که ابتدا یک طرحریزی یکبخشی از شبکه ساخته شود و سپس انجمنها در آن طرحریزی با استفاده از روشهای مربوط به شبکههای یکبخشی شناسائی شوند. این طرحریزیها به طور ذاتی اطلاعات را از دست میدهند. در این مقاله بر اساس معیار ماژولاریتی دوبخشی که قدرت تقسیمبندیها را در شبکههای دوبخشی محاسبه میکند و با استفاده از معیار مرکزیت هلرنک، روشی سریع و قطعی برای شناسائی انجمنها از شبکههای دوبخشی به طور مستقیم و بینیاز از طرحریزی ارائه گردیده است. روش پیشنهادی از فرآیند رأیگیری در فعالیتهای انتخاباتی در جامعه انسانی الهام گرفته و آن را شبیهسازی میکند. نتایج آزمایشات نشان میدهد، مقدار ماژولاریتی انجمنهای حاصل و دقت شناسائی تعداد آنها در روش پیشنهادی بهبود یافته است.
کلیدواژگان: شبکههای اجتماعی، گرافهای دوبخشی، معیار مرکزیت، شناسائی انجمن، رأیگیری.
[1] * Corresponding Author’s email: movaghar@sharif.edu
[2] * رایانامة نويسنده مسؤول: movaghar@sharif.edu
1- مقدمه
شبکهها، سیستمهای پیچیده مختلفی را در رشتههای گوناگون توصیف میکنند. شبکههای استنباط شده از سیستمهای پیچیده از رأسها و یالهائی تشکیل شدهاند که نشان دهنده موجودیتها و رابطهها هستند. تحقیقات زیادی بر روی شبکههای یکبخشی1 یا یکحالته که تنها شامل یک نوع رأس هستند متمرکز شدهاند. با این حال، شبکههای دنیای واقعی معمولاً شامل چندین نوع رأس هستند که سادهترین حالت آنها، شبکه دوبخشی2 یا دوحالته است و شامل دو نوع رأس مختلف میباشد. یک کلاس خاص و فراگیر از شبکهها، شبکههای دوبخشی هستند که در آن رأسها به دو کلاس مجزا تقسیم شده و یالهای درون شبکههای دوبخشی فقط در بین کلاسهای مختلف رأسها رخ داده و هیچ یالی بین یک نوع از رأسها وجود ندارد [1]. شبکههای دوبخشی مدلهای طبیعی بسیاری از سیستمهای دنیای واقعی میباشند. شبکههای اجتماعی به ساختار اجتماعی بسیار مهمی در جامعه مدرن ما تبدیل شدند و ساختار انجمن3 یک ویژگی رایج بین این شبکههای اجتماعی است که نشان دهنده خوشهبنـدی رأسهای شبکه با یالهای متراکم در داخل گروهها اما یالهای پراکنده بین آنهاست. مفهوم انجمن راه بهتری برای درک ساختارهای ماژولار در شبکههای دوبخشی ارائه میدهد، لذا شناسائی انجمن4 در شبکههای پیچیده میتواند به درک ویژگیهای ساختاری این شبکهها و پیشبینی بیشتر ویژگیهای کاربردی با توجه به ساختار آنها کمک کند. تا کنون روشهای بسیار متنوعی برای شناسائی انجمن در شبکههای دوبخشی معرفی گردید. یک ایده ساده برای شناسائی انجمن این بود که ابتدا شبکههای دوبخشی به معادل یکبخشی خود تبدیل شده و پس از آن روشهای معمول شناسائی انجمن در شبکههای یکبخشی بکار گرفته شود که این ایده همواره با مشکل از دست رفتن اطلاعات در این فرآیند مواجه است. بعد از ارائه مفهوم ماژولاریتی5 دوبخشی که در آن دو بخش مستقل از رأسها به طور مستقل در ساختارهای ماژولار قرار میگیرند، ایده شناسائی انجمنها به صورت مستقیم و بدون نیاز به تبدیل شبکههای دوبخشی به یکبخشی مطرح شد. یکی از ابزارهای مفید برای شناسائی انجمنها استفاده از معیار مرکزیت6 است. معیارهای مرکزیت به شکل گسترده در تجزیه و تحلیل شبکههای اجتماعی و برای تعیین اهمیت نسبی رأسهای شبکه که نقش مهمی در تعیین ساختار انجمنها دارند استفاده میشوند. یکی از این معیــارهای مرکزیت، معیاری دقیق برای شناسائی رأسهای مرکزی در شبکههای دوبخشی به نام معیار هلرنک7 است که مهم ترین مزیت این معیار جهت استفاده از آن در این مقاله، عدم نیاز به تبدیل شبکه دوبخشی مورد بررسی به معادل یکبخشی آن است. برخی روشهای مطرح در زمینه شناسائی انجمنها دارای مشکلاتی شامل عدم قطعیت، مصرف بالای زمان و حافظه، عدم امکان اعمال در شبکههای بزرگ مقیاس و محدودیت تفکیک8 هستند. روش پیشنهادی با استفاده از مفاهیم ماژولاریتی دوبخشی و معیار مرکزیت هلرنک توانسته به طور مستقیم و بدون نیاز به تبدیل به معادل یکبخشی، در شبکههای دوبخشی به ویژه شبکههای دوبخشی بزرگ مقیاس اعمال گردد. نتایج حاصل از پیادهسازی روش پیشنهادی بر روی تعدادی شبکه مصنوعی9 و واقعی10 و مقایسه آنها با دو روش شناخته شده برای شناسائی انجمن در شبکههای دوبخشی این امر را اثبات میکند.
ساختار انجمن
ساختار انجمن نه تنها اتصالهای دانهدرشت11 را در شبکهها آشکار میکند، بلکه نقش مهمی در عملکرد شبکهها ایفا مینماید [2]. شناسائی انجمن، امکان بررسی کمی شبکههای فرعی را فراهم میکند که ممکن است ویژگیهای متفاوتی از ویژگیهای کل شبکه داشته باشند. به طور غیر رسمی یک انجمن شبکه، زیرگرافی است که احتمال اتصال رأسهای آن به یکدیگر بیشتر از رأسهای خارج از زیرگراف است. یکی از ویژگیهای کلیدی اکثر شبکههای دوبخشی، ساختار انجمن است که در آن، شبکهها به گروههائی از رأسها و یالها تقسیم میشوند. انجمن، ساختار ماژولار شبکههای زیرین12 است که در آن یالهائی متراکم بین رأسهای همان گروه و در عین حال یالهائی سست بین گروههای مختلف وجود دارد. شناسائی انجمنها میتواند زیرشبکههای دانهدرشت را از شبکههای زیرین شناسائی کند. از سوی دیگر، انجمنهای مختلف دارای ویژگیهای ساختاری متمایزی هستند، بنابراین ویژگیهای متوسط عمومی13 برای ارائه ویژگیهای ساختارهای انجمن کافی نیست [4]. انجمن همچنین راه بهتری برای درک ساختارهای ماژولار شبکههای دوبخشی ارائه میدهد. دو نوع ایده در رابطه با انجمن دوبخشی وجود دارد که اعضاء از یک نوع یا از نوع متفاوت در یک گروه در نظر گرفته شوند. ساختار انجمن در شبکههای دوبخشی نه تنها میزان اتصال رأسها در یک بخش با رأسهای بخش دیگر را نشان میدهد، بلکه رأسهای مشابه را در همان بخش به گروههائی خوشهبندی میکند. برای شناسائی ساختار انجمن در شبکههای دوبخشی، معیار ماژولاریتی خاصی برای شبکههای دوبخشی توسط آقای باربر [1] پیشنهاد شد و الگوریتمهائی مانندBRIM [1] و LP [5] توسعه یافتند.
معیار مرکزیت
مرکزیترین رأس اغلب رأسهائی هستند که وزن بیشتری هم از نظر تعداد تعامل اجتماعی14 و هم از نظر تعداد یال با دیگر رأسها دارند [6]. در تجزیه و تحلیل شبکههای اجتماعی، چنین مفهوم مرکزیتی برای شناسائی کاربران تأثیرگذار استفاده میشود زیرا تأثیر یک کاربر، توانائی عمومیکردن محتوائی خاص در شبکه است [7]. بدین منظور، معیارهای مرکزیت مختلفی در طول سالها برای رتبهبندی رأسهای شبکه بر اساس ویژگیهای توپولوژیکی و ساختاری آنها پیشنهاد شدهاند. این معیارها را میتوان از چند دیدگاه با مقدار پیچیدگی محاسباتی متفاوت در نظر گرفت، از معیارهای کمهزینه مثل مرکزیت درجه15 تا معیارهای پرهزینه مثل مرکزیت بینابینی16 و نزدیکی17. این معیارهای ساختاری نیازمند داشتن دانش کاملی از توپولوژی شبکه هستند [8]. یک مشاهده جالب این است که بسیاری از شبکههای اجتماعی واقعی ماهیتی دووجهی دارند که اجازه میدهد به عنوان یک گراف دوبخشی مدل شوند. سیستم توصیهکننده اجتماعی18 یکی از سیستمهائی است که میتوان آن را به عنوان یک گراف دوبخشی مدلسازی کرد. در این سیستمها، معیارهای مرکزیت میتواند تفسیر متفاوتی از معیارهای مرکزیت مرسوم مانند بینابینی، نزدیکی، درجه و رتبهصفحه19 داشته باشد [9]. معیارهای بینابینی و نزدیکی، به عنوان رایجترین شناسه رأسهای مرکزی در شبکههای یکبخشی شناخته میشوند، گرچه در شبکههای اجتماعی دوبخشی معمولاً در شناسائی کاربران مرکزی که نماینده کاملی برای ساختار شبکهاند مناسب نیستند. یکی از معیارهای مناسب برای شبکههای اجتماعی دوبخشی که در این مقاله از آن برای شناسائی انجمنها بهره بردیم معیار مرکزیت هلرنک است [10]. معیار هلرنک معیاری است که میتوان از آن در شناسائی انجمنها در شبکههای دوبخشی استفاده کرد بدون اینکه مجبور باشیم ابتدا یک طرحریزی20 یکبخشی از شبکه دوبخشی در اختیار بسازیم. در واقع یکی از دلایل استفاده از این معیار هدف مهمی در روش پیشنهادی است که همان امکان شناسائی انجمنها در شبکههای دوبخشی به صورت مستقیم و بی نیاز از طرحریزی یکبخشی معادل آنهاست.
معیار مرکزیت هلرنک
با مد نظر قرار دادن شاخصهای اهمیت کاربران برای شناسائی رأسهای مرکزی، معیار مرکزیت جدیدی به نام هلرنک معرفی شد [10]. معیار هلرنک، یک معیار مرکزیت دقیق جهت شناسائی رأسهای مرکزی در شبکههای اجتماعی دوبخشی است که بر اساس فاصله هلینگر21 بین دو رأس در یک بخش شبکه دوبخشی تعریف شد [11]. محاسبه این معیار میتواند با اجازه به هر رأس برای استفاده از اطلاعات محلیاش، توزیع شده باشد، پس نیازی به یک موجودیت مرکزی که دانش کاملی از ساختار توپولوژیکی شبکه داشته باشد نیست. فاصله هلینگر یک معیار f-divergence است که بیانگر شباهت ساختاری هر رأس با دیگر رأسهای شبکه است. از اینرو، این معیار مبتنی بر فاصله برای شناسائی رأسهای با بیشترین نمایندگی رفتاری، دقیق است. نشان داده شده که رأس با مرکزیت هلرنک بالا، مرکزیت درجه و بینابینی به نسبت بالاتری دارد. در واقع، با وجود اهداف متفاوت در شناسائی رأسهای مرکزی، یک همبستگی جزئی بین هلرنک و دیگر معیارهای مرسوم وجود دارد. از آنجا که معیارهای شباهت مثل هلرنک معمولاً معکوس معیارهای فاصله هستند، ابتدا معیار فاصله مناسب مثل هلینگر انتخاب و به شبکه دوبخشی اعمال میشود. به شکل تئوری تأثیر معیار فاصله در شبکههای دوبخشی آنالیز و یک ماتریس فاصله روی یک بخش شبکه تولید و امتیاز هلرنک هر رأس با توجه به این ماتریس محاسبه میشود. به عنوان نتیجه، رأسهای با هلرنک بالا رأسهای با بیشترین نمایندگی رفتاری در شبکه اجتماعی دوبخشی هستند. در معیار هلرنک، هدف ارائه معیاری مبتنی بر شباهت برای هر زوج از رأسها در شبکه است، بنابراین، یک معیار فاصله خوش تعریف به عنوان معیار پایه انتخاب میشود.
تعریف 1: یک فضای معیار، یک مجموعه X است که مفهوم تابع فاصله 
بین هر زوج از نقاط 
را دارد. یک معیار فاصله خوش تعریف d روی مجموعه X یک تابع 
است که برای همه 
ها، سه ویژگی برقرار باشد [10]:
· قطعیت مثبت22: 
و 
اگر و تنها اگر 
.
· تقارن23 : 
.
· نامساوی مثلثی24: 
.
تابع فاصله به صورت تفاوت بین توزیع احتمال هر زوج از رأسها و بر اساس تابع f-divergence به شکل زیر تعریف میشود.
تعریف 2: یک f-divergence یک تابع 
است که تفاوت بین دو توزیع احتمال P و Q را اندازهگیری میکند. برای یک تابع محدب f با 
، f-divergence توزیع احتمال Q از P به صورت زیر تعریف میشود، که در آن 
یک فضای نمونه است که مجموعه همه خروجیهای ممکن میباشد [10]:
(1) 
برای دو توزیع احتمال گسسته 
و 
(m طول بردارها)، فاصله هلینگر برابر است با:
(2) 
که آشکارا با قاعده اقلیدسی تفاوت جذر بردارها مرتبط است:
(3) 
اعمال فاصله هلینگر
هدف اعمال فاصله هلینگر به یک بخش شبکه دوبخشی اندازهگیری شباهت رأسهای آن بخش شبکه است. فرض میشود x رأسی در شبکه دوبخشی با همسایگی 
و درجه 
، 
بزرگترین درجه رأس شبکه، 
تعداد همسایههای x با درجه i و بردار 
توزیع نرمالنشده برای همه همسایه های مجاور x باشد. فاصله هلینگر بین دو رأس x و y در یک بخش شبکه دوبخشی به صورت زیر تعریف میشود که تابع تفاوت بین دو توزیع احتمال 
و 
را نشان میدهد:
(4) 
پیشبینی رتبه با هلرنک
بعد از یافتن فاصلههای هلینگر بین هر زوج رأس در هر بخش شبکه دوبخشی، ماتریس فاصله 
تولید میشود که 
تعداد رأسها در آن بخش شبکه است. با توجه به ویژگیهای معیار خوشتعریف و قابلیت نگاشت به فضای اقلیدسی، میتوان رأسها را بر اساس فاصلههای آنها خوشهبندی کرد. یعنی هر زوج از رأسهای با فاصله کمتر میتواند به وسیله شعاع همسایگی خاصی در یک خوشه25 قرار گیرد. با میانگینگیری معکوس درایههای هر سطر در ماتریس، امتیاز شباهت نهائی هلرنک برای هر رأس x در یک بخش از شبکه (با مجموعه رأسهای 
) به صورت زیر به دست میآید:
(5) 
فرض میشود 
، مقدار نرمال شده هلرنک رأس x به صورت زیر به دست آید که علامت . نشان دهنده ضرب و 
حداقل ممکن هلرنک برای آن است:
(6) 
یک معیار شباهت، مقادیر کوچک را برای رأسهای نامشابه و مقادیر بزرگ را برای رأسهای مشابه میگیرد. رأسهای یک بخش از شبکه با امتیازات شباهت بالاتر، نشان دهنده بیشترین نمایندگی رفتاری آن بخش شبکه هستند، یعنی این رأسها بیشتر از دیگر رأسها به آن بخش شباهت دارند. معیار هلرنک در واقع شباهت ساختاری هر رأس به دیگر رأسهای شبکه را بیان میکند. بنابراین مرتبسازی رأسها بر اساس این معیار یک پیشبینی رتبه بهتر برای رأسهاست. رأسهای با امتیاز هلرنک بالا بیشتر شبیه دیگر رأسها بوده و رأسهای با امتیاز کمتر برای شناسائی رأسهائی که احتمالاً بسیار متفاوت از دیگر رأسها هستند، بکار میروند.
ماژولاریتی
معیار ماژولاریتی آقای نیومن [3]، گسترهای را نسبت به یک شبکه مدل تهی26 نشان میدهد که یالها به جای بین انجمنها در داخل انجمنها شکل میگیرند. با استفاده از این ماژولاریتی، میتوان کیفیت تخصیص رأسها به انجمنها را ارزیابی کرد. به حداکثر رساندن دقیق ماژولاریتی یک مشکل حل نشدنی است. برای یافتن تقسیمبندیهای27 دارای ماژولاریتی بالا از رأسها، الگوریتمهائی معرفی شد. نظر به وابستگی صریح ماژولاریتی به یک مدل تهی، واضح است که انتخاب خاص مدل تهی تأثیر عمیقی بر ماژولاریتی دارد. به نظر میرسد، تا کنون تنها یک مدل تهی به طور مفصل مورد بررسی قرار گرفت، یعنی شبکههائی با یالهائی که به طور تصادفی تخصیص داده شدهاند به طوری که درجههای مورد انتظار رأسهای شبکه مدل برابر با درجههای واقعی رأسهای شبکه واقعی متناظر است [12]. رویکرد معمول برای شناسائی انجمن در شبکههای دوبخشی، این است که ابتدا یک طرحریزی یکبخشی از یک بخش شبکه ساخته و سپس انجمنها در آن طرحریزی با استفاده از روشهای موجود برای شبکههای یکبخشی شناسائی شوند. این طرحریزی یکبخشی میتواند روشنکننده باشد، اما به طور ذاتی اطلاعات را از دست میدهد. نشان داده شده که تجزیه و تحلیل یک طرحریزی بدونوزن و یکبخشی میتواند نتایج غیرقابل اعتماد یا نادرستی ارائه دهد [4].
ماژولاریتی در شبکههای دوبخشی
برای شناسائی ساختار انجمن در شبکههای دوبخشی، باربر [1] تعریف خاصی از ماژولاریتی در این شبکهها را برای ارزیابی همزمان درستی تقسیمبندی هر دو نوع رأسهای داخل انجمنها پیشنهاد داد. انجمنها بوسیله بهینهسازی این تعریف از ماژولاریتی شناسائی میشوند. محدودیتهای خاصی باید در تعریف ماژولاریتی دوبخشی در نظر گرفته شود، به عنوان مثال رأسهای از یک نوع اجازه ندارند به هم متصل شوند. باربر مدل تهی را بر اساس ماتریس مجاورت دوبخشی یک شبکه تعریف کرد. گراف دوبخشی H گرافی است که در آن مجموعه رأسها به دو زیرمجموعه مجزای X و Y تقسیم شده به طوری که هر یال تنها اجازه دارد یک رأس در X را به رأسی در Y متصل کند.
رأسها با دو رنگ قرمز و آبی که نشان دهنده مجموعههائی است که متعلق به آن هستند از هم جدا میشوند. اگر فرض شود گراف H از p و q رأس قرمز و آبی تشکیل شده، ماتریس مجاورت H با ابعاد 
به شکل زیر نمایش داده میشود:
(7) 
که O یک بلوک ماتریسی با درایههای همه صفر را نشان میدهد و بلوک ماتریسی B به عنوان ماتریس مجاورت دوبخشی، نشان دهنده یالهای بین رأسهای قرمز و آبی است. این یک ماتریس 
است که به شکل 
تعریف میشود و 
برابر با 1 است اگر یک یال، رأسهای 
و 
را به هم متصل کند و گرنه برابر صفر است. ماتریس B دربرگیرنده اطلاعات یالها در یک شبکه دوبخشی است. از 
و 
به ترتیب برای نشان دادن درجه رأسهای و استفاده میشود. بدیهی است که 
. ماژولاریتی دوبخشی یک تقسیم28 به صورت زیر تعریف میشود:
(8) 
که 
درجه رأس قرمز i-ام، 
درجه رأس آبی j-ام و 
و 
انجمنهائی هستند که i و j به آنها اختصاص دارند. مقدار m تعداد یالها و تابع 
اگر 
برابر با 1 وگرنه برابر است با صفر. این تعریف برای شبکه دوبخشی منطقی است چون مانع از یال بین رأسهای همرنگ میشود. افزایش ماژولاریتی29 دوبخشی، وقتی یک رأس ایزوله i به انجمن c منتقل میشود، طبق رابطه 9 (بازنویسی رابطه 8) محاسبه میگردد. افزایش حاصل از انتقال یک رأس آبی میتواند به همین شکل به دست آید.
(9) 
که مقادیر
، 
و 
به ترتیب نشان دهنده تعداد کل یالها و جمع درجههای همه رأسهای قرمز و آبی درون انجمن c هستند. اگر یک رأس ایزوله قرمز i و یک انجمن c به صورت یک انجمن تنها در نظر گرفته شوند، ماژولاریتی ترکیبی برابر است با:
(10) 
که 
تعداد یالهای بین رأس قرمز i و همه رأسهای آبی انجمن c است. ماژولاریتی انجمن جزئی متشکل از رأس قرمز تنهای i برابر است با صفر، چون هر دو مقدار و صفر هستند. لذا، ماژولاریتی وقتی c و i جدا از هم هستند برابر است با:
(11) 
از اینرو 
به صورت زیر به دست میآید:
(12) 
شکل 1. نمونهای از یک گراف دوبخشی با دو مجموعه رأس مجزا
ضریب خوشهبندی در شبکههای دوبخشی
این معیار، گرایش رأسها برای تشکیل خوشه را نشان میدهد. در بسیاری از شبکههای دنیای واقعی، رأسها متمایلاند در انجمنهای متراکم خوشهبندی شوند. معیارهای زیادی برای آزمودن این گرایش پیشنهاد شدهاند. آقای اوپسال، فاکتور 
را به عنوان ضریب خوشهبندی رأس i، به صورت زیر تعریف کرد [13]:
(13) 
که 
تعداد 4-مسیرهای30 متمرکز بر رأس کانونی i و 
زیرمجموعهای از این مقدار است به طوری که ابتدا و انتهای مسیر، رأسی را به اشتراک دارند که بخشی از 4-مسیر نیست و بخشی از حداقل یک 6-دور31 است، به عبارتی، تعدادی از این 4-مسیرهاست که وقتی به صورت بخشی از حداقل یک 6-دور یعنی حلقهای از شش یال با پنج رأس باشند، بسته میشوند. این ضریب دو ویژگی دارد. اول، مقدار آن اگر صورت و مخرج کسر اعداد مثبت باشند و صورت کسر زیرمجموعه ای از مخرج کسر باشد، بین صفر تا 1 متغیر است. دوم، در یک شبکه کاملاً متصل این مقدار برابر با 1 است زیرا همه 4-مسیرها بسته هستند.
پیشینه تحقیق
ساختار انجمن ویژگی ساختاری مهمی در بسیاری از شبکههای پیچیده است که در آن انجمنها همیشه با ماژولهای کاربردی در سیستمهای دنیای واقعی مرتبط هستند. وجود ساختارهای انجمن در شبکهها میتواند تأثیر قابلتوجهی بر فرآیندهای پویائی مانند پراکندگی اطلاعات32 [14] و همگامسازی33 [15] داشته باشد. بنابراین، شناسائی انجمن توجه زیادی به خود جلب و روشهای شناسائی زیادی پیشنهاد شد، شامل روشهای شناسائی انجمنها با مفروضات مختلف مثل تجزیه ماتریس غیرمنفی34 [16]، انتشار برچسب35 [17]، گسترش مجموعههای بذر36 [18]، روش تکاملی37 [19]، رویکردهای نظریهبازی38 [20]، گرافهای خطی39 [21] و بهینهسازی ماژولاریتی40 [22]. یک ایده ساده، یک روش طرحریزی است که در آن شبکههای دوبخشی به شبکههای یکبخشی تبدیل شده و پس از آن میتوان روشهای شناسائی انجمن در شبکههای یکبخشی را به طور طبیعی به کار برد [23]. با این حال، استدلال شده که روشهای طرحریزی ممکن است به مشکل اطلاعات ناقص منجر شوند زیرا تنها یک نوع از رأسها اعمال شده و نوع دیگر آنها پس از طرحریزی از بین میرود [24]. بنابراین روشهای مختلفی برای حفظ دو نوع رأس پس از تقسیمبندی انجمنها معرفی گردید. باربر ابتدا یک ماژولاریتی دوبخشی را پیشنهاد داد [1] که از ماژولاریتی یکبخشی [25] گسترش مییابد و سپس الگوریتم BRIM را برای القای دوبخش مستقل از رأسها به ساختارهای ماژولار توسعه داد. با این حال، ماژولاریتی شبکههای دوبخشی دارای محدودیتهائی در مسئله تفکیک [26] است زیرا نمیتوان انجمنهای کوچک را با امتیاز ماژولاریتی بالا به دقت شناسائی کرد. برای شناسائی انجمن دو-دسته41 بر اساس توسعه الگوریتم شناسائی انجمن k-دسته روشی ارائه شد که تمام مزایای الگوریتم k-دسته را دارد و سطحی از انعطافپذیری را با ترکیب آستانههای دسته مستقل فراهم میکند [27]. روشهای دیگری با مفروضات متمایز نیز پیشنهاد شد، مانند بردارهای ویژه ماتریسها42 [12]، بهینهسازی ماژولاریتی [4]، ضریب خوشهبندی [28]، درجه صمیمیت43 [29]، مدل بلوک تصادفی44 [30]، ماژولاریتی مبتنی بر چگالی45 [31] و صمیمیت نامتقارن46 [24]. یک روش یکپارچه شناسائی انجمن مبتنی بر احتمال تشابه رأس47 [32] برای مقابله با شبکههای یکبخشی و دوبخشی با هم پیشنهاد گردید [33]. همانطورکه اندازه شبکه به سرعت افزایش مییابد، ایجاد تعادل بین دقت و عملکرد در عمل مهم بوده است. روشهای کنونی، جز در شبکههای یکبخشی، به شناسائی انجمن در شبکههای دوبخشی بزرگ با صدها هزار رأس و یال توجه چندانی نکردهاند. روشهای دقیق و کارآمدی برای شناسائی انجمن در شبکههای یکبخشی بزرگ با استفاده از شباهت رأس پیشنهاد شد [32]. با این حال، روشهای بیشتری برای مقابله موثر با شبکههای دوبخشی بزرگ مورد نیاز است. یکی از دلایل احتمالی این وضع، حداقل پیچیدگی زمانی از درجه دوم است که باعث میشود ساعتها طول بکشد تا با شبکههای دوبخشی بزرگ سروکار داشته باشیم و مشکل محدودیت تفکیک نیز وجود دارد که منجر به شناسائی نادرست انجمنهای کوچک میشود [26].
الگوریتم BiAttractor [34]، روشی برای شناسائی انجمنهای دوحالته در شبکههای دوبخشی بزرگ با استفاده از دینامیک فاصله48 است که در آن از تعاملهای جامعه انسانی الهام گرفته شده، به طوری که تعاملهای بیشتر در همان انجمن و تعاملهای کمتر بین انجمنهای متفاوت وجود دارد. این روش در شبکههای پراکنده پیچیدگی 
دارد و تقسیمبندی دقیقی از انجمنها به دست میآورد. یک تقسیمبندی خوب مقادیری بهینه یا نزدیک به بهینه برخی معیارها را تولید و سازماندهی سلسلهمراتبی ساختار انجمن را در وضوحهای مختلف نشان میدهد. تقسیمبندی گراف و الگوریتمهای خوشهبندی سلسلهمراتبی49 مثل الگوریتم تجمعی50، بطور سنتی برای حل مشکل شناسائی انجمن پیاده سازی میشوند. از وقتی نیومن تعریف ماژولاریتی را ارائه کرد [3]، به سرعت به معیاری محبوب که کیفیت تقسیمبندی را اندازه میگیرد تبدیل شد. ماژولاریتی نسبت یالهای تشکیل شده در انجمنها به یالهای تشکیل شده بین انجمنهاست. نیومن یک مدل تهی تعریف کرد که درجه رأسها را حفظ تا تصادفی بودن یالهای تشکیل شده بین رأسها را اندازهگیری کند. از آنجا که ماژولاریتی بالا نشان از تقسیمبندی خوب است، حداکثررسانی این معیار با تکنیکهای بهینهسازی موضوعی محبوب است. با این حال، یافتن راه حل بهینه دقیق برای این مشکل، غیرقابل حل است، لذا الگوریتمهای تقریبی زیادی توسعه یافتند. رویکرد حریصانهای به نام Louvain، یکی از کارآمدترین این الگوریتمها با عملکردی عالی است [22]. الگوریتم BiLouvain نیز روش دو مرحلهای شناسائی ساختار انجمن در شبکههای دوبخشی است [35] که در آن الگوریتم Louvain به شبکههای دوبخشی گسترش داده شد. این الگوریتم در شبکههای دوبخشی یک ساختار شبکه متعادل با تعداد مساوی از دو نوع رأس تولید و سپس برای شبکه متعادل حاصل از الگوریتم اول، از یک روش خوشهبندی تجمعی برای خوشهبندی بیشتر استفاده میکند.
در شبکههای دوبخشی، دو راه برای شناسائی انجمنها وجود دارد، انجمنهای متناظر51 یک به یک و انجمنهای متناظر چند به چند. دومی به طور طبیعی ساختارهای خوشهای را در شبکه دوبخشی نشان میدهد. با این حال، روشهای کمی، شناسائی انجمنهای متناظر چند به چند را هدف قرار دادهاند. در مرجع [37] یک الگوریتم انتشار چند برچسبی به نام BiMLPA برای این منظور پیشنهاد شد که از دو نوع انتشار برچسب Multi-Multi LP و Multi-Single LP تشکیل شده است. الگوریتم BiMLPA بر مسئله ناپایدار LPA و محدودیتهای رویکردهای قبلی غلبه می کند و چندین ویژگی مطلوب مانند سرعت و پایداری را داراست. نتایج تجربی نشان میدهد که BiMLPA از رویکردهای قبلی مانند LPAb+، biSBM و ComSim بهتر عمل میکند.
اکثر رویکردهای شناسائی انجمن پیشنهادی برای شبکههای دوبخشی از محدودیتهائی رنج میبرند، مانند شناسائی انجمنها در حضور بسیاری رأسهای غیرمتمایز با یالهای غیرمعمول که ساختارهای انجمن را پنهان میکنند، از دست دادن اطلاعات توپولوژیکی مرتبط به دلیل تبدیل شبکه دوبخشی به گرافهای ساده استاندارد و تعیین دستی چندین پارامتر ورودی از جمله تعداد انجمنهائی که باید شناسائی شوند. برای کاهش این مشکلات، در مرجع [38] یک الگوریتم شناسائی انجمن بدون پارامتر در شبکههای دوبخشی به نام BiNeTClus پیشنهاد شد که در دو فاز عمل میکند. فاز اول بر شناسائی یک گروهبندی اولیه از رأسها از طریق یک مدل داده تراکنشی که قادر به مقابله با وضعیتی است که شبکههائی با بسیاری از یالهای غیر معمول را در بر میگیرد، تمرکز دارد. هدف فاز دوم، پالایش نتایج خوشهبندی فاز اول از طریق یک استراتژی بهینهسازی ماژولاریتی دوبخشی برای شناسائی ساختار انجمن نهائی است. در شبکههای دوبخشی، ساختارهای انجمن محدود به ناسازگاریاند، زیرا رأسهای از یک نوع بر اساس الگوهای مشترک اتصال با رأسهای نوع دیگر گروهبندی شده و این امر باعث میشود که مدل بلوک تصادفی که مدل تولیدی بسیار انعطافپذیری برای شبکههای با ساختار بلوک است، انتخابی شهودی برای شناسائی انجمن دوبخشی باشد. با این حال، فرمولهای معمولی مدل بلوک تصادفی از ساختار ویژه شبکههای دوبخشی استفاده نمیکنـنــد. در مرجع [39] یک فرمول ناپارامتریک بیزین52 از مدل بلوک تصادفی و یک الگوریتم متناظر برای شناسائی موثر انجمنها در شبکههای دوبخشی معرفی شد. BiSBM، نتایج شناسائی انجمن را نسبت به SBMهای عمومی هنگامی که دادهها نویز دارند و نیز محدودیت تفکیک مدل را بهبود داده و درک ما از چشم انداز بهینهسازی پیچیده مرتبط با وظایف شناسائی انجمن را گسترش میدهد. یک مقایسه مستقیم بین توزیعهای قبلی در BiSBM و یک SBM سلسلهمراتبی با وضوح بالا، یک ساختار غیرشهودی از مشکلات شناسائی انجمن را نشان میدهد که توسط شبکههای کوچکتر و پراکندهتر پر شده و در آن مدلهای غیر سلسلهمراتبی بهتر از همتای انعطافپذیرتر خود عمل میکنند. در مرجع [40]، الگوریتم کلونی زنبور مصنوعی53 بهبودیافته IABC-BN پیشنهاد شد که برای شناسائی انجمن در شبکه دوبخشی استفاده میشود. در مرحله اول، یک فرآیند اولیهسازی جمعیت54 جدید از روش کلونی زنبور مصنوعی برای شناسائی خوشه در گراف دوبخشی پیشنهاد شد. در مرحله دوم یعنی مرحله جستجوی زنبور شاغل55، یک معادله جستجوی ترکیبی جدید پیشنهاد گردید. در مرحله سوم یعنی مرحله زنبورهای تماشاگر56، معادله جستجوی ترکیبی جدید دیگری پیشنهاد شد. در مرحله چهارم یعنی مرحله زنبور پیشاهنگ57، یک آستانه احتمال برای افزایش توانایی اکتشاف و بهبود تنوع جمعیتی الگوریتم معرفی گردید. طبق دانش نویسنده، IABC-BN اولین روش کلونی زنبور مصنوعی برای شناسائی خوشه در گرافهای دوبخشی است.
شناسائی ساختار انجمن بهویژه در تحلیل شبکههای بیولوژیکی بزرگ مقیاس با ماهیت دوبخشی، مانند آنهائی که نشاندهنده فعل و انفعالات نظارتی58، دارو-ژن59، یا ارتباط ژن-بیماری60 هستند، مفید است. انجمنهای شناسائی شده در شبکههای بیولوژیکی برای فرآیندهای بیولوژیکی خاص غنی میشوند، بنابراین به فرد اجازه میدهند داروها، مولکولهای تنظیم کننده یا بیماریها را به چنین فرآیندهائی اختصاص دهد. در مرجع [41] یک مبنای نظری از روشهای مختلفی که میتوانند برای شناسائی انجمن در شبکههای بیولوژیکی دوبخشی استفاده شوند، ارائه شد. چندین استراتژی شناسائی انجمنها و نقاط قوت و ضعف آنها در زمینه کاربردشان در شبکههای دوبخشی ژنومی61 مورد بررسی قرار گرفته و سپس آنها را در یک شبکه تعامل دارو-ژن گسترده ژنومی به کار میبرند. امتیاز +Murata همهکاره است و انجمنهای شناسائی شده توسط این روش به ساختار دوبخشی شبکه احترام میگذارند. با این حال، تنها روشی که آن را پیادهسازی میکند BiLouvain بوده که اجرای آن در شبکههای گسترده ژنومی بسیار کند است. بنابراین روشی که از یک بهینهساز طیفی مانند BRIM برای به حداکثر رساندن امتیاز +Murata استفاده میکند، بسیار مفید خواهد بود. دو روش پرکاربرد شناسائی ساختار انجمن در شبکههای دوبخشی، روش ماژولاریتی و روش پارتیشنبندی گراف است. نتایج تحلیلی مرجع [42] نشان میدهد که مسئله حداکثررسانی ماژولاریتی را میتوان پس از رفع محدودیتهای گسستگی62، به عنوان یک مسئله طیفی دوباره فرمولبندی کرد. این یعنی روش ماژولاریتی و روش پارتیشنبندی گراف اساساً معادل هستند. در اینجا، ماژولاریتی دوبخشی بابر تحلیل و مشخص شد که حداکثررسانی ماژولاریتی دوبخشی بابر را میتوان با رفع محدودیتهای گسستگی به عنوان یک مسئله طیفی دوباره فرمولبندی کرد. همچنین، یک الگوریتم طیفی ماژولاریتی برای شناسائی ساختارهای انجمن در شبکههای دوبخشی طراحی شد و نتایج نشان داد این الگوریتم طیفی بهتر از الگوریتمهای حداکثررسانی محلی ماژولاریتی مثل BRIM و BLP عمل میکند. بهطور کلی، الگوریتم بهینهسازی عمومی بهتر از الگوریتم بهینهسازی محلی است. با این حال، بیشتر الگوریتمهای فعلی حداکثررسانی ماژولاریتی دوبخشی به صورت محلی اختصاص داده شدهاند و تعداد کمی، خوشهبندی طیفی را مطالعه میکنند. شناسائی انجمن در شبکههای دوبخشی زمانی (در حال تکامل) چالش برانگیز است زیرا میتوان آن را یا بر روی شبکه دوبخشی زمانی انجام داد یا روی شبکههای مختلف طرحریزیشده و از طریق الگوریتمهای شناسائی انجمن متنوع. سه روش پیشنهادی در مرجع [43]، ساختارهای انجمن مشهود را شناسائی میکنند. تحلیل شبکههای ارزیابی سه روش، شباهت و تفاوت بین آنها در شناسائی زوج رأسهای مشترک یا گروههائی از رأسها که اغلب متعلق به یک انجمن هستند را آشکار میکند. دو روشی مبتنی بر شبکه طرحریزیشده یکسان، ساختارهای انجمن منسجم را شناسائی کرده، در حالی که روش مبتنی بر شبکه دوبخشی اولیه زمانی این دیدگاه از ساختار انجمن را تکمیل میکند. در واقع دو روشی که شبکه را بر اساس طرحریزی زمانی یکسان تقسیم کردند به ترتیب با استفاده از Louvain و Louvain تثبیتشده، ساختارهای انجمن منسجم را شناسائی کرده، در حالی که روش سوم، بر اساس شبکه دوبخشی زمانی اولیه، چشمانداز مکملی از ساختار انجمن ارائه میدهد.
2- روش پیشنهادی
استخراج سریع، قطعی63 و با کیفیت ساختار انجمن از شبکهها مشکلی چالشی است. در این مقاله، یک روش شناسائی انجمن پیشنهاد شده که روشی سریع و قطعی است و میتواند ساختارهای انجمن با کیفیت و قطعی را آشکار کند. روش پیشنهادی از فرآیند رأیگیری در فعالیتهای انتخاباتی یک جامعه انسانی الهام گرفته، طوری که هر رأس بر اساس قوانین رأیگیری، به نامزدهای معرفی شده رأی داده و گروههای رأس به هم متصل میتوانند به سرعت در مورد نامزدهای خود به اجماع برسند. در پایان رویه، نامزدها و رأیدهندگان، گروهی از خوشهها را تشکیل و سپس این خوشهها به عنوان انجمنهای اولیه در نظر گرفته شده و برخی از آنها برای به دست آوردن ساختار انجمن نهائی، در قالب انجمنهای بزرگتر با کارائی بالا تجمیع میشوند. تحلیل ساختارهای انجمن استخراجی از بسیاری شبکهها نشان میدهد هر رأس و بیشتر همسایههای آن همیشه به یک انجمن تعلق دارند و آن رأس و همسایههای در یک انجمن یک خوشه کوچک را تشکیل و هر انجمن از چندین خوشه کوچک تشکیل شده است. در هر خوشه همیشه رأسی وجود دارد که درجه به نسبت بزرگتری از دیگران دارد و خوشه گروهی از رأسهاست که با آن رأس با درجه بزرگتر مرتبطند. این پدیده مشابه فرآیند رأیگیری در جامعه انسانی است. در شبکههای اجتماعی، همیشه افرادی با نفوذ در حوزه محلی وجود دارند که اگر در انتخاباتی با امکان نامزدی آزادانه شرکت کنند، هر رأی دهنده به فردی که نفوذ بیشتری در اطرافش دارد رأی میدهد. این روش منجر به ایجاد خوشههای کوچک زیادی شده که یک گروه رأس است و رأس تأثیرگذار را با دیگران احاطه میکند. بر اساس این واقعیتها، روشی جهت شبیهسازی فرآیند رأیگیری برای شناسائی ساختارهای انجمن پیشنهاد شد که در آن اصولی به عنوان قوانین رأیگیری فرض شده، از درجه برای انعکاس تأثیر هر رأس و از شباهت بین رأسها برای نشان دادن نزدیکی آنها استفاده شد. هر رأس به یکی از همسایههای خود رأی میدهد که درجه آن بزرگتر است. اگر بیش از یک رأس با درجه بزرگتر وجود دارد که تأثیر یکسانی بین همسایهها داشته باشد، رأس رأی دهنده به رأسی رأی میدهد که بیشترین شباهت را با آن دارد. بررسی شباهت بین رأسها با معیار مرکزیت هلرنک صورت میگیرد. به این ترتیب، هر رأس به سرعت رأی داده و در پایان فرآیند رأیگیری، خوشههای شامل رأس کوچک زیادی به دست میآید. طبق این تحلیل، هر انجمن از چند خوشه تشکیل شده و ما خوشهها را به عنوان انجمنهای اولیه در نظر گرفته و برخی از آنها را ادغام میکنیم تا در نهایت ساختار انجمن نهائی را بسازیم. روند کلی مراحل مختلف روش پیشنهادی در شکل 2 نشان داده شده است.
قوانین رأیگیری
گراف مورد استفاده در روش پیشنهادی گراف دوبخشی، بدونجهت و بدونوزن است و میتوان آن را به صورت 
نشان داد که در آن U و I دو مجموعه از انواع مختلف رأس را نشان داده و یال 
انواع مختلف رأسها را به هم متصل میکند. هیچ یالی بین رأسهای از همان مجموعه U یا I وجود ندارد. روش پیشنهادی، انجمنها را با شبیهسازی فرآیند رأیگیری در انتخاباتی که اجازه نامزدی آزادانه را میدهد شناسائی میکند. قوانین رأیگیری برای رویه شناسائی اهمیت زیادی دارد. رأس 
طبق قوانین زیر رأی میدهد:
1. اگر رأس u به عنوان کاندیدا نامزد شود یا رأس u بین همسایههای مرتبه دوم خود بزرگترین درجه را داشته باشد، آنگاه به خودش رأی میدهد.
2. وگرنه، رأسی از همسایههای مرتبه دوم رأس u که درجه آن بزرگتر از درجه رأس u باشد انتخاب و به عنوان رأس v در نظر گرفته میشود. اگر بیشتر از یک رأس از این رأسها وجود داشته باشد، آن رأسی که بیشترین شباهت را با رأس u دارد انتخاب و به عنوان رأس v در نظر گرفته میشود. شباهت بین رأسهای u و v به صورت 
تعریف میشود. اگر 
باشد، رأس u خود را به عنوان کاندیدا نامزد کرده و به خودش رأی میدهد.
3. وگرنه، اگر رأس v به رأسهای دیگر رأی نداده باشد، رأس u رأس v را به عنوان کاندیدا نامزد کرده و به آن رأی میدهد.
4. اگر رأس v به رأس دیگری مثل رأس w رأی داده باشد، این بدان معناست که رأس v از حق خود برای نامزد شدن به عنوان یک کاندیدا دست برداشته و در نتیجه رأس u به رأسw رأی میدهد.
طبق این قوانین رأیگیری، ترتیب رأیگیری رأسها میتواند بر ترتیب رأسهای معرفی شده به عنوان نامزد تأثیر داشته باشد، به طوری که ترتیبهای مختلف رأیگیری ممکن است منجر به نتایج متفاوتی شود.
مراحل کار
در گام اول، ضریب خوشهبندی برای هر رأس مجموعه U در شبکه دوبخشی محاسبه شده و رأسها به ترتیب صعودی ضرایب خوشهبندی آنها رأی میدهند. برای هر رأس 
، ضریب خوشهبندی به صورت زیر محاسبه میگردد:
(14) 
برای رأس x، هرچه تعداد یالهای بین همسایههای آن بیشتر باشد، ضریب خوشهبندی آن بزرگتر است. اگر زیرگراف متشکل از همسایههای مرتبه دوم رأس x، گرافی کامل باشد، 
به حداکثرش یعنی 1 میرسد. با این حال، بعید است زیرگراف همسایگی برای هر رأس در یک شبکه پراکنده، گرافی کامل باشد، به خصوص برای رأسهای با درجه بزرگتر. به عبارتی، ضریب خوشهبندی برای یک رأس با درجههای بزرگتر همیشه کوچک است. بنابراین، رأی دادن به ترتیب صعودی ضریب خوشهبندی میتواند رأسهای با درجه بزرگتر را زودتر به عنوان کاندیدا معرفی کرده و آنها را با همسایههای خود احاطه کند تا خوشهها را بسازند. در کنار محاسبه ضریب خوشهبندی رأس ، فاصله هلینگر این رأس تا تمامی رأسهای دیگر از روی ماتریس هلینگر جهت محاسبه مقدار مرکزیت هلرنک آن به دست میآید. در گام دوم و در یک حلقه تکرار با تعداد رأسها، رأس u با کمترین ضریب خوشهبندی که احتمالاً درجه بالائی دارد انتخاب و مجموعه همسایههای مرتبه دوم با درجه بزرگتر از آن به دست میآید. اگر این مجموعه تهی باشد، رأس u به عنوان کاندیدا نامزد شده، به خودش رأی داده و اولین خوشه را تشکیل و اگر در همسایههای مرتبه دوم رأس u چند رأس وجود داشته باشد که درجه آنها بزرگتر از رأس u است، از شباهت بین آنها و رأس u استفاده شده تا مشخص شود رأس u باید به کدامیک رأی دهد. شباهت بین رأسها نقش مهمی در روند رأیگیری دارد. شباهت بین رأسهای u و v بر اساس مرکزیت هلرنک به صورت زیر محاسبه میشود:
(15) 
رأس v با بالاترین شباهت انتخاب میشود، اگر این شباهت مقدار صفر داشته باشد، رأس u به عنوان کاندیدا نامزد شده، به خودش رأی داده و خوشهای را تشکیل میدهد. اگر مقدار این شباهت بالاتر از صفر باشد، وضعیت رأیدهی رأس v تعیین کننده است. اگر رأس v به رأس دیگری رأی نداده باشد، رأس u، رأس v را به عنوان کاندیدا نامزد کرده و به آن رأی میدهد. در اینجا رأس v خوشهای را تشکیل داده و رأس u به آن خوشه اضافه میگردد. اگر رأس v به رأس دیگری مثل رأس w رأی داده باشد، بدان معناست که رأس v از حق خود برای نامزدی به عنوان یک کاندیدا دست برداشته، در نتیجه رأس u به رأسw رأی میدهد. در اینجا رأس u به خوشهای که رأس w ایجاد کرده و رأس v هم در آن عضویت دارد اضافه خواهد شد. پس از رأیگیری، خوشههای کوچکی به دست میآیند که البته انجمنهای نهائی نیستند. در گام سوم، این خوشهها به عنوان انجمنهای اولیه در نظر گرفته شده و در یک حلقه تکرار، برخی از آنها برای ایجاد انجمنهای نهائی ادغام میشوند. برای افزایش کارائی، از ایده باربر [1] بهره گرفته شد و استراتژی مشابهی برای پیوستن یک جفت انجمن که ادغام آنها میتواند به بزرگترین افزایش ماژولاریتی در هر تکرار منجر گردد بکار میرود. مقدار ماژولاریتی ساختار حاصل از خوشههای اولیه طبق رابطه 16 و مقدار افزایش ماژولاریتی حاصل از هر ادغام جهت تصمیمگیری برای انجام آن طبق رابطه 17 محاسبه میگردد:
(16) 
(17) 
در رابطه 16، m تعداد یالهای گراف، 
تعداد یالهای داخل انجمن 
، 
جمع درجه رأسهای نوع اول و 
جمع درجه رأسهای نوع دوم داخل انجمن است. در رابطه 17، افزایش ماژولاریتی حاصل از افزودن انجمن 
به انجمن بدست میآید. در اینجا، m تعداد یالهای گراف، 
درجه رأس p-ام از نوع اول در انجمن ، جمع درجه رأسهای نوع دوم داخل انجمن و 
تعداد یالهای بین رأس p-ام از نوع اول در انجمن با همه رأسهای نوع دوم داخل انجمن است. برای دستیابی به کیفیت بالاتر، فقط جفت خوشههائی در نظر گرفته میشوند که شباهت آنها بزرگتر از یک آستانه معین باشد. شباهت بین یک جفت انجمن اولیه و طبق رابطه 18 محاسبه میگردد. اگر این شباهت بزرگتر از آستانه تعریفی باشد، افزایش ماژولاریتی حاصل از این ادغام محاسبه میگردد. در هر تکرار انجمنهائی با هم ادغام میشوند که ادغام آنها بالاترین افزایش ماژولاریتی را نتیجه دهد. در پایان حلقه تکرار، ساختاری به عنوان ساختار نهائی به خروجی میرود که در بین همه تکرارها بالاترین ماژولاریتی حاصل از کل ساختار را به دست آورد.
(18) 
روند ادغام از وضعیتی شروع میشود که هر خوشه کوچک به عنوان یک انجمن اولیه در نظر گرفته شود، نه از وضعیتی که هر رأس یک انجمن است، یعنی زمان ادغام بسیار کمتر است. علاوه بر این، چون ادغام انجمنهای غیرمشابه ممکن است کیفیت ساختار انجمن حاصل را تضعیف کند، فقط ادغام انجمنهائی که شباهت آنها از یک آستانه معین بیشتر است مدنظر قرار میگیرد. همچنین، زمانی که بین هر جفت انجمن شباهتی بزرگتر از آستانه معین وجود نداشته باشد، بجای تکرار عملیات ادغام تا زمانی که همه رأسها در یک انجمن قرار گیرند، میتوان رویه ادغام را زودتر خاتمه داد و این یعنی فرآیند ادغام با کارائی بالا انجام میشود.
شبه کد بیانگر مراحل مختلف روش پیشنهادی به صورت زیر است:
00 Input: 
, Bipartite Network; Output: CS, Detected Community Structure
01 for 
do
02 
03 Calculate 
from 
of all 
04 
;
05 while 
do
06 
; 
07 
08 if 
then
09 There is no vertex whose degree is larger than u in the neighborhood of v and u votes for itself
10 for 
do
11 
12 
13 if 
then
14 The similarity between u and v is 0, u nominates itself as a candidate and votes for itself
15 if v has not voted for other vertices then u nominates v as a candidate, and votes for v
16 else v has voted for other vertex, u votes for that vertex also
17 return 
18 
19 
20 while 
do
21 for 
do
22 if 
then
23 
24 Calculate the modularity after joining the selected pair of communities and record the current largest modularity and the corresponding community structure as a 
25 
26 return CS
شکل 2. روند کلی مراحل مختلف روش پیشنهادی
3- نتایج آزمایشهای تجربی
در این بخش روش پیشنهادی در مقایسه با دو الگوریتم شناخته شده برای شناسائی انجمنها در شبکههای دوبخشی مصنوعی و واقعی به نام AdaptiveBRIM و BiAttractor (به شرح زیر) ارزیابی میشود. کد روش پیشنهادی در محیط Colab نوشته شده و نتایج کار، با پیاده سازی این کد بر روی یک سرور با مشخصات Intel E5-2683 v4 Broadwell @ 2.1Ghz حاصل شد.
· الگوریتم AdaptiveBRIM: آقای باربر الگوریتم ماژولهای القائی بازگشتی دوبخشی64 را بر اساس ایده به حداکثررسانی مکرر ماژولاریتی 
در شبکه دوبخشی پیشنهاد کرد [1] و [36]. در هر تکرار، تضمین میشود که کاهش نیابد. با این حال، تقسیمبندی شناسائیشده شبکههای دوبخشی منجر به یک حداکثر محلی به جای حداکثر عمومی میشود. در همین حال تعداد ماژولها نیز با به حداکثر رساندن ماژولاریتی تعیین میشود.
· الگوریتم BiAttractor: آقای سان روش جدیدی با استفاده از دینامیک فاصله برای شناسائی انجمنهای دوحالته در شبکه های دوبخشی بزرگ پیشنهاد داد که در آن از تعاملهای جامعه انسانی الهام گرفته شده، به طوری که تعاملهای بیشتر داخل انجمن و تعاملهای کمتر بین انجمنهای متفاوت وجود دارد. الگوریتم در شبکههای پراکنده پیچیدگی زمانی دارد و تقسیمبندی دقیقی از انجمنها را به دست میآورد [34].
پیچیدگی زمانی
در روش پیشنهادی، شناسائی انجمنهای اولیه با شبیهسازی فرآیند رأیگیری را میتوان با پیچیدگی زمانی 
انجام داد که در آن n و m به ترتیب تعداد رأسها در یکی از دو مجموعه رأس و تعداد یالهای شبکه بوده و d میانگین درجه رأسهاست. ادغام برخی انجمنهای اولیه برای به دست آوردن انجمنهای نهائی پیچیدگی زمانی 
را داراست، که در آن k دفعات تکرار ادغام بوده و در حالت کلی 
و 
است. پس کل زمان مصرفی 
در شبکههای پراکنده است و نتیجه میگیریم که روش پیشنهادی میتواند به طور موثر در شبکههای بزرگ مقیاس اعمال شود.
پارامترهای ارزیابی
برای مقایسه روشهای مختلف دو نوع اندازهگیری وجود دارد. اگر تقسیمات انجمنها روی شبکههای زیرین از قبل داده شده باشد، معیار اطلاعات متقابل نرمال شده65 (NMI) برای دادن امتیاز از بازه [0-1] اعمال میشود [44]، وگرنه معیار ماژولاریتی بکار گرفته میشود [25]. ماژولاریتی اصل فقط برای شبکههای یکبخشی تعریف شده بود اما باربر تعریف ماژولاریتی در شبکههای دوبخشی را با عنوان گسترش داد [1]. مقدار بالاتر از بازه [0-1] نشان دهنده یال درون انجمن بیشتر از یال مورد انتظار مدل تهی است، به دلیل مسئله محدودیت تفکیک نیز محدودیت دارد [26].
شبکههای مصنوعی
برخی روشهای شناسائی انجمن وابسته به بهینهسازی مقدار ماژولاریتی هستند. این روشها ممکن است مشکل محدودیت تفکیک و محدودیت شناسائی انجمنهای کوچکتر از مقداری معین، بسته به اندازه شبکه و یالهای داخلی داشته باشند. برای نشان دادن اثربخشی روش پیشنهادی حلقهای از bicliqueها با تعداد biclique مختلف طراحی شد. هر biclique از دو نوع مجموعه رأس دوتائی و سهتائی تشکیل شده که به طور کامل با هم متصل هستند. ویژگیهای توپولوژیکی پایه آنها در جدول 1 آمده است. آزمایشها روی حلقههای با تعداد biclique مختلف انجام و نتایج تفصیلی در جدول 2 نشان داده شده و بیانگر آن است که مقدار NMI انجمنهای حاصل و دقت شناسائی تعداد آنها در روش پیشنهادی بهبود یافته است.
جدول 1. ویژگیهای توپولوژیکی پایه حلقههای biclique
|
|
|
|
|
|
|
| ||
0.5- | 0.482 | 2.80 | 28 | 20 | 8 | 12 | 4-bicliq. | ||
0.5- | 0.482 | 2.80 | 56 | 40 | 16 | 24 | 8-bicliq. | ||
0.5- | 0.482 | 2.80 | 112 | 80 | 32 | 48 | 16-bicliq. | ||
روش پیشنهادی | BiAttractor | AdaptiveBRIM |
| ||||||
| NMI |
| NMI |
| NMI | ||||
4 | 1.000 | 4 | 1.000 | 4 | 1.000 | 4-bicliq. | |||
8 | 1.000 | 8 | 1.000 | 8 | 1.000 | 8-bicliq. | |||
16 | 1.000 | 16 | 1.000 | 15 | 0.934 | 16-bicliq. | |||
|
|
|
|
|
|
|
| ||
0.337- | 0.328 | 5.563 | 89 | 32 | 14 | 18 | SW | ||
0.743- | 0.781 | 2.270 | 160 | 141 | 5 | 146 | AR | ||
0.171- | 0.303 | 3.140 | 358 | 244 | 136 | 108 | SCI | ||
0.166- | 0.427 | 2.139 | 1476 | 1380 | 551 | 829 | CN | ||
روش پیشنهادی | BiAttractor | AdaptiveBRIM |
| ||||||
|
|
|
|
|
| ||||
4 | 0.358 | 4 | 0.345 | 4 | 0.345 | SW | |||
5 | 0.636 | 5 | 0.601 | 5 | 0.602 | AR | |||
35 | 0.899 | 39 | 0.660 | 24 | 0.660 | SCI | |||
79 | 0.938 | 132 | 0.859 | 104 | 0.798 | CN | |||
