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:-
Tim Evans,
Aug 17, 2010, 1:49 AM