search

vtraag / louvain-igraph

Implementation of the Louvain algorithm for community detection with various methods for use with igraph in python.
GNU General Public License v3.0
246 stars 46 forks source link

Change in handling multilayer to allow for single intra-layer partition object #34

Open wweir827 opened 6 years ago

wweir827 commented 6 years ago

We have made some modifications to allow for running multilayer case with only two partition objects : a single igraph with all intralayer edges, and an interlayer igraph. For the intralayer VertexPartition object, the graph and a vector denoting the layer membership for each node is passed for creation. Having a fixed number of partition objects keeps the run time from ballooning for networks with many layers (as shown in the figure below).

To do this, we have modified GraphHelper to keep track of what portion of a given edge is within a layer in a vectorized weight. This allows us to calculate a layer specific null model contribution as is required in the multimodularity framework. We have also overridden several of the methods of MutableVertexPartition.cpp to allow for appropriate book keeping when creating condensed graphs.

image

vtraag commented 4 years ago

@rabisgon, I was thinking: the improvements you make here for running multilayer stuff could actually more easily implemented in the Leiden algorithm in igraph, which only implements CPM/modularity anyhow. The changes that were proposed in this PR would better fit with that implementation I think.