شناسائی جامعه در شبکه¬های پیچیده با استفاده از درخت پوشای مینیمم و بیشینه¬سازی ماژولاریتی
محورهای موضوعی : مهندسی برق و کامپیوترسندس بهادری 1 * , مریم نورائی 2
1 - گروه مهندسی کامپیوتر، دانشگاه آزاد اسلامي واحد آبادان، ایران
2 - گروه مهندسي كامپيوتر، دانشگاه آزاد اسلامي واحد آبادان، ایران
کلید واژه: شبکه‌های پیچیده, جامعه, درخت پوشای مینیمم, افزایش ماژولاریتی,
چکیده مقاله :
چکیده: ماژولاریتی، یکی از ویژگی های برجسته شبکه های پیچیده است که ساختار این شبکه ها را به صورت گروه های جامعه ای تقسیم می کند. تاکنون، روش های زیادی برای شناسایی جوامع در شبکه های پیچیده به کار گرفته شده است، اما برخی از این روش ها بهینه سازی های محلی دارند که به ترتیب پردازش نودها، جواب نهایی را تحت تاثیر قرار می دهند. در این مقاله، یک روش جدید برای یافتن جوامع در شبکه های پیچیده با استفاده از تقسیم و ادغام پیشنهاد شده است. در این روش، از درخت پوشای کمینه به عنوان یک ابزار برای تشخیص عدم تشابه بین نودها استفاده می شود. در فرایند تقسیم، یال هایی که بیشترین عدم تشابه را نشان می دهند، در درخت پوشای کمینه حذف می شوند تا گروه های کوچکتری از نودهای یک جامعه ایجاد شوند. در فرایند ادغام، هر گروه با گروه همسایه ادغام می شود که ترکیب آنها بیشترین افزایش ماژولاریتی را نسبت به گروه های همسایه دیگر داشته باشند. نتایج آزمایش های انجام شده بر روی شبکه های واقعی و شبکه های ساختگی نشان می دهد که روش پیشنهادی در این مقاله، دقت بهتری برای شناسایی جوامع در شبکه های پیچیده دارد.
Modularity is one of the prominent features of complex networks that divides the structure of these networks into community groups. So far, many methods have been used to identify communities in complex networks, but some of these methods have local optimizations that affect the order of processing nodes and the final solution. In this paper, a new method for finding communities in complex networks using split and merge is proposed. In this method, minimum spanning tree is used as a tool to detect dissimilarity between nodes. In the partitioning process, the edges that show the most dissimilarity are removed in the minimum spanning tree to create smaller groups of nodes in a community. In the merging process, each group is merged with the neighboring group whose combination has the highest increase in modularity compared to other neighboring groups. The results of experiments conducted on real networks and artificial networks show that the method proposed in this article has a good accuracy for identifying communities in complex networks.
[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.