Methods to find community based on edge centrality

Peng Gang Sun and Yang Yang

Physica A: Statistical Mechanics and its Applications, 2013, vol. 392, issue 9, 1977-1988

Abstract: Divisive algorithms are of great importance for community detection in complex networks. One algorithm proposed by Girvan and Newman (GN) based on an edge centrality named betweenness, is a typical representative of this field. Here we studied three edge centralities based on network topology, walks and paths respectively to quantify the relevance of each edge in a network, and proposed a divisive algorithm based on the rationale of GN algorithm for finding communities that removes edges iteratively according to the edge centrality values in a certain order. In addition, we gave a comparison analysis of these measures with the edge betweenness and information centrality. We found the principal difference among these measures in the partition procedure is that the edge centrality based on walks first removes the edge connected with a leaf vertex, but the others first delete the edge as a bridge between communities. It indicates that the edge centrality based on walks is harder to uncover communities than other edge centralities. We also tested these measures for community detection. The results showed that the edge information centrality outperforms other measures, the edge centrality based on walks obtains the worst results, and the edge betweenness gains better performance than the edge centrality based on network topology. We also discussed our method’s efficiency and found that the edge centrality based on walks has a high time complexity and is not suitable for large networks.

Keywords: Community; Edge centrality; Divisive algorithm (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437112010904
Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:392:y:2013:i:9:p:1977-1988

DOI: 10.1016/j.physa.2012.12.024

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().