A New overlapping community detection algorithm based on similarity of neighbors in complex networks

Pelin Çetin; Sahin Emrah Amrahov

Kybernetika (2022)

  • Volume: 58, Issue: 2, page 277-300
  • ISSN: 0023-5954

Abstract

top
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 𝑙𝑔 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.

How to cite

top

Çetin, Pelin, and Emrah Amrahov, Sahin. "A New overlapping community detection algorithm based on similarity of neighbors in complex networks." Kybernetika 58.2 (2022): 277-300. <http://eudml.org/doc/298899>.

@article{Çetin2022,
abstract = {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.},
author = {Çetin, Pelin, Emrah Amrahov, Sahin},
journal = {Kybernetika},
keywords = {overlapping community detection; complex networks; graph approach; similarity approach; community metrics},
language = {eng},
number = {2},
pages = {277-300},
publisher = {Institute of Information Theory and Automation AS CR},
title = {A New overlapping community detection algorithm based on similarity of neighbors in complex networks},
url = {http://eudml.org/doc/298899},
volume = {58},
year = {2022},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 58
IS - 2
SP - 277
EP - 300
AB - 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.
LA - eng
KW - overlapping community detection; complex networks; graph approach; similarity approach; community metrics
UR - http://eudml.org/doc/298899
ER -

References

top
  1. Aghaalizadeh, S., Afshord, S. T., Bouyer, A., Anari, B., , Phys. A 563 (2021), 125420. MR4169328DOI
  2. Agrawal, S., Patel, A., , Phys. A 563 (2021), 125459. DOI
  3. Ahn, Y. Y., Bagrow, J. P., Lehmann, S., , 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., , Appl. Intell. 51 (2021), 8067-8087. DOI
  6. CDlib, Community Discovery Library. 
  7. Chakraborty, T., Dalmia, A., Mukherjee, A., Ganguly, N., , ACM Computing Surveys 50 (2018), 1-37. DOI
  8. Chen, D., Shang, M., Lv, Z., Fu, Y., , Phys. A 389 (2010), 4177-4187. DOI
  9. Choumane, A., Awada, A., Harkous, A., , 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., , New J. Phys. 9 (2007), 180. DOI
  13. Feng, L., Zhao, Q., Zhou, C., , Phys. A 563 (2021), 125429. MR4165640DOI
  14. Fortunato, S., , Phys. Rep. 486 (2009), 75-174. MR2580414DOI
  15. Gao, Y., Yu, X., Zhang, H., , Expert Syst. Appl. 173 (2021), 114682. DOI
  16. Ge, J., Sun, H., Xue, C., He, L., Jia, X., He, H., Chen, J., , Comput. Intell. 37 (2021), 484-510. MR4221985DOI
  17. Gopalan, P. K., Blei, D. M., , Proc. Natl. Acad. Sci. USA 110 (2013), 14534-14539. MR3105375DOI
  18. Goswami, S., Das, A. K., , 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., , New J. Phys. 12 (2010), 103018. DOI
  22. Guo, K., Wang, Q., Lin, J., Wu, L., Guo, W., Chao, K.-M., , Appl. Intell. 52 (2022), 9919-9937. DOI
  23. Gupta, S., Kumar, P., , Data Knowl. Engrg. 125 (2020), 101777. DOI
  24. He, C., Liu, H., Tang, Y., Liu, S., Fei, X., Cheng, Q., Li, H., , Future Gener. Comput. Syst. 116 (2021), 275-290. DOI
  25. Jin, D., Gabrys, B., Dang, J., , Sci. Rep. 5 (2015), 8600. DOI
  26. Joghan, H. S., Bagheri, A., Azad, M., , J. Supercomput. 75 (2019), 8094-8114. DOI
  27. Kim, J., Lim, S., Lee, J. G., Lee, B. S., , IEEE Trans. Knowl. Data Engrg. 31 (2019), 2138-2150. DOI
  28. Kouni, I. B. E., Karoui, W., Romdhane, L. B., , Expert Syst. Appl. 162 (2020), 113020. DOI
  29. Lancichinetti, A., Fortunato, S., Kertesz, J., , 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., , Appl. Intell. 52 (2021), 1188-1208. DOI
  32. Lierde, H. V., Member, G.S., Chow, T. W. S., , 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., , Inform. Sci. 453 (2018), 216-226. MR3804435DOI
  35. Lu, H., Zhang, Z., Qu, Z., Kang, Y., , 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., , 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., , Neurocomputing 207 (2016), 488-500. DOI
  38. Mahabadi, A., Hosseini, M., , Multimed. Tools. Appl. 80 (2021), 6567-6598. DOI
  39. McCarthy, A. D., Chen, T., Rudinger, R., Matula, D. W., , 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., , Phys. Rev. E 77 (2008), 1-12. MR2448166DOI
  42. Newman, M. E. J., Girvan, M., , Phys. Rev. E 69 (2004), 1-15. MR2282139DOI
  43. Palla, G., Derényi, I., Farkas, I., Vicsek, T., , Nature 435 (2005), 814-818. DOI
  44. Pattabiraman, B., Patwary, M. A., Gebremedhin, A. H., Liao, W. K., Choudhary, A., , Internet Math. 11 (2015), 421-448. MR3373772DOI
  45. Pattanayak, H. S., Verma, H. K., Sangal, A. L., , 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., , Phys. Rev. E 83 (2011), 066114. DOI
  47. Qin, M., Lei, K., , Inform. Sci. 551 (2021), 146-167. MR4190551DOI
  48. Shen, H., Cheng, X., Cai, K., Hu, M-B., , Phys. A 388 (2009), 1706-1712. DOI
  49. Sun, Z., Wang, B., Sheng, J., Yu, Z., Shao, J., , IEEE Access 6 (2018), 70919-70934. DOI
  50. Wang, X., Liu, G., Li, J., , IEEE Access 5 (2017), 25258-25269. DOI
  51. Wang, Z. X., Li, Z. C., Ding, X. F., Tang, J. H., , 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., , IEEE Trans. Evol. Comput. 21 (2017), 363-377. DOI
  53. Whang, J. J., David, F., Dhillon, I. S., , IEEE Trans. Knowl. Data. Engrg. 28 (2016), 1272-1284. DOI
  54. Wu, Q., Chen, R., Wang, L., Guo, K., , Concurr. Comput. Pract. Exp. 33 (2021). DOI
  55. Xie, J., Szymanski, B. K., Liu, X., , In: IEEE 11th International Conference on Data Mining Workshops, Vancouver 2011, pp. 344-349. DOI
  56. Yu, H., Ma, R., Chao, J., Zhang, F., , IEEE Trans. Comput. Soc. Syst. (2022), 1-11. MR4150897DOI
  57. Zhang, S., Wang, R. S., Zhang, X. S., , Phys. Rev. E 76 (2007), 046103. DOI
  58. Zhang, Y., Yeung, D. Y., , 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., , IEEE Access 7 (2019), 171223-171234. DOI

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.