PaperlayerView exact revision on arXiv

Source-linked AI summary

Inferring monopartite projections of bipartite networks: an entropy-based approach

Fabio Saracco, Mika J. Straka, Riccardo Di Clemente, Andrea Gabrielli, Guido Caldarelli, Tiziano Squartini

arXiv:1607.02481v4physics.soc-phcs.SIphysics.data-anq-fin.GN

TL;DR

The paper addresses how to infer same-layer links from bipartite data without losing the structure encoded in the original network. It proposes statistical validation of shared-neighbor similarity using bipartite null models. In a comparison with a forest-inducing method, the validated links had the largest reported overlap, about 82%, though that method provides no explicit statistical control.

  • Problem

    Bipartite projections must recover same-layer relationships while preserving the original structure, but weighted shared-neighbor projections can obscure statistical relevance through degree effects and spurious clusters.

    Source: §I · p. 1

  • Method

    The method links same-layer nodes only when their shared-neighbor similarity is statistically significant against a bipartite null-model benchmark.

    Source: §I · p. 2, §IV · p. 11

  • Results

    About 82% of the links validated by the forest-inducing method overlapped with this procedure's links, but the forest method provides no explicit statistical control.

    Source: algorithms · p. 16

  • Takeaways & Limitations

    Stronger null-model constraints retain more information and yield stricter benchmarks, whereas BiRG preferentially connects high-degree nodes.

    Source: §IV · p. 11

    BiCM computation can be demanding, and proposed Poisson-Binomial approximations have limited applicability and may fail substantially on real bipartite networks.

    Source: §IV · p. 12

Abstract

from arXiv · show

Bipartite networks are currently regarded as providing a major insight into the organization of many real-world systems, unveiling the mechanisms driving the interactions occurring between distinct groups of nodes. One of the most important issues encountered when modeling bipartite networks is devising a way to obtain a (monopartite) projection on the layer of interest, which preserves as much as possible the information encoded into the original bipartite structure. In the present paper we propose an algorithm to obtain statistically-validated projections of bipartite networks, according to which any two nodes sharing a statistically-significant number of neighbors are linked. Since assessing the statistical significance of nodes similarity requires a proper statistical benchmark, here we consider a set of four null models, defined within the exponential random graph framework. Our algorithm outputs a matrix of link-specific p-values, from which a validated projection is straightforwardly obtainable, upon running a multiple hypothesis testing procedure. Finally, we test our method on an economic network (i.e. the countries-products World Trade Web representation) and a social network (i.e. MovieLens, collecting the users' ratings of a list of movies). In both cases non-trivial communities are detected: while projecting the World Trade Web on the countries layer reveals modules of similarly-industrialized nations, projecting it on the products layer allows communities characterized by an increasing level of complexity to be detected; in the second case, projecting MovieLens on the films layer allows clusters of movies whose affinity cannot be fully accounted for by genre similarity to be individuated.

I. INTRODUCTION

The introduction frames projection as a way to infer same-layer relationships while preserving information in bipartite data. It proposes linking nodes only when their shared-neighbor similarity is statistically significant.

I. INTRODUCTION

  • Bipartite projections should recover same-layer relationships while preserving information encoded in the original two-layer structure.This matters when direct measurement of within-layer relationships is impractical.Source: §I · p. 1
  • Naive shared-neighbor projections can become dense, while weighted projections can let high-degree nodes dominate and produce spurious cliques.A single node connected to all nodes on the other layer can induce such a clique.Source: §I · p. 1
  • Threshold-based validation requires an arbitrary cutoff, while a cited null-model approach retains relatively little of the original bipartite structure.The introduction also notes that a benchmark comparison is needed to assess statistical relevance.Source: §I · pp. 1–2
  • The proposed grand canonical method links same-layer nodes if and only if their similarity is statistically significant.The paper describes applications to the World Trade Web and MovieLens after deriving similarity distributions under four bipartite null models and applying multiple-hypothesis testing.Source: §I · p. 2

II. METHODS

The method constructs a layer-specific projection by evaluating pairs of same-layer nodes against a statistical benchmark and retaining significant links. The bipartite network is represented by a binary biadjacency matrix.

II. METHODS

  • A bipartite network is represented by a binary biadjacency matrix whose rows and columns correspond to the two node layers.Links within either layer are not allowed.Source: §II · p. 2
  • For each pair in the layer of interest, the algorithm measures similarity and computes a p-value against a specified null model.The matrix entries encode whether each cross-layer node pair is linked.Source: §II · p. 2
  • The projection links a pair if and only if its p-value is statistically significant, repeating the procedure for every node pair.The method is presented as a sequence of pairwise tests followed by link selection.Source: §II · p. 2

A. Measuring nodes similarity

Node similarity is measured by counting shared neighbors, equivalently counting the V-motifs formed by a node pair and a common neighbor. The naive projection retains these counts but can yield an almost trivial dense topology.

A. Measuring nodes similarity

  • The similarity of two same-layer nodes is the number of shared neighbors, represented as a count of K1,2 bicliques or V-motifs.A single V-motif is present when both nodes connect to the same opposite-layer node.Source: A. Measuring nodes similarity · p. 2
  • Naive projection uses the shared-neighbor count as its weight, and thresholding positive counts produces an almost trivial, densely connected topology.The figure depicts the V-motif used to define the similarity measure.Source: A. Measuring nodes similarity · p. 2, Figure 1 · p. 3

B. Quantifying the statistical significance of nodes similarity

The method assesses observed shared-neighbor counts against exponential-random-graph null models. Under these models, the count follows a Poisson-Binomial distribution, from which the algorithm obtains pair-specific p-values.

B. Quantifying the statistical significance of nodes similarity

  • The four ERG benchmarks constrain total links, degrees on both layers, or degrees on one layer only.They are the BiRG, BiCM, and two partial configuration models, BiPCM_r and BiPCM_c.Source: B. Quantifying the statistical… · p. 3
  • Linear constraints factorize the network probability into pair-specific coefficients, making each possible V-motif an independent Bernoulli trial.The motif count is therefore a sum of independent trials, each with its own probability coefficient.Source: B. Quantifying the statistical… · p. 3
  • The shared-neighbor count follows a Poisson-Binomial distribution, with its probability for n motifs expressed as a sum over n-tuples.The distribution describes the count under the selected null model.Source: B. Quantifying the statistical… · p. 3
  • The p-value is the probability of observing at least the actual number of shared neighbors, and repeating this calculation yields a matrix of pairwise p-values.The authors provide Python code to speed up numerical computation.Source: B. Quantifying the statistical… · pp. 3–4
  • The test is one-tailed for unusually large shared-neighbor counts, but the method can also validate unusually small counts to identify dissimilarity.The reverse validation is presented as an available use of the algorithm.Source: B. Quantifying the statistical… · p. 4

C. Validating the projection

The method uses FDR to select statistically significant links while accounting for multiple tests. A fixed number of retained links is not necessarily compatible with the FDR guarantee.

C. Validating the projection

  • FDR sorts the p-values and selects the largest index î whose p-value satisfies the procedure’s threshold, then rejects hypotheses through that index.The paper uses a single-test significance level of t = 0.01.Source: C. Validating the projection · p. 4
  • The projection links a pair of nodes if and only if its p-value passes the FDR criterion, producing a binary, undirected network.The procedure is presented as a way to control the expected number of incorrectly rejected null hypotheses, even when tests are dependent.Source: C. Validating the projection · p. 4
  • Testing hypotheses independently can overestimate false links, whereas Bonferroni correction can yield very sparse or empty projections as the number of tests grows.The text notes that Bonferroni may also produce too many false negatives when many tests are expected to be significant.Source: C. Validating the projection · p. 4
  • Choosing a fixed number of validated links is not always compatible with retaining an FDR-guaranteeing significance level.The required inequalities can fail when consecutive p-values are close, such as p-value3 = 0.039 and p-value4 = 0.040.Source: C. Validating the projection · pp. 4–5

Community detection

The study uses repeated, randomly reshuffled runs of Louvain to address the algorithm’s dependence on node order, retaining the run with the highest modularity.

Community detection

  • Louvain’s output depends on node order, so the study runs it on randomly reshuffled node orders.It considers N outcomes, where N is the network size.Source: Community detection · p. 5
  • The retained Louvain partition is the one with the maximum modularity among the reshuffled runs.The procedure is described as enhancing detection of partitions with higher modularity.Source: Community detection · p. 5
  • A parallelized Python implementation of the reshuffled Louvain method is available in a public repository.Source: Community detection · p. 5

A. World Trade Web

The World Trade Web projections reveal country communities associated with levels of economic development and product communities associated with complexity. The country-level BiCM structure persists over time, while partial null models provide different degrees of correspondence to the fuller benchmarks.

A. World Trade Web

  • The naïve country projection has link density between 0.93 and 0.95 and clustering coefficients close to 1, yielding trivial structural quantities.Figure 2 contrasts the naïve projection with BiRG- and BiCM-induced projections.Source: A. World Trade Web · pp. 5–6, Figure 2 · p. 5
  • The BiRG country projection separates raw-material-dependent economies from a connected component, but is described as a meaningful yet too-rough filter.The BiRG reference probability is approximately 0.13 for every country-product pair.Source: A. World Trade Web · pp. 6–7
  • The BiCM country projection identifies communities of advanced, developing, and raw-material-exporting economies, with Australia, New Zealand, Chile, and Argentina forming a seafood-export community of their own.The figure presents the Louvain communities for the BiCM-induced projection in 2000.Source: Figure 3 · p. 6, A. World Trade Web · p. 7
  • The BiCM country communities form a hierarchy, with developing economies seemingly intermediate between advanced economies and raw-material exporters; this mesoscopic pattern persists across the dataset’s years.The 2000 and 2008 snapshots also show changing country groupings and structural roles, including Germany’s star-like connections and Austria’s and Japan’s high betweenness.Source: Figure 4 · p. 6, A. World Trade Web · pp. 7–8
  • The country-degree-only BiPCMr projection yields less detailed results compatible with BiCM, whereas the product-degree-only BiPCMc projection is close to BiRG and adds little information.Figure 5 depicts the BiPCMr-induced country projection and its similar mesoscopic patterns.Source: Figure 5 · p. 7, A. World Trade Web · pp. 8–9
  • The BiPCMc product projection identifies communities including machinery, transportation, chemicals, electronics, textiles, and live animals, with a partition described as stable over time.The figure’s larger communities also include fabrics, clothes, wooden products, and live animals.Source: Figure 6 · p. 8, A. World Trade Web · p. 9
  • Product communities separate into high- and low-complexity groups, with advanced economies mainly trading in the former and developing economies mainly trading in the latter.The figure compares the intensity of the two economy groups’ activity across product communities.Source: Figure 7 · p. 8, A. World Trade Web · p. 9

B. MovieLens

MovieLens ratings were binarized as favorable when users gave a movie at least 3 out of 5. Among the three projections, BiCM reveals a complex movie-community structure, including affinities not fully captured by genre labels.

B. MovieLens

  • MovieLens 100k contains ratings from 943 users for 1,559 movies; ratings of at least 3 were treated as favorable.The data were collected from September 19, 1997 through April 22, 1998.Source: B. MovieLens · p. 9
  • BiCM, unlike the naïve and BiRG projections, reveals a composite movie-community structure with modularity Q ≃0.58.The structure appears as diagonal blocks in the BiCM panel; the naïve projection is dense, while BiRG yields a large component of popular movies.Source: B. MovieLens · pp. 9–10, Figure 8 · p. 9
  • BiCM communities partition movies sharply when genres are considered in combinations, and capture a 1996-release cohort despite its heterogeneous genres.The cohort’s similarity is linked to users’ curiosity about yearly new releases, rather than to a shared genre.Source: B. MovieLens · p. 11
  • Detected clusters include family movies, horror-trait titles distinct from more popular “cult mass” films, and movies inspired by books or theatrical plays.The family cluster combines Animation, Children’s, Fantasy, and Musical; the cult-mass cluster has similar genres to the horror-trait group, with Crime replacing Horror and Thriller.Source: B. MovieLens · p. 11
  • Other detected communities comprise foreign and US independent films, plus “classic” Hollywood movies associated with iconic actors or master directors.The foreign and independent films form one niche cluster, while book- or play-inspired movies and documentaries form another.Source: B. MovieLens · p. 11
  • The BiPCMr projection yields a coarser partition of three macro-groups: authorial films, recent mainstream blockbusters, and independent or niche movies.Examples of the authorial group include classic Hollywood, Hitchcock, Kubrick, and Spielberg films; the blockbuster group includes Star Trek, Star Wars, Indiana Jones, and Batman sagas.Source: B. MovieLens · p. 11
  • Projecting onto users also detects communities, but none seems accurately described by the supplied age, gender, occupation, or US ZIP-code indicators.The authors suggest that user tastes may correlate with sociometric variables not yet identified.Source: B. MovieLens · p. 11

IV. DISCUSSION

The discussion compares four bipartite null models by how much degree information they retain, finding that layer-specific degree constraints can approximate the full BiCM. It also cautions that computing the exact BiCM can be demanding and that approximations may lose validated links.

IV. DISCUSSION

  • The BiRG uses the same distribution for every node pair and favors high-degree nodes, while stronger constraints retain more information and produce stricter benchmarks.The BiPCM constraining degrees on the opposite layer also gives a homogeneous benchmark; the same-layer BiPCM induces pair-specific distributions and can approximate the BiCM.Source: §IV · pp. 11–12
  • Constraining degrees on the layer being projected provides a benchmark that accounts for node heterogeneity; partial models can approximate the BiCM when degree heterogeneity is reduced.The discussion recommends constraining at least the projected layer's degree sequence, except when constraints are redundant.Source: §IV · pp. 11–12
  • Exact BiCM computation can be demanding, and Poisson-Binomial approximations have limited applicability and may fail substantially on real networks.The authors provide Python code to speed p-value computation while retaining exact distributions.Source: §IV · p. 12

Appendix A: the Poisson-Binomial distribution

  • The Poisson-Binomial distribution models a sum of independent Bernoulli trials with potentially different success probabilities, reducing to a Binomial distribution when those probabilities coincide.For projection, the relevant tail probability is the survival distribution function above the observed V-motif count.Source: Appendix A · p. 12

Poisson-Binomial distribution

  • A Binomial approximation is available when trial probabilities coincide, or when their spread is sufficiently narrow; Poisson and Gaussian approximations target small and large expected success counts, respectively.The passage gives σ/µ < 0.5 as a condition for the narrow-spread Binomial approximation.Source: Poisson-Binomial distribution · p. 13
  • For the WTW projection at t = 0.01 in 2000, the skewness-corrected Gaussian approximation loses ≃20% of statistically significant links relative to the full Poisson-Binomial distribution.The appendix notes that the skewness correction improves on the Gaussian approximation when event counts are small, but this comparison shows a limitation in the WTW setting.Source: Poisson-Binomial distribution · p. 13

1. Bipartite Random Graph model

  • Under BiRG, equal link probabilities make shared V-motif counts Binomial, with the probability determined by the squared bipartite link probability.Source: §1 · p. 14

3. Bipartite Partial Configuration Models

  • The BiCM constrains both degree sequences, while partial models constrain one layer; BiPCMc can approximate the BiCM when top-layer degree heterogeneity is reduced.BiPCMr's shared V-motif distribution is Poisson-Binomial; the discussion also reports that BiPCM performance depends on which layer's degrees are constrained.Source: §IV · p. 11, §2 · p. 14, §3 · pp. 14–15

Appendix D: comparing different projection

The WTW comparison finds that methods using Bonferroni correction yield fewer validated links, while the forest-inducing method has the greatest overlap with the proposed procedure. That overlap does not itself provide statistical control.

algorithms

  • The method in outputs an empty network across the dataset, while the method in validates only a tenth of links among advanced economies.The authors suspect the large number of simultaneous hypotheses makes the correction for too severe.Source: algorithms · p. 16
  • The method in [13] validates a subset of links found by FDR control, yielding a less informative WTW community structure.The authors attribute this to its use of Bonferroni correction.Source: algorithms · p. 16
  • ≃82% overlap with the proposed procedure is observed for the forest-inducing method, which does not explicitly control statistical significance.The authors suggest the overlap may reflect selection of events with many shared co-occurrences; a forest-like topology does not guarantee the most significant events.Source: algorithms · p. 16

Related papers

Loading 1607.02481v4…