Analytical maximum-likelihood method to detect patterns in real networks

Abstract

In order to detect patterns in real networks, randomized graph ensembles that preserve only part of the topology of an observed network are systematically used as fundamental null models. However, their generation is still problematic. The existing approaches are either computationally demanding and beyond analytic control, or analytically accessible but highly approximate. Here we propose a solution to this long-standing problem by introducing an exact and fast method that allows to obtain expectation values and standard deviations of any topological property analytically, for any binary, weighted, directed or undirected network. Remarkably, the time required to obtain the expectation value of any property is as short as that required to compute the same property on the single original network. Our method reveals that the null behavior of various correlation properties is different from what previously believed, and highly sensitive to the particular network considered. Moreover, our approach shows that important structural properties (such as the modularity used in community detection problems) are currently based on incorrect expressions, and provides the exact quantities that should replace them.

26 pages, 10 figures

References in corpus (13)

• Community detection in graphs
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Clustering in Complex Directed Networks
• Random graphs with clustering
• Classes of complex networks defined by role-to-role connectivity profiles
• Prominence and control: The weighted rich-club effect
• The entropy of network ensembles
• A fitness model for the Italian Interbank Money Market
• Maximum likelihood: extracting unbiased information from complex networks
• The International Trade Network: weighted network analysis and modelling
• Generalized Bose-Fermi statistics and structural correlations in weighted networks
• Correlations in weighted networks
• Rich-club vs rich-multipolarization phenomena in weighted networks

Cited by in corpus (113)

• Multilayer Networks
• The structure and dynamics of multilayer networks
• The Statistical Physics of Real-World Networks
• The Physics of Financial Networks
• Nestedness in complex networks: Observation, emergence, and implications
• Quantifying randomness in real networks
• Early-warning signals of topological collapse in interbank networks
• Randomizing bipartite networks: the case of the World Trade Web
• Reciprocity of weighted networks
• Community detection for correlation matrices
• Systemic risk analysis in reconstructed economic and financial networks
• Randomizing world trade. I. A binary network analysis
• Randomizing world trade. II. A weighted network analysis
• Inferring monopartite projections of bipartite networks: an entropy-based approach
• Enhanced reconstruction of weighted networks from strengths and degrees
• The role of bot squads in the political propaganda on Twitter
• Breaking of ensemble equivalence in networks
• Reconstruction methods for networks: the case of economic and financial systems
• Uncovering disassortativity in large scale-free networks
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Statistically validated network of portfolio overlaps and systemic risk
• Reconstructing the world trade multiplex: the role of intensive and extensive biases
• Detecting early signs of the 2007-2008 crisis in the world trade
• Unbiased sampling of network ensembles
• Breaking the spell of nestedness
• Null Models of Economic Networks: The Case of the World Trade Web
• Lightning Network: a second path towards centralisation of the Bitcoin economy
• Randomized reference models for temporal networks
• Flow of online misinformation during the peak of the COVID-19 pandemic in Italy
• Estimating topological properties of weighted networks from limited information
• Bitcoin Transaction Networks: an overview of recent results
• Degree correlations in directed scale-free networks
• Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
• Complex Networks and Symmetry I: A Review
• Enhanced capital-asset pricing model for the reconstruction of bipartite financial networks
• Extracting significant signal of news consumption from social networks: the case of Twitter in Italian political elections
• Brexit and bots: characterizing the behaviour of automated accounts on Twitter during the UK election
• A GDP-driven model for the binary and weighted structure of the International Trade Network
• Firms' Challenges and Social Responsibilities during Covid-19: a Twitter Analysis
• Transfer entropy between communities in complex networks
• Reconstructing networks
• Triadic motifs and dyadic self-organization in the World Trade Network
• The Grand Canonical ensemble of weighted networks
• Configuration model for correlation matrices preserving the node strength
• Codon Bias Patterns of $E.coli$'s Interacting Proteins
• Correlations between weights and overlap in ensembles of weighted multiplex networks
• Local clustering in scale-free networks with hidden variables
• Reconstructing firm-level interactions: the Dutch input-output network
• Multiplexity versus correlation: the role of local constraints in real multiplexes
• Complex Networks and Symmetry II: Reciprocity and Evolution of World Trade
• Epidemics of Liquidity Shortages in Interbank Markets
• A faster horse on a safer trail: generalized inference for the efficient reconstruction of weighted networks
• Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
• Grand canonical validation of the bipartite International Trade Network
• Multiplexity and multireciprocity in directed multiplexes
• Ensemble nonequivalence in random graphs with modular structure
• Meta-validation of bipartite network projections
• Centrality anomalies in complex networks as a result of model over-simplification
• Statistical Mechanics of Multi-Edge Networks
• The ambiguity of nestedness under soft and hard constraints
• Social dynamics of financial networks
• Randomizing growing networks with a time-respecting null model
• Reconstructing mesoscale network structures
• Stationarity, non-stationarity and early warning signals in economic networks
• Bow-Tie Structures of Twitter Discursive Communities
• Gene communities in co-expression networks across different tissues
• Duality between equilibrium and growing networks
• Networks with arbitrary edge multiplicities
• Proper network randomization is key to assessing social balance
• Detecting spatial homogeneity in the world trade web with Detrended Fluctuation Analysis
• Pattern-detection in the global automotive industry: a manufacturer-supplier-product network analysis
• Spatial effects in real networks: measures, null models, and applications
• Pattern detection in bipartite networks: a review of terminology, applications and methods
• Entropy-based approach to missing-links prediction
• The role of distances in the World Trade Web
• Entropy-based randomisation of rating networks
• Entropy-based detection of Twitter echo chambers
• Weighted hypersoft configuration model
• The role of adjacency matrix degeneration in maximum entropy weighted network models
• Synchronization Invariance Under Network Structural Transformations
• Maximum Entropy approach to multivariate time series randomization
• Colombian export capabilities: building the firms-products network
• Phase transitions for scaling of structural correlations in directed networks
• Bibliometric and social network analysis on the use of satellite imagery in agriculture: an entropy-based approach
• Entropy of labeled versus unlabeled networks
• Entropy rate of random walks on complex networks under stochastic resetting
• Hamiltonian Dynamics of Preferential Attachment
• Binary versus non-binary information in real time series: empirical results and maximum-entropy matrix models
• Universal Database for Economic Complexity
• The configuration multi-edge model: Assessing the effect of fixing node strengths on weighted network magnitudes
• Online disinformation in the 2020 U.S. Election: swing vs. safe states
• Entropy-based models to randomize real-world hypergraphs
• Crowded trades, market clustering, and price instability
• Analytic solution of the two-star model with correlated degrees
• The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
• Reconstructing topological properties of complex networks using the fitness model
• Economic networks in and out of equilibrium
• Geometric randomization of real networks with prescribed degree sequence
• Weighted network estimation by the use of topological graph metrics
• Patterns of link reciprocity in directed, signed networks
• Central limit theorem for the principal eigenvalue and eigenvector of Chung-Lu random graphs
• An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
• Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
• Statistically validated projection of bipartite signed networks
• Local phase transitions in a model of multiplex networks with heterogeneous degrees and inter-layer coupling
• Gravity models of networks: integrating maximum-entropy and econometric approaches
• A Grand-Canonical Solution to a Class of Random Optimization Problems
• Italian Twitter semantic network during the Covid-19 epidemic
• Assessing imbalance in signed brain networks
• Spectral signatures of structural change in financial networks
• Robust subgraph counting with distribution-free random graph analysis
• Commodity-specific triads in the Dutch inter-industry production network
• Randomisation Algorithms for Large Sparse Matrices