شناسائی انجمن در شبکههای دوبخشی با استفاده از معیار مرکزیت هلرنک
محورهای موضوعی : فناوری اطلاعات و ارتباطات
علی خسروزاده
1
(گروه مهندسی کامپیوتر، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران)
علی موقر
2
()
محمدمهدی گیلانیان صادقی
3
(گروه مهندسی کامپیوتر، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران)
حمیدرضا ماهیار
4
(گروه مهندسی کامپیوتر، دانشگاه مک مستر، همیلتون، انتاریو، کانادا)
کلید واژه: شبکههای اجتماعی, گراف‌‌های دوبخشی, معیار مرکزیت, شناسائی انجمن, رأی‌‌گیری,
چکیده مقاله :
ساختار انجمن ویژگی مشترک و مهمی در بسیاری از شبکههای پیچیده از جمله شبکههای دوبخشی است. شناسائی انجمن‌‌ها در سال‌های اخیر در بسیاری زمینه‌ها مورد توجه قرار گرفته و روش‌های زیادی برای این منظور پیشنهاد شده است، اما مصرف سنگین زمان در برخی روش‌‌ها، استفاده از آنها را در شبکههای بزرگ مقیاس محدود میکند. روش‌هائی با پیچیدگی کمتر وجود دارند اما اکثراً غیرقطعی هستند که کاربرد آنها در دنیای واقعی را کاهش میدهد. رویکرد معمول اتخاذ شده برای شناسائی انجمن‌‌ها در شبکههای دوبخشی این است که ابتدا یک طرح‌‌ریزی یک‌بخشی از شبکه ساخته شود و سپس انجمن‌‌ها در آن طرح‌‌ریزی با استفاده از روش‌های مربوط به شبکههای یک‌بخشی شناسائی شوند. این طرح‌‌ریزی‌‌ها به طور ذاتی اطلاعات را از دست می‌دهند. در این مقاله بر اساس معیار ماژولاریتی دوبخشی که قدرت تقسیم‌‌‌‌بندی‌‌ها را در شبکههای دوبخشی محاسبه میکند و با استفاده از معیار مرکزیت هلرنک، روشی سریع و قطعی برای شناسائی انجمن‌‌ها از شبکههای دوبخشی به طور مستقیم و بی‌نیاز از طرح‌‌ریزی ارائه گردیده است. روش پیشنهادی از فرآیند رأی‌‌گیری در فعالیت‌‌های انتخاباتی در جامعه انسانی الهام گرفته و آن را شبیه‌‌سازی میکند. نتایج آزمایشات نشان میدهد، مقدار ماژولاریتی انجمن‌‌های حاصل و دقت شناسائی تعداد آنها در روش پیشنهادی بهبود یافته است.
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.