Modularity and community detection in bipartite networks

The modularity of a network quantifies the extent, relative to a null model network, to which vertices cluster into community groups. We define a null model appropriate for bipartite networks, and use it to define a bipartite modularity. The bipartite modularity is presented in terms of a modularity matrix $\mathbf{B}$; some key properties of the eigenspectrum of $\mathbf{B}$ are identified and used to describe an algorithm for identifying modules in bipartite networks. The algorithm is based on the idea that the modules in the two parts of the network are dependent, with each part mutually being used to induce the vertices for the other part into the modules. We apply the algorithm to real-world network data, showing that the algorithm successfully identifies the modular structure of bipartite networks.

Figure 1

Agreement between model network modules and modules found using the BRIM algorithm. Each point shows the mean normalized mutual information between the model network community groups and those identified using the algorithm, averaged over 100 realizations of the model network. Error bars show the standard error of the mean.

Figure 2

Modules in the Southern women network. The women are represented as open symbols with black labels and the events are represented as filled symbols with white labels. The modules are indicated by the shape of the symbols. Vertices are positioned with coordinates based on the elements of the singular vectors corresponding to the two largest singular values of $\stackrel{\mathrm{̃}}{\mathbf{B}}$; some vertices are repositioned slightly to eliminate overlaps. The vertex partition pictured has the highest modularity we have found for the Southern women network, $Q=0.34554$.

Figure 3

Quality of solutions found in the Scotland corporate interlock network. The modularity $Q$ depends on the allowed number of modules $c$. The points correspond to solutions found using the BRIM algorithm starting from a random initial assignment of vertices to modules. The values on the ordinate indicate the number of modules occupied by at least one vertex in the solution state found by the BRIM algorithm. All points are slightly dithered to better show regions with many similar or identical solutions. The lines show the course of an adaptive search for the correct number of modules to maximize the modularity, terminating at states with the modularity and number of modules shown by the crosses.