11
$\begingroup$

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?

$\endgroup$
  • 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 '12 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$ – adamo Jul 17 '12 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 '12 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 '12 at 13:45
  • $\begingroup$ No apologies needed. My English was not so clear anyway. $\endgroup$ – adamo Jul 17 '12 at 13:49
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.