PaperlayerView exact revision on arXiv

Source-linked AI summary

Module identification in bipartite and directed networks

R. Guimera, M. Sales-Pardo, L. A. N. Amaral

arXiv:physics/0701151v2physics.data-anphysics.bio-phphysics.soc-ph

TL;DR

The paper addresses limited methods for module identification in bipartite and directed networks, including failures caused by ignoring link direction or losing bipartite information. It proposes bipartite modularity, random benchmark networks, and a bipartite representation for directed networks, finding that unweighted projection is unreliable while the direct bipartite approach is preferable when team sizes vary.

  • Problem

    Module-identification methods are limited for bipartite and directed networks, and disregarding direction can fail when modules depend on incoming and outgoing links.

  • Method

    The paper introduces a bipartite modularity, random bipartite networks with prescribed modular structure, and a bipartite representation for directed unipartite networks.

  • Results

    The unweighted projection approach is unreliable, while weighted projection and bipartite approaches perform similarly and become equivalent when all teams have the same size.

  • Takeaways & Limitations

    The bipartite approach is preferable when the network’s modular structure is unknown, especially because team-size variation can produce different projection and bipartite results.

  • Takeaways & Limitations

    The analysis identifies modules independently within the two node sets rather than grouping actors and teams simultaneously.

Abstract

from arXiv · show

Modularity is one of the most prominent properties of real-world complex networks. Here, we address the issue of module identification in two important classes of networks: bipartite networks and directed unipartite networks. Nodes in bipartite networks are divided into two non-overlapping sets, and the links must have one end node from each set. Directed unipartite networks only have one type of nodes, but links have an origin and an end. We show that directed unipartite networks can be conviniently represented as bipartite networks for module identification purposes. We report a novel approach especially suited for module detection in bipartite networks, and define a set of random networks that enable us to validate the new approach.

I. BACKGROUND

The paper formulates bipartite module identification as finding actor groups linked through shared teams, while requiring algorithms to infer partitions, module counts, and sizes. It introduces a bipartite modularity based on deviations from random co-membership expectations.

  • Bipartite networks divide nodes into two non-overlapping sets, with every link joining nodes from opposite sets.
  • The target is to identify actor modules whose members are closely connected through co-participation in many teams.
  • A valid algorithm must be network independent and infer the partition, number of modules, and module sizes from the links.
  • Projection-based methods can lose original bipartite information, including team sizes, while hierarchical methods may not specify module boundaries.
  • The proposed bipartite modularity compares observed actor co-membership counts with random expectations and turns module identification into combinatorial optimization.

III. MODEL BIPARTITE NETWORKS WITH MODULAR STRUCTURE

The paper constructs random bipartite networks with predefined modular structure by assigning actors to modules and generating teams with tunable within-module preference. Team homogeneity p controls the strength of the planted structure.

  • The model therefore provides random networks with prescribed modular structure for evaluating module-identification accuracy.
  • The model divides actors into NM modules and creates NT teams whose members are more likely to come from a designated module.
  • Each team is created by selecting its size, assigning a module color, and filling positions with actors according to the homogeneity parameter p.
  • At p = 1, teams contain actors from one module, whereas p = 0 produces perfectly mixed actors and no modular structure.

IV. RESULTS

The study compares unweighted projection, weighted projection, and direct bipartite approaches for detecting modules, maximizing each modularity with simulated annealing. The comparison is designed to assess how the representations affect module identification.

  • The unweighted projection builds an actor-only network and applies the standard unipartite modularity.
  • The weighted projection connects actors who share teams and weights each link by their number of shared teams.
  • The bipartite approach applies the proposed modularity directly to the complete bipartite network.
  • All three approaches maximize modularity with simulated annealing, which is described as accurate but too slow for very large networks.

A. Model bipartite networks

The model experiments compare recovered partitions with predefined module structure using mutual information. The baseline networks use four equal actor modules and 128 teams of size 14.

  • Algorithm performance is assessed by comparing its recovered partition with the predefined group structure.
  • Mutual information IAB equals 1 for identical partitions and 0 for uncorrelated partitions.
  • The simplest model uses equal-sized modules, equal-sized teams, and equally probable team colors.
  • Unless otherwise stated, networks contain NM = 4 modules with 32 actors each and NT = 128 teams of size m = 14.

1. Team homogeneity

As team homogeneity increases, weighted projection and bipartite approaches identify modules much more accurately than unweighted projection. The two former approaches perform indistinguishably across the reported homogeneity range.

  • 1. Team homogeneity: At p = 1, all reasonable algorithms perfectly identify the modular structure, whereas at p = 0 they return random partitions.The mutual information is I = 1 at p = 1 and I = 0 at p = 0.
  • 1. Team homogeneity: The unweighted projection performs systematically and significantly worse than weighted projection and bipartite approaches for all p values.
  • 1. Team homogeneity: Weighted projection and bipartite approaches yield indistinguishable results.

2. Number of teams and average team size

The number of teams changes the information available for module identification and affects the approaches differently. More teams improve weighted projection and bipartite methods but make unweighted projections increasingly dense.

  • 2. Number of teams and average team size: For weighted projection and bipartite algorithms, increasing the number of teams increases available information and makes module identification easier.With sufficiently large NT, the signal-to-noise ratio can exceed 1 even for very small p.
  • 2. Number of teams and average team size: As the number of teams increases, unweighted projection becomes denser and eventually fully connected, preventing useful information extraction.
  • 2. Number of teams and average team size: Weighted projection and bipartite algorithm performance remains indistinguishable as the number of teams varies.

3. Module size heterogeneity

Module-size heterogeneity is represented through ordered module-size ratios, while team-size distributions expose a distinction between bipartite and weighted projection approaches. Equal team sizes make their modularity formulations equivalent, but unequal sizes can separate them.

  • 3. Module size heterogeneity: The parameter h is the ratio of consecutive module sizes after ordering modules so that S1 ≥ S2 ≥ ··· ≥ SNM, with integer rounding.
  • 3. Module size heterogeneity: Teams are selected with probabilities proportional to corresponding module size so actors participate, on average, in the same number of teams.
  • 3. Module size heterogeneity: Weighted projection and bipartite approaches perform similarly and clearly outperform unweighted projection for all h values.
  • 3. Module size heterogeneity: The bipartite approach accounts for team-size distributions, whereas weighted projection disregards them and excludes teams with m = 1.
  • 4. Team size distribution: When all teams have the same size, bipartite modularity reduces to weighted unipartite modularity up to an irrelevant additive constant.
  • 4. Team size distribution: Unequal team sizes explain differences between weighted projection and bipartite approaches, and Eq. (5) is generally preferred because it explicitly includes team-size distributions.

B. Southern women dataset

In the Southern women-event bipartite network, unweighted projections fail to recover the true modular structure because central events make the projections very dense. Weighted projection and bipartite approaches instead recover the two-module structure closely matching established partitions.

  • B. Southern women dataset: The dataset records women’s attendance at social events and forms a women-event bipartite network.
  • B. Southern women dataset: Unweighted projections of both women and events fail to capture the true modular structure because central events make the projections very dense.Events attended by most women connect most pairs of women in the projection.
  • B. Southern women dataset: Weighted projection and bipartite approaches yield the same results and recover the network’s two-module structure.Except for one woman, the partition matches the ethnographers’ subjective partition and agrees with some supervised algorithms.

V. MODULES IN DIRECTED NETWORKS

Directed networks can be represented as bipartite networks by splitting each node into outgoing and incoming counterparts, allowing modules based on direction-specific connections to be identified. In the model example, this approach recovers both in-modules and out-modules, whereas ignoring direction fails.

  • Bipartite representation: Each directed node i becomes two bipartite nodes, A_i and B_i, with a directed edge i→j represented by an edge A_i–B_j.The A nodes encode outgoing roles and the B nodes encode incoming roles.
  • Direction-specific modules: The model network has different module partitions according to outgoing versus incoming links.Outgoing links group nodes 1–12 and 13–24, while incoming links group nodes 1–6 and 13–18 versus 7–12 and 19–24.
  • Direction-specific modules: The bipartite representation makes the directed network’s modular structure apparent and enables the UWP, WP, and B approaches to identify in-modules and out-modules correctly.This result is shown in Fig. 4(d).
  • Direction-specific modules: Disregarding link direction produces modules that fail to capture the network’s modular structure.The direction-disregarding result is shown in Fig. 4(e).

VI. DISCUSSION

The discussion positions the bipartite modularity framework as interpretable, extensible across optimization methods, and useful for studying nested structure. It also argues that the bipartite approach is preferable when team sizes vary or the modular structure is unknown.

  • Optimization: The bipartite modularity can be optimized with simulated annealing, greedy search, extremal optimization, or spectral methods.Simulated annealing was chosen for best possible accuracy, while faster alternatives are available.
  • Hierarchical structure: Sampling all local modularity maxima can reveal hierarchical nested modules and submodules within each node set.The most modular partition need not represent the most relevant division of nodes.
  • Comparison of approaches: The unweighted projection approach is considered unreliable and capable of producing incorrect results in most situations.The authors state that it should not be used.
  • Comparison of approaches: Weighted projection and bipartite approaches perform similarly and are equivalent when all teams have the same size.They can differ noticeably when team sizes are not uniform.
  • Comparison of approaches: The bipartite approach is preferable when the network’s modular structure is unknown because it has a more straightforward interpretation.This preference is stated specifically for cases with nonuniform team sizes and unknown structure.

APPENDIX A: WEIGHTED UNIPARTITE MODULARITY

For bipartite networks with uniform team sizes, the paper shows that its bipartite modularity is equivalent to weighted projection modularity, up to a partition-independent constant.

  • Networks with uniform teams: When every team has the same size m, bipartite modularity is equivalent to weighted projection modularity.The weighted projection assigns each pair of actors a weight equal to their number of shared teams.
  • Networks with uniform teams: Each actor’s team participation increases the total projected link weight by m−1.This identity supplies the constant team-size factor used in the equivalence derivation.
  • Networks with uniform teams: A term independent of the partition can be discarded, leaving the bipartite and weighted modularity objectives equivalent up to an irrelevant constant.The equivalence follows after summing over modules.
Loading physics/0701151v2…