Increasing the accuracy of identifying overlapping communities using weighted edges

Subject Areas : Multimedia Processing, Communications Systems, Intelligent Systems

Iraj Teymouri ¹ , Mehdi Afzali ²

1 - Farhangian University, Zanjan Branch, Zanjan, Iran
2 - Islamic Azad University

Received: 2020-12-08 Accepted : 2021-03-28 Published : 2020-09-22

Keywords: Social networks, community identification, Complex networks,

Abstract :

In recent years, several algorithms have been proposed for detection in complex networks. It should be noted that wuth regarding the features of these communities, one of the existing methods for identifying communities, is providing an algorithms for weighting the edges of the network as the weight of the edges of the communities are incresed and at the same time the weight of the edges between communities are reduced. Therefore the distinction between communities could be identified simply. In the proposed method with useing the process of weighting the edges, we distinguish between the nodes that are more similar to each other and the nodes that have slight similarity. i.e. by assigning the weight with using the proposed criteria in some algorithms, the edges with more weight will have a greater role in determining the population.According that there is a positive correlation between similarity measures and community structures, the results of the tests shows that using local similarity measures as the weight of edges for some algorithms, causes an increase in the accuracy of communities recognition. These algorithms use the degree of the nodes as one of the network characteristics for computing the cores absorbing ability for communities formation. For example, in the case of Real Networks, running WHD-EM algorithm on the High school network, discovers the communities with the NMI=0.6652 and the purity criteria equal to 0.9845. Also it should be noted that some algorithms such as CPM, OSLOM and LINK in terms of NMI criteria, are better.

References:

[1]Gros, C. Complex and adaptive dynamical systems : a primer, with 98 figures and 10 tables. Berlin: Springer, 2008.

[2]Hakami Zanjani, A., & Darooneh, A. “Finding communities in linear time by developing the seeds”. Physical Review E, 84(3), 2011: 036109.

[3]Fortunato, S. “Community detection in graphs”. Physics Reports, 486(3–5), 2010: 75-174.

[4]Palla, G., Derenyi, I., Farkas, I., & Vicsek, T. “Uncovering the overlapping community structure of complex networks in nature and society”. Nature, 435(7043), 2005: 814-818.

[5]Rives, A. W., & Galitski, T. “Modular organization of cellular networks”. Proc Natl Acad Sci U S A, 100(3), 2003: 1128-1133.

[6]Chen, J., & Yuan, B. “Detecting functional modules in the yeast protein-protein interaction network”. Bioinformatics, 22(18), 2006: 2283-2290.

[7]Caldarelli, G., & Vespignani, A. Large scale structure and dynamics of complex networks : from information technology to finance and natural science. Singapore ; Hackensack, NJ: World Scientific, 2007.

[8]Guimera, R., & Nunes Amaral, L. A. “ Functional cartography of complex metabolic networks”. Nature, 433(7028), 2005: 895-900.

[9]Krause, A. E., Frank, K. A., Mason, D. M., Ulanowicz, R. E., & Taylor, W. W. “Compartments revealed in food-web structure”. Nature, 426(6964), 2003: 282-285.

[10]Reichardt, J. Structure in complex networks. Berlin: Springer. 2009.

[11]Xiang, J., Hu, K., & Tang, Y. “A class of improved algorithms for detecting communities in complex networks”. Physica A: Statistical Mechanics and its Applications, 387(13), 2008: 3327-3334.

[12]Ju, X., et. Al. “Enhancing community detection by using local structural information. Journal of Statistical Mechanics: Theory and Experiment, 2016(3), 20016: 033405.

 [13]Kernighan, B. W., & Lin, S. “An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 1970: 291 - 307.

[14]Girvan, M., & Newman, M. E. “Community structure in social and biological networks”. Proc Natl Acad Sci U S A, 99(12), 2002: 7821-7826.

[15]Newman, M. E. J., & Girvan, M. “Finding and evaluating community structure in networks”. Phys. Rev. E, 69(2). 2004.

[16]Newman, M. E. J. “Fast algorithm for detecting community structure in networks. Phys. Rev, 69(6), 2004:

[17]Boettcher, S., & Percus, A. G. “Optimization with Extremal Dynamics”. Physical Review Letters, 86(23), 2001: 5211-5214.

[18]Zachary, W. W. “An Information Flow Model for Conflict and Fission in Small Groups”. Journal of Anthropological Research, 33(4), 1977: 452-473.

[19]Papadopoulos, S., Kompatsiaris, Y., Vakali, A., & Spyridonos, P. “Community detection in Social Media. Data Mining and Knowledge Discovery, 24(3), 2012: 515-554.

[20]Yang, J., McAuley, J., & Leskovec, J. “Community Detection in Networks with Node Attributes”. Paper presented at the 2013 IEEE 13th International Conference on Data Mining.