articlePhysical Review EJul 9, 2009GREEN OA

Line graphs, link partitions, and overlapping communities

TETim EvansRLRenaud Lambiotte

Imperial College London · London Institute for Mathematical Sciences

PubMed
Indexed inarxivcrossrefpubmed

Abstract

In this paper, we use a partition of the links of a network in order to uncover its community structure. This approach allows for communities to overlap at nodes so that nodes may be in more than one community. We do this by making a node partition of the line graph of the original network. In this way we show that any algorithm that produces a partition of nodes can be used to produce a partition of links. We discuss the role of the degree heterogeneity and propose a weighted version of the line graph in order to account for this.

Citation impact

630
total citations
FWCI
27.84
Percentile
100%
References
25
Citations per year

Authors

2

Topics & keywords

Topics
Keywords
  • Partition (number theory)
  • Computer science
  • Graph partition
  • Community structure
  • Network partition
  • Frequency partition of a graph
  • Graph
  • Complex network
No related works found for this paper.

Funding