Motif-based Community Detection: a Probabilistic Model based on Repeating Patterns

Hajibabaei, H.; Seydi, V.; Koochari, A.

doi:10.22061/jecei.2023.9931.663

نشریات مستقل دانشگاه در سامانه ارزیابی نشریات علمی وزارت علوم

نشریه معماری وشهرسازی پایدار موفق به اخذ رتبه علمی-پژوهشی شد

تعداد نشریات	13
تعداد شماره‌ها	200
تعداد مقالات	2,008
تعداد مشاهده مقاله	2,680,170
تعداد دریافت فایل اصل مقاله	1,937,363

	Motif-based Community Detection: a Probabilistic Model based on Repeating Patterns
Journal of Electrical and Computer Engineering Innovations (JECEI)
مقاله 17، دوره 12، شماره 1، فروردین 2024، صفحه 247-258 اصل مقاله (1016.54 K)
نوع مقاله: Original Research Paper
شناسه دیجیتال (DOI): 10.22061/jecei.2023.9931.663
نویسندگان
H. Hajibabaei¹؛ V. Seydi^* ¹؛ A. Koochari²
¹Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.
²Department of Computer Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran.
تاریخ دریافت: 22 مرداد 1402، تاریخ بازنگری: 14 آبان 1402، تاریخ پذیرش: 13 آذر 1402
چکیده
Background and Objectives: The detection of community in networks is an important tool for revealing hidden data in network analysis. One of the signs that the community exists in the network is the neighborhood density between nodes. Also, the existence of a concept called a motif indicates that a community with a high edge density has a correlation between nodes that go beyond their close neighbors. Motifs are repetitive edge patterns that are frequently seen in the network. Methods: By estimating the triangular motif in the network, our proposed probabilistic motif-based community detection model (PMCD) helps to find the communities in the network. The idea of the proposed model is network analysis based on structural density between nodes and detecting communities by estimating motifs using probabilistic methods. Results: The suggested model's output is the strength of each node's affiliation to the communities and detecting overlaps in communities. To evaluate the performance and accuracy of the proposed method, experiments are done on real-world and synthetic networks. The findings show that, compared to other algorithms, the proposed method is acting more accurately and densely in detecting communities. Conclusion: The advantage of PMCD in using the probabilistic generative model is speeding up the computation of the hidden parameters and establishing the community based on the likelihood of triangular motifs. In fact, the proposed method proves there is a probabilistic correlation between the observation of two node pairs in different communities and the increased existence of motif structure in the network.
کلیدواژه‌ها
Community Detection؛ Motif؛ Complex Networks؛ Probabilistic Model

مراجع
[1] J. Sia, E. Jonckheere, P. Bogdan, "Ollivier-ricci curvature-based method to community detection in complex networks," Sci. Rep., 9(1): 1-12, 2019. [2] Y. Y. Ahn, J. P. Bagrow, S. Lehmann, "Link communities reveal multiscale complexity in networks," Nature, 466(7307): 761-764, 2010. [3] J. J. McAuley, J. Leskovec, "Learning to discover social circles in ego networks," in Proc. NIPS: 548-556, 2012. [4] M. Girvan, M. E. Newman, "Community structure in social and biological networks," PNAS, 99(12): 7821-7826, 2002. [5] W. Wu, S. Kwong, Y. Zhou, Y. Jia, W. Gao, "Nonnegative matrix factorization with mixed hypergraph regularization for community detection," Inf. Sci., 435: 263-281, 2018. [6] S. Fortunato, D. Hric, "Community detection in networks: A user guide," Phys. Rep., 659: 1-44, 2016. [7] H. Hajibabaei, V. Seydi, A. Koochari, "Community detection in weighted networks using probabilistic generative model," J. Intell. Inf. Syst., 60: 119- 136, 2023. [8] T. S. Wang, H. T. Lin, P. Wang, "Weighted-spectral clustering algorithm for detecting community structures in complex networks," Artif. Intell. Rev., 47(4): 463-483, 2017. [9] X. Chen, J. Li, "Community detection in complex networks using edge-deleting with restrictions," Physica A, 519: 181-194, 2019. [10] F. D. Zarandi, M. K. Rafsanjani, "Community detection in complex networks using structural similarity," Physica A, 503: 882-891, 2018. [11] B. D. Le, H. Shen, H. Nguyen, N. Falkner, "Improved network community detection using meta-heuristic based label propagation," Appl. Intell., 49(4): 1451-1466, 2019. [12] C. Lyu, Y. Shi, L. Sun, "A novel local community detection method using evolutionary computation," IEEE Trans. Cybern., 51(6): 3348-3360, 2019. [13] W. Zhou, X. Wang, C. Zhang, R. Li, C. Wang, "Community detection by enhancing community structure in bipartite networks," Mod. Phys. Lett. B, 33(7): 1950076, 2019. [14] J. Yang, J. Leskovec, "Overlapping community detection at scale: a nonnegative matrix factorization approach," in Proc. the Sixth ACM International Conference on Web Search and Data Mining: 587-596, 2013. [15] T. Ma et al., "LED: A fast overlapping communities detection algorithm based on structural clustering," Neurocomputing, 207: 488-500, 2016. [16] F. Liu, D. Choi, L. Xie, K. Roeder, "Global spectral clustering in dynamic networks," PNAS, 115(5): 927-932, 2018. [17] J. Yang, J. Leskovec, "Community-affiliation graph model for overlapping network community detection," in Proc. 2012 IEEE 12th International Conference on Data Mining: 1170-1175, 2012. [18] G. Palla, I. Derényi, I. Farkas, T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," nature, 435(7043): 814-818, 2005. [19] X. Zhou, K. Yang, Y. Xie, C. Yang, T. Huang, "A novel modularity-based discrete state transition algorithm for community detection in networks," Neurocomputing, 334: 89-99, 2019. [20] M. E. Newman, M. Girvan, "Finding and evaluating community structure in networks," Phys. Rev. E, 69(2): 026113, 2004. [21] K. Berahmand, A. Bouyer, "A link-based similarity for improving community detection based on label propagation algorithm," J. Syst. Sci. Complexity, 32(3): 737-758, 2019. [22] U. N. Raghavan, R. Albert, S. Kumara, "Near linear time algorithm to detect community structures in large-scale networks," Phys. Rev. E, 76(3): 036106, 2007. [23] M. Zarezade, E. Nourani, A. Bouyer, "Community detection using a new node scoring and synchronous label updating of boundary nodes in social networks," J. AI Data Min., 8(2): 201-212, 2020. [24] S. Kumar, B. Panda, D. Aggarwal, "Community detection in complex networks using network embedding and gravitational search algorithm," J. Intell. Inf. Syst., 57: 51-72, 2021. [25] A. Torkaman, K. Badie, A. Salajegheh, M. H. Bokaei, S. F. Fatemi, "A hybrid deep network representation model for detecting researchers’ communities," J. AI Data Min., 10(2): 233-243, 2022. [26] X. Su et al., "A comprehensive survey on community detection with deep learning," IEEE Trans. Neural Networks Learn. Syst., 2022. [27] M. Ali, M. Hassan, K. Kifayat, J. Y. Kim, S. Hakak, M. K. Khan, "Social media content classification and community detection using deep learning and graph analytics," Technol. Forecasting Social Change, 188: 122252, 2023. [28] C. Li, Y. Tang, Z. Tang, J. Cao, Y. Zhang, "Motif‐based embedding label propagation algorithm for community detection," Int. J. Intell. Syst., 37(3): 1880-1902, 2022. [29] M. A. Javed, M. S. Younis, S. Latif, J. Qadir, A. Baig, "Community detection in networks: A multidisciplinary review," J. Network Comput. Appl., 108: 87-111, 2018. [30] K. Guo, X. Huang, L. Wu, Y. Chen, "Local community detection algorithm based on local modularity density," Appl. Intell., 52(2): 1238-1253, 2022. [31] J. Sánchez-Oro, A. Duarte, "Iterated Greedy algorithm for performing community detection in social networks," Future Gener. Comput. Syst., 88: 785-791, 2018. [32] V. A. Traag, L. Waltman, N. J. Van Eck, "From Louvain to Leiden: guaranteeing well-connected communities," Sci. Rep., 9(1): 1-12, 2019. [33] C. Li, H. Chen, T. Li, X. Yang, "A stable community detection approach for complex network based on density peak clustering and label propagation," Appl. Intell., 52(2): 1188-1208, 2022. [34] J. Xie, B. K. Szymanski, X. Liu, "Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process," in Proc. 2011 ieee 11th International Conference on Data Mining Workshops: 344-349, 2011. [35] S. Gregory, "Finding overlapping communities in networks by label propagation," New J. Phys., 12(10): 103018, 2010. [36] B. Adamcsek, G. Palla, I. J. Farkas, I. Derényi, T. Vicsek, "CFinder: locating cliques and overlapping modules in biological networks," Bioinformatics, 22(8): 1021-1023, 2006. [37] P. Bloem, S. de Rooij, "Large-scale network motif analysis using compression," Data Min. Knowl. Discovery, 34: 1421-1453, 2020. [38] A. Arenas, A. Fernandez, S. Fortunato, S. Gomez, "Motif-based communities in complex networks," J. Phys. A: Math. Theor., 41(22): 224001, 2008. [39] C. E. Tsourakakis, J. Pachocki, M. Mitzenmacher, "Scalable motif-aware graph clustering," in Proc. the 26th International Conference on World Wide Web: 1451-1460, 2017. [40] L. Huang, H. Y. Chao, Q. Xie, "MuMod: A micro-unit connection approach for hybrid-order community detection," in Proc. the AAAI conference on artificial intelligence, 34(01): 107-114, 2020. [41] J. Yang, J. McAuley, J. Leskovec, "Community detection in networks with node attributes," in Proc. IEEE 13th International Conference on Data Mining: 1151-1156, 2013. [42] K. Yang, Q. Guo, J. G. Liu, "Community detection via measuring the strength between nodes for dynamic networks," Physica A, 509: 256-264, 2018. [43] W. Yu, W. Wang, P. Jiao, X. Li, "Evolutionary clustering via graph regularized nonnegative matrix factorization for exploring temporal networks," Knowledge-Based Syst., 167: 1-10, 2019. [44] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, U. Alon, "Network motifs: simple building blocks of complex networks," Science, 298(5594): 824-827, 2002. [45] Y. Xu, W. Yin, "A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion," SIAM J. Imag. Sci., 6(3): 1758-1789, 2013. [46] C. J. Hsieh, I. S. Dhillon, "Fast coordinate descent methods with variable selection for non-negative matrix factorization," in Proc. the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining: 1064-1072, 2011. [47] C. J. Lin, "Projected gradient methods for nonnegative matrix factorization," Neural Comput., 19(10): 2756-2779, 2007. [48] D. F. Gleich, C. Seshadhri, "Vertex neighborhoods, low conductance cuts, and good seeds for local community methods," in Proc, the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining: 597-605, 2012. [49] V. D. Blondel, J. L. Guillaume, R. Lambiotte, E. Lefebvre, "Fast unfolding of communities in large networks," J. Stat. Mech: Theory Exp., 2008(10): P10008, 2008. [50] A. Clauset, M. E. Newman, C. Moore, "Finding community structure in very large networks," Phys. Review E, 70(6): 066111, 2004. [51] W. W. Zachary, "An information flow model for conflict and fission in small groups," J. Anthropol. Res., 33(4): 452-473, 1977. [52] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, S. M. Dawson, "The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations," Behav. Ecol. Sociobiol., 54(4): 396-405, 2003. [53] J. Kunegis, "Konect: the koblenz network collection," in Proc. the 22nd International Conference on World Wide Web: 1343-1350, 2013. [54] J. Leskovec, J. Kleinberg, C. Faloutsos, "Graph evolution: Densification and shrinking diameters," ACM Trans. Knowl. Discovery Data (TKDD), 1(1): 2-es, 2007. [55] H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich, "Local higher-order graph clustering," in Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, 2017, pp. 555-564. [56] R. Rossi, N. Ahmed, "The network data repository with interactive graph analytics and visualization," in Proc. Twenty-ninth AAAI Conference on Artificial Intelligence, 2015. [57] A. Lancichinetti, S. Fortunato, F. Radicchi, "Benchmark graphs for testing community detection algorithms," Phys. Review E, 78(4): 046110, 2008.
آمار تعداد مشاهده مقاله: 162 تعداد دریافت فایل اصل مقاله: 138

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب

پیوندهای مفید

پیوندهای مفید

اخبار و اعلانات

آمار

Motif-based Community Detection: a Probabilistic Model based on Repeating Patterns