Geodesic
A New overlapping community detection algorithm based on similarity of neighbors in complex networks
Kybernetika, Tome 58 (2022) no. 2, pp. 277-300
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Community detection algorithms help us improve the management of complex networks and provide a clean sight of them. We can encounter complex networks in various fields such as social media, bioinformatics, recommendation systems, and search engines. As the definition of the community changes based on the problem considered, there is no algorithm that works universally for all kinds of data and network structures. Communities can be disjointed such that each member is in at most one community or overlapping such that every member is in at least one community. In this study, we examine the problem of finding overlapping communities in complex networks and propose a new algorithm based on the similarity of neighbors. This algorithm runs in $ O(m \textit{lg} m) $ running time in the complex network containing $ m $ number of relationships. To compare our algorithm with existing ones, we select the most successful four algorithms from the Community Detection library (CDlib) by eliminating the algorithms that require prior knowledge, are unstable, and are time-consuming. We evaluate the successes of the proposed algorithm and the selected algorithms using various known metrics such as modularity, F-score, and Normalized Mutual Information. In addition, we adapt the coverage metric defined for disjoint communities to overlapping communities and also make comparisons with this metric. We also test all of the algorithms on small graphs of real communities. The experimental results show that the proposed algorithm is successful in finding overlapping communities.
Community detection algorithms help us improve the management of complex networks and provide a clean sight of them. We can encounter complex networks in various fields such as social media, bioinformatics, recommendation systems, and search engines. As the definition of the community changes based on the problem considered, there is no algorithm that works universally for all kinds of data and network structures. Communities can be disjointed such that each member is in at most one community or overlapping such that every member is in at least one community. In this study, we examine the problem of finding overlapping communities in complex networks and propose a new algorithm based on the similarity of neighbors. This algorithm runs in $ O(m \textit{lg} m) $ running time in the complex network containing $ m $ number of relationships. To compare our algorithm with existing ones, we select the most successful four algorithms from the Community Detection library (CDlib) by eliminating the algorithms that require prior knowledge, are unstable, and are time-consuming. We evaluate the successes of the proposed algorithm and the selected algorithms using various known metrics such as modularity, F-score, and Normalized Mutual Information. In addition, we adapt the coverage metric defined for disjoint communities to overlapping communities and also make comparisons with this metric. We also test all of the algorithms on small graphs of real communities. The experimental results show that the proposed algorithm is successful in finding overlapping communities.
DOI : 10.14736/kyb-2022-2-0277
Classification : 94C15
Keywords: overlapping community detection; complex networks; graph approach; similarity approach; community metrics 
@article{10_14736_kyb_2022_2_0277,
     author = {\c{C}etin, Pelin and Emrah Amrahov, Sahin},
     title = {A {New} overlapping community detection algorithm based on similarity of neighbors in complex networks},
     journal = {Kybernetika},
     pages = {277--300},
     year = {2022},
     volume = {58},
     number = {2},
     doi = {10.14736/kyb-2022-2-0277},
     mrnumber = {4467497},
     zbl = {07584157},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-2-0277/}
}
TY  - JOUR
AU  - Çetin, Pelin
AU  - Emrah Amrahov, Sahin
TI  - A New overlapping community detection algorithm based on similarity of neighbors in complex networks
JO  - Kybernetika
PY  - 2022
SP  - 277
EP  - 300
VL  - 58
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-2-0277/
DO  - 10.14736/kyb-2022-2-0277
LA  - en
ID  - 10_14736_kyb_2022_2_0277
ER  - 
%0 Journal Article
%A Çetin, Pelin
%A Emrah Amrahov, Sahin
%T A New overlapping community detection algorithm based on similarity of neighbors in complex networks
%J Kybernetika
%D 2022
%P 277-300
%V 58
%N 2
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2022-2-0277/
%R 10.14736/kyb-2022-2-0277
%G en
%F 10_14736_kyb_2022_2_0277
Çetin, Pelin; Emrah Amrahov, Sahin. A New overlapping community detection algorithm based on similarity of neighbors in complex networks. Kybernetika, Tome 58 (2022) no. 2, pp. 277-300. doi: 10.14736/kyb-2022-2-0277

[1] Aghaalizadeh, S., Afshord, S. T., Bouyer, A., Anari, B.: A three-stage algorithm for local community detection based on the high node importance ranking in social networks. Phys. A 563 (2021), 125420. | DOI | MR

[2] Agrawal, S., Patel, A.: SAG cluster: An unsupervised graph clustering based on collaborative similarity for community detection in complex networks. Phys. A 563 (2021), 125459. | DOI

[3] Ahn, Y. Y., Bagrow, J. P., Lehmann, S.: Link communities reveal multiscale complexity in networks. Nature 466 (2010), 761-764. | DOI

[4] Arab, M., Hasheminezhad, M.: Limitations of quality metrics for community detection and evaluation. In: 3th International Conference on Web Research (ICWR), Tehran 2017.

[5] Attal, J. P., Malek, M., Zolghadri, M.: Overlapping community detection using core label propagation algorithm and belonging functions. Appl. Intell. 51 (2021), 8067-8087. | DOI

[6] CDlib: Community Discovery Library.

[7] Chakraborty, T., Dalmia, A., Mukherjee, A., Ganguly, N.: Metrics for community analysis: A survey. ACM Computing Surveys 50 (2018), 1-37. | DOI

[8] Chen, D., Shang, M., Lv, Z., Fu, Y.: Detecting overlapping communities of weighted networks via a local algorithm. Phys. A 389 (2010), 4177-4187. | DOI

[9] Choumane, A., Awada, A., Harkous, A.: Core expansion: a new community detection algorithm based on neighborhood overlap. Soc. Netw. Anal. Min. 10 (2020), 30. | DOI

[10] Coscia, M., Rossetti, G., Giannotti, F., Pedreschi, D.: DEMON: A local-first discovery method for overlapping communities. In: Proc. 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing 2012.

[11] Amrahov, Ş. Emrah, Tugrul, B.: A community detection algorithm on graph data. In: 2018 International Conference on Artificial Intelligence and Data Processing (IDAP), Malatya 2018.

[12] Farkas, I., Ábel, D., Palla, G., Vicsek, T.: Weighted network modules. New J. Phys. 9 (2007), 180. | DOI

[13] Feng, L., Zhao, Q., Zhou, C.: Incorporating affiliation preference into overlapping community detection. Phys. A 563 (2021), 125429. | DOI | MR

[14] Fortunato, S.: Community detection in graphs. Phys. Rep. 486 (2009), 75-174. | DOI | MR

[15] Gao, Y., Yu, X., Zhang, H.: Overlapping community detection by constrained personalized pagerank. Expert Syst. Appl. 173 (2021), 114682. | DOI

[16] Ge, J., Sun, H., Xue, C., He, L., Jia, X., He, H., Chen, J.: LPX: Overlapping community detection based on X-means and label propagation algorithm in attributed networks. Comput. Intell. 37 (2021), 484-510. | DOI | MR

[17] Gopalan, P. K., Blei, D. M.: Efficient discovery of overlapping communities in massive networks. Proc. Natl. Acad. Sci. USA 110 (2013), 14534-14539. | DOI | MR

[18] Goswami, S., Das, A. K.: Determining maximum cliques for community detection in weighted sparse networks. Knowl. Inf. Syst. 64 (2022), 289-324. | DOI

[19] Gregory, S.: An algorithm to find overlapping community structure in networks. In: Proc. 11th European Conference on Principles and Practice of Knowledge Discovery in Databases, Warsaw 2007.

[20] Gregory, S.: A fast algorithm to find overlapping communities in networks. In: Machine Learning and Knowledge Discovery in Databases, Berlin 2008.

[21] Gregory, S.: Finding overlapping communities in networks by label propagation. New J. Phys. 12 (2010), 103018. | DOI

[22] Guo, K., Wang, Q., Lin, J., Wu, L., Guo, W., Chao, K.-M.: Network representation learning based on community-aware and adaptive random walk for overlapping community detection. Appl. Intell. 52 (2022), 9919-9937. | DOI

[23] Gupta, S., Kumar, P.: An overlapping community detection algorithm based on rough clustering of links. Data Knowl. Engrg. 125 (2020), 101777. | DOI

[24] He, C., Liu, H., Tang, Y., Liu, S., Fei, X., Cheng, Q., Li, H.: Similarity preserving overlapping community detection in signed networks. Future Gener. Comput. Syst. 116 (2021), 275-290. | DOI

[25] Jin, D., Gabrys, B., Dang, J.: Combined node and link partitions method for finding overlapping communities in complex networks. Sci. Rep. 5 (2015), 8600. | DOI

[26] Joghan, H. S., Bagheri, A., Azad, M.: Weighted label propagation based on local edge betweenness. J. Supercomput. 75 (2019), 8094-8114. | DOI

[27] Kim, J., Lim, S., Lee, J. G., Lee, B. S.: LinkBlackHole*: Robust overlapping community detection using link embedding. IEEE Trans. Knowl. Data Engrg. 31 (2019), 2138-2150. | DOI

[28] Kouni, I. B. E., Karoui, W., Romdhane, L. B.: Node importance based label propagation algorithm for overlapping community detection in networks. Expert Syst. Appl. 162 (2020), 113020. | DOI

[29] Lancichinetti, A., Fortunato, S., Kertesz, J.: Detecting the overlapping and hierarchical community structure in complex networks. New J. Phys. 11 (2009), 033015. | DOI

[30] Lee, C., Reid, F., McDaid, A., Hurley, N.: Detecting highly overlapping community structure by greedy clique expansion.

[31] Li, C., Chen, H., Li, T., Yang, X.: A stable community detection approach for complex network based on density peak clustering and label propagation. Appl. Intell. 52 (2021), 1188-1208. | DOI

[32] Lierde, H. V., Member, G.S., Chow, T. W. S.: Scalable spectral clustering for overlapping community detection in large-scale networks. IEEE Trans. Knowl. Data. Engrg. 32 (2020), 754-767. | DOI

[33] Lim, S., Ryu, S., Kwon, S., Jung, K., Lee, J. G.: LinkSCAN: Overlapping community detection using the link-space transformation. In: IEEE 30th International Conference on Data Engineering, Chicago 2014.

[34] Long, H.: Overlapping community detection with least replicas in complex networks. Inform. Sci. 453 (2018), 216-226. | DOI | MR

[35] Lu, H., Zhang, Z., Qu, Z., Kang, Y.: LPANNI: Overlapping community detection using label propagation in large-scale complex networks. IEEE Trans. Knowl. Data. Engrg. 31 (2019), 1736-1749. | DOI

[36] Ma, T., Liu, Q., Cao, J., Tian, Y., Al-Dhelaan, A., Al-Rodhaan, M.: LGIEM: Global and local node influence based community detection. Future Gener. Comput. Syst. 105 (2020), 533-546. | DOI

[37] Ma, T., Wang, Y., Tang, M., Cao, J., Tian, Y., Al-Dhelaan, A., Al-Rodhaan, M.: LED: A fast overlapping communities detection algorithm based on structural clustering. Neurocomputing 207 (2016), 488-500. | DOI

[38] Mahabadi, A., Hosseini, M.: SLPA-based parallel overlapping community detection approach in large complex social networks. Multimed. Tools. Appl. 80 (2021), 6567-6598. | DOI

[39] McCarthy, A. D., Chen, T., Rudinger, R., Matula, D. W.: Metrics matter in community detection. In: Complex Networks and Their Applications VIII (H. Cherifi, S. Gaito, J. Mendes, E. Moro, L. Rocha, eds.), Stud. Comput. Intell., 881, Springer 2019, pp. 164-175. | DOI

[40] McDaid, A., Greene, D., Hurley, N.: Normalized mutual information to evaluate overlapping community finding algorithms.

[41] Nepusz, T., Petróczi, A., Négyessy, L., Bazsó, F.: Fuzzy communities and the concept of bridgeness in complex networks. Phys. Rev. E 77 (2008), 1-12. | DOI | MR

[42] Newman, M. E. J., Girvan, M.: Finding and evaluating community structure in networks. Phys. Rev. E 69 (2004), 1-15. | DOI | MR

[43] Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435 (2005), 814-818. | DOI

[44] Pattabiraman, B., Patwary, M. A., Gebremedhin, A. H., Liao, W. K., Choudhary, A.: Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detection. Internet Math. 11 (2015), 421-448. | DOI | MR

[45] Pattanayak, H. S., Verma, H. K., Sangal, A. L.: Community detection metrics and algorithms in social networks. In: First International Conference on Secure Cyber Computing and Communication (ICSCCC), Jalandhar 2018, pp. 483-489. | DOI

[46] Psorakis, I., Roberts, S., Ebden, M., Sheldon, B.: Overlapping community detection using Bayesian non-negative matrix factorization. Phys. Rev. E 83 (2011), 066114. | DOI

[47] Qin, M., Lei, K.: Dual-channel hybrid community detection in attributed networks. Inform. Sci. 551 (2021), 146-167. | DOI | MR

[48] Shen, H., Cheng, X., Cai, K., Hu, M-B.: Detect overlapping and hierarchical community structure in networks. Phys. A 388 (2009), 1706-1712. | DOI

[49] Sun, Z., Wang, B., Sheng, J., Yu, Z., Shao, J.: Overlapping community detection based on information dynamics. IEEE Access 6 (2018), 70919-70934. | DOI

[50] Wang, X., Liu, G., Li, J.: Overlapping community detection based on structural centrality in complex networks. IEEE Access 5 (2017), 25258-25269. | DOI

[51] Wang, Z. X., Li, Z. C., Ding, X. F., Tang, J. H.: Overlapping community detection based on node location analysis. Knowl. Based Syst. 105 (2016), 225-235. | DOI

[52] Wen, X., Chen, W. N., Lin, Y., Gu, T., Zhang, H., Li, Y., Yin, Y., Zhang, J.: A maximal clique based multiobjective evolutionary algorithm for overlapping community detection. IEEE Trans. Evol. Comput. 21 (2017), 363-377. | DOI

[53] Whang, J. J., David, F., Dhillon, I. S.: Overlapping community detection using neighborhood-inflated seed expansion. IEEE Trans. Knowl. Data. Engrg. 28 (2016), 1272-1284. | DOI

[54] Wu, Q., Chen, R., Wang, L., Guo, K.: A label propagation algorithm for community detection on high-mixed networks. Concurr. Comput. Pract. Exp. 33 (2021). | DOI

[55] Xie, J., Szymanski, B. K., Liu, X.: SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In: IEEE 11th International Conference on Data Mining Workshops, Vancouver 2011, pp. 344-349. | DOI

[56] Yu, H., Ma, R., Chao, J., Zhang, F.: An overlapping community detection approach based on DeepWalk and improved label propagation. IEEE Trans. Comput. Soc. Syst. (2022), 1-11. | DOI | MR

[57] Zhang, S., Wang, R. S., Zhang, X. S.: Uncovering fuzzy community structure in complex networks. Phys. Rev. E 76 (2007), 046103. | DOI

[58] Zhang, Y., Yeung, D. Y.: Overlapping community detection via bounded nonnegative matrix tri-factorization. In: Proc. 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing 2012, pp. 606-614. | DOI

[59] Zhou, Q., Cai, S., Zhang, Y.: Detecting overlapping community structure with node influence. IEEE Access 7 (2019), 171223-171234. | DOI

Cité par Sources :