Edge partitions for overlapping communities in complex networks

We propose to partition the edges of a graph in order to uncover overlapping communities of its nodes. Our approach is based on the construction of different types of weighted line graphs, i.e. graphs whose nodes are the edges of the original graph, that encapsulate differently the relations between the edges. Weighted line graphs provide an alternative, valuable representation of the system's topology, and have important applications in community detection, as the usual node partition of a line graph naturally leads to an edge partition of the original graph. This identification allows us to use traditional partitioning methods in order to address the long-standing problem of the detection of overlapping communities.

We have a simple C++ line graph code which takes in a graph as an edge list and outputs different types of line graph as another edge list. An executable suitable for most Windows machines is included as is basic documentation. This code been used successfully on a graph which produced 5.5e8 stubs in its line graph, though a special machine was used for this as it needs more than 4Gb of RAM memory. On a 4Gb machine a line graph with 4.5e7 stubs was created.We also have java based code which is aprt of a much bigger package.

Discussions, papers and slides from talks:-

• • Paper: Line Graphs, Link Partitions and Overlapping Communities, Phys.Rev.E 80 (2009) 016105 arXiv:0903.2181.

  • Conference Paper: Overlapping Communities, Link Partitions and Line Graphs, a very slightly altered version for ECCS09.

  • Slides from talk What am I? Finding Communities in Networks Using Line Graphs given at University of Warwick Complexity Forum, 28thOctober 2009.

  • Slides from talk Overlapping Communities, Edge Partitions and Line Graphs given at ECCS09 (University of Warwick, 22nd September 2009).

  • Paper: Edge Partitions and Overlapping Communities in Complex Networks, arXiv:0912.4389 (to appear in Eur. Phys. J. B). This covers in more detail the case where one is interested in the different line graphs of a weighted graph.

  • We have a short bibliography of line graph papers.