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?
5
-
2$\begingroup$ How would one "restrict the detection of communities just on one of the two modes" without knowing in advance which nodes make up the modes? It seems circular. $\endgroup$– hardmath ♦Jun 7, 2012 at 12:27
-
$\begingroup$ In a bipartite network you already know the two modes. So for example if half the nodes that belong to mode "A" link with a node that belongs to mode "B" then you have a community there. $\endgroup$– adamoJul 17, 2012 at 8:57
-
$\begingroup$ If you know in advance which nodes belong to each mode, then that answers my question about how to restrict the detection. However your example and its implied notion of "community" is unclear. If a vertex in a bipartite graph does not link to any vertex of the opposing mode, then it doesn't link to any vertex (it would be isolated). In a connected bipartite graph every mode "A" vertex links to some mode "B" vertex and vice versa. "Community" would typically mean something more than a connected subgraph. $\endgroup$– hardmath ♦Jul 17, 2012 at 10:41
-
$\begingroup$ On reflection I suspect your "link with a node" meant to link with a single common node, giving a clique in the projected graph (see Answer), and thus "a community there". Apologies for not grasping your point at first reading. $\endgroup$– hardmath ♦Jul 17, 2012 at 13:45
-
$\begingroup$ No apologies needed. My English was not so clear anyway. $\endgroup$– adamoJul 17, 2012 at 13:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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:
Multipartite graphs are usually reduced to unipartite projections of each vertex class. For instance, from the bipartite network of scientists and papers one can extract a network of scientists only, who are related by coauthorship.
