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

Support for Multi-layered network with cross node couplings #35

Closed thechargedneutron closed 6 years ago

thechargedneutron commented 6 years ago

Does this implementation support a network where cross connections between nodes across layers exist? (Example connections like Node1 of Layer1 connected to Node 2 of Layer2) . Although the formula for Modularity does not support this but is there a way around? I want to do community detection on such a network (basically a fully connected network). Any suggestions on how to achieve this if not supported by this package?

This issue/feature request has already been raised here. Any suggestion or advice is welcomed.

vtraag commented 6 years ago

Yes, the package should support something like that. Perhaps you can explain your setup more fully, so that I can provide advice on doing that using this package? I am currently on leave, so a detailed reply may have to wait a little bit longer.

thechargedneutron commented 6 years ago

So, the network can be simply stated as follows: between every two nodes (across all layers), I have a weight which lies between 0 and 1. To be precise, each node of each layer has a data associated to it and I find the weights between two nodes by finding the correlation between the data. Hence, it is like a fully connected network with each node connected to all other nodes (number of connections = number of nodes * number of layers - 1).

A sample input with 62 nodes and 5 layers can be seen here.

vtraag commented 6 years ago

I would actually recommend to see the network as a network of n x l nodes (i.e. 62 x 5 = 310) and use the CPM method. That method finds clusters where the average correlation within a cluster is higher than the specified resolution parameter.

Or is there any specific reason why you think of this in terms of layers?

thechargedneutron commented 6 years ago

I am not very sure if we can consider it as a network of n x l nodes. This is because there is a slight difference between the calculation of correlation between nodes of the same layer and between nodes of other layers. Although I will take CPM as last resort, I want to look if other such algorithms are available.

vtraag commented 6 years ago

Ok, that is clear. I would actually still recommend CPM over Modularity for correlation based edge weights. The Modularity null model doesn't make much sense in that context, and may show some problematic behaviour.

Assuming a node in each layer can be in different communities, the terminology used in this package is a "slice". I do provide a function of detecting communities in which case the strength between corresponding nodes in different slices is the same for all nodes, see https://louvain-igraph.readthedocs.io/en/latest/multiplex.html#slices-to-layers for more details.

However, since you have a more complex requirement (have different strengths for corresponding nodes), you will have to construct the appropriate representation yourself. The documentation and the code should provide helpful guide I think. If you don't manage to do so yourself, I can help you once I'm back from my leave.