PaperlayerView exact revision on arXiv

Source-linked AI summary

An information-theoretic, all-scales approach to comparing networks

James P. Bagrow, Erik M. Bollt

arXiv:1804.03665v3cs.SIcs.ITmath.ITphysics.data-anphysics.soc-ph

TL;DR

Meaningfully comparing networks is an open problem, particularly when they do not share nodes. This paper compares them through graph-invariant network portraits and Jensen–Shannon divergence, with reported results distinguishing networks within and across ensembles and revealing structure in real networks.

  • Problem

    Researchers increasingly need meaningful comparisons across multiple networks, including networks without shared node sets, while standardized quantitative benchmarks for comparison methods are lacking.

    Source: §1 · p. 2, §5 · p. 17

  • Method

    The Network Portrait Divergence compares networks using graph-invariant portraits and an information-theoretic divergence, with a generalization for weighted networks.

    Source: §1 · p. 3, §5 · p. 16

  • Results

    Within-ensemble ER and BA realizations had relatively small divergence, whereas ER-to-BA comparisons exceeded 0.6; Arabidopsis layers also showed distinct pairwise relationships.

    Source: §4.1 · p. 10, §4.3 · p. 13

  • Takeaways & Limitations

    The measure applies without equal node sets or connectivity assumptions and supports comparisons of directed, undirected, unweighted, and weighted networks.

    Source: §5 · p. 16

    The work does not establish a standardized systematic benchmark suite, which the authors consider beyond its scope.

    Source: §5 · p. 18

Abstract

from arXiv · show

As network research becomes more sophisticated, it is more common than ever for researchers to find themselves not studying a single network but needing to analyze sets of networks. An important task when working with sets of networks is network comparison, developing a similarity or distance measure between networks so that meaningful comparisons can be drawn. The best means to accomplish this task remains an open area of research. Here we introduce a new measure to compare networks, the Network Portrait Divergence, that is mathematically principled, incorporates the topological characteristics of networks at all structural scales, and is general-purpose and applicable to all types of networks. An important feature of our measure that enables many of its useful properties is that it is based on a graph invariant, the network portrait. We test our measure on both synthetic graphs and real world networks taken from protein interaction data, neuroscience, and computational social science applications. The Network Portrait Divergence reveals important characteristics of multilayer and temporal networks extracted from data.

1 Introduction

Comparing multiple networks is increasingly common, but meaningful comparison remains an open task, including when networks have different node sets. The paper introduces an information-theoretic approach that compares networks through graph invariants.

1 Introduction

  • Network comparison matters across applications including brain networks, temporal-network evolution, protein classification, and model evaluation.Comparison measures can also support clustering for network aggregation and serve as objective functions for fitting models to data.Source: §1 · p. 2
  • Comparisons that require shared node sets exclude cases where networks have identical topologies but different nodes; this work allows comparison without node correspondence.Shared node sets can still be appropriate when correspondences between layers are the focus.Source: §1 · p. 2
  • Graph invariants let comparisons focus on topology rather than graph encoding, and can be represented as distributions compared using information-theoretic divergences.The Jensen–Shannon divergence is symmetric and normalized, making it a suitable choice for comparing the paper’s graph-invariant distributions.Source: §1 · pp. 2–3
  • The paper introduces a novel graph-invariant distribution and uses Jensen–Shannon divergence to compare networks through those invariants.The approach is presented as principled and general-purpose for network comparison.Source: §1 · p. 3

2 Network portraits

Network portraits encode network structure in a graph-invariant matrix, supporting visualization and comparison. The paper also describes an information-theoretic alternative to an earlier portrait-comparison method.

2 Network portraits

  • A network portrait B has entries Bℓ,k counting nodes with k nodes at shortest-path distance ℓ, with ℓ spanning zero through the graph diameter.The portrait is unchanged by node ordering or labeling.Source: §2 · pp. 3–4
  • Portrait rows encode network structure at multiple scales, including node count, degree distribution, next-nearest neighbors, and shortest-path counts.The zeroth row stores N, the first captures P(k), and higher rows capture more distant neighborhoods.Source: §2 · pp. 4–5
  • Portraits distinguish random graphs from highly ordered structures such as lattices, capturing network dimensionality and regularity.Source: §2 · p. 5
  • The network portrait is a graph invariant: isomorphic graphs have identical portraits, regardless of node ordering or labeling.The converse does not hold: non-isomorphic dodecahedral and Desargues graphs have equal portraits.Source: §2 · pp. 4–5
  • For weighted networks, the portrait is generalized to account for real-valued shortest-path lengths rather than integer-valued lengths.The generalization is described in the appendix.Source: §2 · p. 5

2.1 Comparing networks by comparing portraits

  • The earlier portrait-comparison method uses row-wise cumulative distributions and Kolmogorov–Smirnov statistics, aggregated with greater weight on lower, more occupied shells.The paper characterizes that earlier comparison as somewhat ad hoc and proposes an information-theoretic alternative.Source: §2.1 · p. 6

3 An information-theoretic approach to network comparison

The section defines an information-theoretic network comparison based on distributions constructed from network portraits. The Network Portrait Divergence compares those distributions with Jensen–Shannon divergence, yielding a symmetric scalar measure with structural information from all scales.

3 An information-theoretic approach to network comparison

  • The Network Portrait Divergence compares portrait-based graph-invariant distributions using information theory, replacing the earlier ad hoc comparison measure.The proposed measure uses the shortest-path information encoded by network portraits.Source: §3 · pp. 7–9
  • The method combines node-pair distance probabilities with the prevalence of nodes at those distances, then conditions on connected pairs to define one joint distribution.This yields a normalized distribution even when the graph is disconnected.Source: §3 · pp. 8–9
  • Using a single joint distribution compares network structure across distance shells without leaving separate row-wise divergences to aggregate.The earlier approach produced up to max(d, d′) + 1 separate quantities.Source: §3 · pp. 7, 9
  • The Network Portrait Divergence DJS ranges from 0 to 1 and quantifies network dissimilarity using distance distributions; smaller values indicate more similar networks, and DJS is symmetric while sqrt(DJS) is a metric.KL(P(k)||Q(k)) is undefined if some k has P(k)>0 and Q(k)=0.Source: §3 · pp. 7, 9
  • Portrait-based comparison is independent of node indexing and shared node sets, avoids node-matching optimization, and handles directed, disconnected, and weighted networks.The joint neighbor–shortest-path distribution lets structure from local patterns through large-scale connectivity contribute simultaneously.Source: §3 · pp. 9–10

4 Results

The Network Portrait Divergence distinguishes synthetic network ensembles and rewiring perturbations, and reveals structural relationships across multiplex layers and network years. Weighted temporal comparisons remain broadly robust to the tested binning choices.

4.1 Synthetic networks

4.2 Measuring network perturbations with Network Portrait Divergence

  • DJS rises with rewiring count; below about 100 rewires the types are indistinguishable, but above 100 random rewiring produces greater divergence, especially for BA graphs.Source: §4.2 · pp. 11–12, Figure 3 · p. 12

4.3 Comparing real networks

  • In Arabidopsis, direct and physical layers are most distinct; among the other five, suppressive–synthetic (DJS = 0.553) and additive–suppressive (DJS = 0.365) are distinguished.Source: §4.3 · p. 13, Figure 4 · p. 14
  • In C. elegans, electrical junctions are closer to monadic than polyadic synapses, while monadic synapses are closer to polyadic than electrical junctions.All polyadic synapses are aggregated into one layer, which accounts for over half of the network’s links.Source: §4.3 · p. 14
  • The IBM network’s 2015–2016 structural similarity coincides with slower growth; other years diverge strongly, especially the extreme years.Source: §4.3 · p. 14, Figure 5 · p. 15
  • Across four quantile binnings of weighted paths, temporal relationships remain robust and resemble—but are not identical to—the unweighted pattern.The tested bin counts range from 100 to 10.Source: §4.3 · pp. 15–16, Figure 6 · p. 16

5 Conclusion

The Network Portrait Divergence compares networks through an information-theoretic graph invariant, and the paper reports validation on synthetic and real-world data. Its scope spans disconnected, directed, unweighted, and weighted networks, but computation remains quadratic in node count.

5 Conclusion

  • The Network Portrait Divergence uses an invariant portrait to compare network topology across structural scales without requiring connected graphs, matching indices, equal node sets, or a specified relation.It is designed to be affected by network topology rather than recording format or node order.Source: §5 · p. 16
  • Computation remains quadratic in the number of nodes, so scaling to very large networks will likely require efficiency gains such as shortest-path-distribution approximations.The paper says its computational complexity compares favorably with many other measures, particularly spectral measures.Source: §5 · p. 16
  • Unlike the communicability-based comparison of Chen et al., Network Portrait Divergence needs no ad hoc modification when comparing networks of different sizes.Its distinctive composition uses all shortest-path-length distributions for the networks being compared.Source: §5 · p. 17
  • Other information-theoretic divergences, including Hellinger distance and total variation distance, may yield different interpretations and insights across comparison problems.The paper identifies understanding their use across different network comparison problems as a fruitful direction.Source: §5 · p. 17
  • Suitable graph null models could support statistical procedures that assess structural randomness or the significance of an observed divergence.The paper proposes comparing divergences from random graph proxies with the divergence between the original graphs, potentially using a Z-test.Source: §5 · p. 17
  • Network comparison lacks standardized, systematic benchmarks, so this work evaluates selected tasks rather than introducing a benchmarking suite.Defining and validating an appropriate suite is described as beyond the scope of the work.Source: §5 · pp. 17–18
  • As network datasets grow in scope, Network Portrait Divergence has the potential to help researchers explore and understand their sets of networks.Source: §5 · p. 18

Abbreviations

The abbreviations list names common divergence and random-graph terms alongside the paper’s domain-specific interaction abbreviation.

Abbreviations

A Portraits and Network Portrait Divergences for weighted networks

For weighted networks, the portrait groups shortest paths into length bins, using weighted shortest-path algorithms and a researcher-selected binning strategy. When comparing two graphs, the bins must be shared so their portrait rows are compatible.

A Portraits and Network Portrait Divergences for weighted networks

  • Weighted portraits require Dijkstra’s algorithm and all-pairs shortest paths, giving total complexity O(MN + N^2 log N), compared with O(MN + N^2) for unweighted portraits.The weighted case is more costly because minimum-cost paths are generally more computationally intensive to find than minimum-length paths.Source: A Portraits and Network Portrait… · pp. 18–19
  • Each weighted-portrait row represents a shortest-path-length interval, and B_i,k counts nodes having k nodes at distances within that interval.The bins partition the path lengths; the final bin includes its upper endpoint.Source: A Portraits and Network Portrait… · p. 19
  • The paper uses adaptive quantile bins that partition unique connected-pair shortest-path lengths into approximately equal-sized groups; researchers may choose b or another binning rule.For example, b = 100 gives approximately 1% of shortest paths per bin.Source: A Portraits and Network Portrait… · p. 19
  • For IBM developers, shared-file counts weight edges; Dijkstra uses reciprocal weights, while Fig. 7 aligns path-length bin marks in the cumulative distribution with portrait rows.The reciprocal-weight choice makes larger weights correspond to more closely related developers.Source: A Portraits and Network Portrait… · p. 19, Figure 7 · p. 20
  • For two graphs, the weighted portraits use shared path-length bins computed as quantiles of the union of their connected-pair shortest-path lengths.Shared bins make the portrait rows compatible in the distributions used to compute Network Portrait Divergence.Source: A Portraits and Network Portrait… · p. 20

Related papers

Loading 1804.03665v3…