Are there any algorithms for community detection for bipartite graphs (2-mode networks) implemented in igraph, networkX, R or Python etc.? In particular, is there such an implementation in which one would be able to restrict the detection of communities just on one of the two modes?
Tell me more
×
Computational Science Stack Exchange is a question and answer site for
scientists using computers to solve scientific problems. It's 100% free, no registration required.
|
|
The phrase "community detection" is loosely defined as partitioning the vertices of a graph into "communities" such that each has members more densely linked to one another than to members of other "communities". Our first task is to ascertain what this should mean in the case of a bipartite graph, which by definition consists of two "modes" such that members of one mode are linked only to members of the other mode. It may be expressed, at least for simple graphs, as having an adjacency matrix of special block structure: $$A = \begin{pmatrix} 0 & B \\ B^T & 0 \end{pmatrix}$$ It seems to me that the most pertinent interpretation of "restrict the detection of communities just on one of the two modes" would apply said algorithms to the "projected" graphs corresponding to blocks of $A^2$, i.e. the first mode with adjacency matrix $BB^T$ and the second mode with adjacency matrix $B^TB$. Note that even if the original bipartite graph is simple (so that $A$ is binary), the projected graphs will generally be multi-graphs. Fortunately igraph has a method to construct these for us. We are equally fortunate in that the igraph community detection algorithms and related have been "updated to handle weighted graphs" (such as multi-graphs). S. Fortunato (2010) surveys community detection criteria (Community detection in graphs) and their use with bipartite and multipartite networks. The interpretation I suggest above is articulated on page 8:
|
||||
|
|
