PaperlayerView exact revision on arXiv

Source-linked AI summary

Modularity and community detection in bipartite networks

Michael J. Barber

arXiv:0707.1616v3physics.data-ancond-mat.stat-mechphysics.soc-ph

TL;DR

Bipartite networks require community-detection methods that respect their two disjoint vertex sets, since unipartite projections lose information. The paper defines a degree-preserving bipartite null model and modularity, then develops BRIM using the modularity matrix’s spectral structure. Applied to real-world networks, BRIM identifies modular structure, but its results can depend on initialization and the modularity has an expected resolution limit.

  • Problem

    Unipartite projections of bipartite networks intrinsically lose information, motivating modularity and module-identification methods that preserve bipartite structure.

  • Method

    The paper defines bipartite modularity with a structure-preserving null model and develops BRIM by alternately inducing module assignments across the two vertex sets.

  • Results

    BRIM identified modular structures in real-world networks, including a four-module Southern Women solution with Q = 0.34554.

  • Takeaways & Limitations

    Incorporating bipartite structure into the mathematical and computational treatment provides a useful basis for identifying modules in both network parts.

  • Takeaways & Limitations

    The bipartite modularity is expected to have a resolution limit that can hide substructures in large networks.

Abstract

from arXiv · show

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 B; some key properties of the eigenspectrum of 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.

I. INTRODUCTION

The paper motivates community detection in bipartite networks, whose two-part structure makes standard null models and unipartite projections inadequate. It proposes a bipartite modularity matrix and BRIM algorithm to identify modules in both vertex sets.

  • Motivation: Community detection enables quantitative study of subnetworks whose properties may differ from those of the aggregate network.The paper illustrates this with topically related web pages forming modules in the World Wide Web.
  • Motivation: Modularity measures within-module connectivity relative to a null model, but exact optimization is generally intractable because possible partitions grow rapidly.The choice of null model therefore directly affects the modularity value and optimization problem.
  • Bipartite networks: Bipartite networks contain two disjoint vertex sets with no within-set edges, representing affiliation or interaction relations such as actors and events.This structure is common in natural, social, and technological networks.
  • Bipartite networks: Unipartite projections can illuminate bipartite structure but intrinsically lose information about the original two-mode network.The paper therefore treats the bipartite structure directly rather than relying only on projected networks.
  • Contribution: The paper proposes a bipartite modularity matrix, analyzes its eigenspectrum, and introduces BRIM for mutually dependent module identification across both network parts.BRIM stands for bipartite, recursively induced modules.
  • Related work: The paper positions its contribution against prior work that focused modularity on one part of a bipartite network at a time.Earlier work also noted the possibility of classifying both partite sets simultaneously.

II. BIPARTITE MODULARITY

The paper constructs bipartite modularity by imposing the network’s two-part structure on the null model and modularity matrix. The resulting formulation preserves degree constraints while excluding same-part edges.

  • Modularity matrix: Modularity can be expressed using an index matrix S whose binary columns encode module membership, with each vertex assigned to exactly one module.The matrix formulation combines S with the modularity matrix B to evaluate a partition.
  • Null model: The null model constrains expected vertex degrees to match actual degrees, extending the standard degree-preserving null-model principle to bipartite networks.The expected number of null-model edges must also equal the number of actual edges.
  • Null model: The bipartite null model preserves the adjacency matrix’s block off-diagonal structure, assigning zero likelihood to same-color edges.This reflects the defining constraint that vertices within the same part cannot be adjacent.
  • Modularity matrix: The bipartite modularity matrix B has zero diagonal blocks, so meaningful positive or negative modularity contributions arise only from pairs in distinct vertex sets.The cross-part block is represented by ˜B = ˜A − ˜P.
  • Modularity measure: The paper fully defines bipartite modularity by combining the modularity expression with the bipartite degree-preserving null model.The formulation parallels Newman’s matrix-based development for unipartite networks.

A. Spectral Methods for Module Identification

The paper reviews spectral approaches for modularity optimization and identifies their limitations for bipartite networks. It then motivates a specialized method that exploits bipartite structure rather than relying only on generic spectral partitioning.

  • Spectral approaches: Generic spectral partitioning assigns vertices to predetermined-size groups, which is problematic when real-world community number and sizes are unknown.This limitation motivates methods based on modularity rather than fixed-size partitioning.
  • Spectral approaches: Spectral optimization of modularity uses the modularity matrix and is conceptually better aligned with community structure than minimizing between-group edges.The approach can use the leading eigenvector, called the Newman vector, for two-group assignments.
  • Two-module optimization: For two modules, vertices are assigned according to the signs of the leading modularity eigenvector to maximize the modularity approximation.Positive components select one module and negative components select the other.
  • Alternative approach: Multiple eigenvectors can support more than two modules, but the paper does not use that vector-partitioning or recursive-bipartitioning route.Instead, it develops an alternative technique that capitalizes on the bipartite character of the network.

B. Module Identification in Bipartite Networks

For bipartite networks, the modularity eigenproblem reduces to the singular-value structure of the asymmetric block ˜B. This enables module assignments across both vertex sets and motivates BRIM’s alternating optimization.

  • Bipartite spectral structure: The bipartite modularity eigenvalue problem yields paired relations ˜Bv_i = λ_i u_i and ˜B^T u_i = λ_i v_i.The vectors u_i and v_i correspond to the two vertex sets.
  • Bipartite spectral structure: Every eigenvalue λ_i of B is paired with −λ_i, so only positive eigenvalues can contribute positively to modularity.The SVD of ˜B automatically focuses on the relevant positive singular values and vectors.
  • Community bound: The number of communities is at most the smaller of the two vertex-set sizes because the rank of ˜B is less than both dimensions.This bound follows from the zero row and column sums induced by degree matching.

C. Recursive Identification of Bipartite Modules

The method alternates module assignments between the two vertex sets, using bipartite modularity contributions to recursively induce structure in the other set. BRIM monotonically improves modularity but generally reaches a local rather than global maximum, and its efficacy is evaluated on model networks using normalized mutual information.

  • Recursive Identification of Bipartite Modules: Given fixed blue-module assignments, each red vertex is assigned to the module with the largest corresponding modularity contribution.The assignment is made by selecting the maximum entry in the red vertex's row of the transformed modularity matrix.
  • Recursive Identification of Bipartite Modules: Given fixed red-module assignments, each blue vertex is analogously assigned to the module with the largest corresponding modularity contribution.The same row-wise maximization principle is applied to the transformed matrix for blue vertices.
  • Recursive Identification of Bipartite Modules: BRIM alternates these two maximization procedures, with each vertex set recursively inducing the other into modular structures.The procedure is iterative and maximizes the bipartite modularity Q.
  • Recursive Identification of Bipartite Modules: Q never decreases during BRIM iterations, so the algorithm reaches a partition at a maximum encountered by the procedure, generally a local rather than global maximum.The previous partition can always be retained, guaranteeing nondecrease; global maximization is not assured.
  • Model-network evaluation: The model network contains Nmod modules with Nred red and Nblue blue vertices, linking same-module opposite-color pairs with pin and different-module pairs with pout.No within-color edges are allowed, and the model's modular behavior depends on the relationship between pin and pout.
  • Model-network evaluation: BRIM is evaluated by normalized mutual information between assumed and detected partitions, where 1 indicates a match and 0 indicates independence.The model uses Nmod = 5, Nred = 12, Nblue = 8, producing n = 100 vertices; results average Inorm over 100 instantiations with standard-error bars.

D. Determining the Number of Modules

The number of modules is not determined automatically by basic BRIM and can lead to poor local optima when the allowed count is badly chosen. An adaptive search instead varies the module count, using modularity to bracket and refine a maximum with logarithmic scaling in network size.

  • Determining the Number of Modules: BRIM does not determine how many modules should be used, and assigning initially unique modules can be resource intensive.When vertices greatly outnumber modules, this strategy may terminate at low-quality local maxima far from the true module count.
  • Adaptive search: The adaptive procedure starts at c = 1 with Q = 0, repeatedly doubles c while Q increases, and locally reoptimizes using BRIM.Each step partially reuses the preceding vertex-to-module assignment.
  • Adaptive search: After Q decreases, the search switches from extrapolation to bisection within the interval containing the modularity maximum.New module counts are tested to reduce the interval containing the putative maximum.
  • Adaptive search: The adaptive BRIM algorithm identifies the appropriate module count cmax in a number of steps that scales logarithmically with the number of vertices.The procedure adapts the allowed module count by combining doubling with interval refinement.

IV. RESULTS

The paper applies BRIM to two real-world bipartite networks: interactions among women at social events and corporate interlocks in Scottish firms.

  • IV. RESULTS: BRIM is applied to a social-event interaction network involving women in the American Deep South and to a corporate-interlock network of Scottish firms.Both datasets are available in Pajek format.

A. Southern Women Event Participation

The Southern women dataset represents 18 women and 14 social events as a connected bipartite network. BRIM identified modular structures, with the strongest solution reaching Q = 0.34554 and generally outperforming unipartite-projection-based groupings.

  • The dataset contains 18 women participating in 14 social events, forming a connected bipartite network.
  • BRIM identified modular structures under all three event-initialization strategies: one module, one module per event, and random assignment.The authors tested these initialization strategies because solution quality can depend on the initial state.
  • The figure displays four modules using symbol shapes, with women as open symbols and events as filled symbols; coordinates derive from singular vectors of ˜B.The pictured partition is reported as the highest modularity found for this network.
  • The BRIM groupings were comparable to previous Southern women analyses, including divisions based on ethnographic knowledge and consensus across 21 studies.A modified Doreian partition increased modularity from 0.29390 to 0.32950, approaching the best BRIM and spectral solutions.
  • Compared with unipartite projections, the bipartite analysis evaluates and assigns modules to both women and events, preserving structure that projection-based analyses can lose.The best women-only projection division had negative standard unipartite modularity, whereas projection-derived assignments were generally inferior under bipartite modularity.

B. Scotland Corporate Interlock

The Scotland corporate interlock network contains firms connected to directors through shared board memberships. BRIM found that restricting the allowed number of modules improved the search, yielding roughly twenty community groups in the largest component.

  • The dataset records 108 Scottish firms and 136 individuals with multiple directorships during 1904–5.The bipartite network connects firms to their board members.
  • The analyzed largest component contains 131 directors and 86 firms, allowing as many as 86 modules.
  • Q = 0.56634 for assigning every director to a unique module and Q = 0.39873 for assigning all directors to one module.Both extreme assignments captured some modular character but were poor relative to solutions found from random initializations.
  • The best solutions emerged when the allowed number of modules was restricted to fewer than thirty.Restricting the search traded excluded higher-modularity possibilities for more effective exploration of the remaining assignments.
  • Adaptive BRIM runs typically allowed a number of modules within 10% of the number actually found, and two runs exceeded all larger fixed-c trials in modularity.
  • The largest component has roughly twenty community groups, substantially fewer than its 131 directors or 86 firms.The result provides a starting point for studying community structures of firms or directors, with sector and capital information left for fuller analysis.

V. CONCLUSIONS

The paper incorporates bipartite structure into modularity and community detection through a specialized matrix treatment and the BRIM algorithm. It demonstrates effectiveness on real-world networks while noting an expected resolution-limit constraint.

  • Conclusions: The bipartite modularity is formulated through an asymmetric submatrix and singular value decomposition rather than the full matrix’s spectral decomposition.This adapts matrix-based methods to the two-part structure of bipartite networks.
  • Conclusions: BRIM uses properties of the asymmetric submatrix to identify modules in bipartite networks.The algorithm is specifically designed for bipartite networks and was applied to real-world data.
  • Conclusions: The algorithm demonstrated effectiveness on real-world networks while also revealing limitations.The conclusion reports empirical effectiveness but does not quantify it in the supplied passage.
  • Conclusions: The authors expect bipartite modularity to have a resolution limit similar to unipartite modularity, although they did not demonstrate it.The anticipated consequence is that modules in large networks may contain hidden substructures requiring deeper investigation.
  • Conclusions: Fixing module assignments in one network part creates a stable modularity landscape for partitioning vertices in the other part.This mutually conditioned treatment is how BRIM exploits the bipartite structure computationally.
Loading 0707.1616v3…