Irreducible network backbones: unbiased graph filtering via maximum entropy

Abstract

Networks provide an informative, yet non-redundant description of complex systems only if links represent truly dyadic relationships that cannot be directly traced back to node-specific properties such as size, importance, or coordinates in some embedding space. In any real-world network, some links may be reducible, and others irreducible, to such local properties. This dichotomy persists despite the steady increase in data availability and resolution, which actually determines an even stronger need for filtering techniques aimed at discerning essential links from non-essential ones. Here we introduce a rigorous method that, for any desired level of statistical significance, outputs the network backbone that is irreducible to the local properties of nodes, i.e. their degrees and strengths. Unlike previous approaches, our method employs an exact maximum-entropy formulation guaranteeing that the filtered network encodes only the links that cannot be inferred from local information. Extensive empirical analysis confirms that this approach uncovers essential backbones that are otherwise hidden amidst many redundant relationships and inaccessible to other methods. For instance, we retrieve the hub-and-spoke skeleton of the US airport network and many specialised patterns of international trade. Being irreducible to local transportation and economic constraints of supply and demand, these backbones single out genuinely higher-order wiring principles.

Main + SI. (19+8) pages, (8+9) figures, (2+4) tables. Submitted for publication

References in corpus (26)

• Community detection in graphs
• Catastrophic cascade of failures in interdependent networks
• The architecture of complex weighted networks
• Structure and tie strengths in mobile communication networks
• Extracting the multiscale backbone of complex weighted networks
• The statistical mechanics of networks
• Layer aggregation and reducibility of multilayer interconnected networks
• Emergence of network features from multiplexity
• Statistically validated networks in bipartite complex systems
• Maximum likelihood: extracting unbiased information from complex networks
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Spectral coarse-graining of complex networks
• Randomizing world trade. I. A binary network analysis
• A topological criterion for filtering information in complex brain networks
• Randomizing world trade. II. A weighted network analysis
• Breaking of ensemble equivalence in networks
• Information filtering in complex weighted networks
• The Backbone of a City
• Unwinding the hairball graph: pruning algorithms for weighted complex networks
• Reconstructing the world trade multiplex: the role of intensive and extensive biases
• Geographical Coarsegraining of Complex Networks
• Estimating topological properties of weighted networks from limited information
• Ensemble nonequivalence in random graphs with modular structure
• Network reconstruction via density sampling
• Fast extraction of the backbone of projected bipartite networks to aid community detection
• Network Backboning with Noisy Data

Cited by in corpus (7)

• The structured backbone of temporal social ties
• An Evaluation Tool for Backbone Extraction Techniques in Weighted Complex Networks
• Introduction to correlation networks: Interdisciplinary approaches beyond thresholding
• From Relational Data to Graphs: Inferring Significant Links using Generalized Hypergeometric Ensembles
• Extracting the signed backbone of intrinsically dense weighted networks
• Characterization of interactions' persistence in time-varying networks
• The Atlas for the Aspiring Network Scientist