Analytical maximum-likelihood method to detect patterns in real networks
arXiv:1103.0701 · doi:10.1088/1367-2630/13/8/083001
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.
arXiv comment26 pages, 10 figures
References in corpus (32)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Community detection in graphs
- The architecture of complex weighted networks
- The large-scale organization of metabolic networks
- Random graphs with arbitrary degree distributions and their applications
- Specificity and stability in topology of protein networks
- Analysis of weighted networks
- Detecting rich-club ordering in complex networks
- Reaction-diffusion processes and metapopulation models in heterogeneous networks
- Clustering in Complex Directed Networks
- Generation of uncorrelated random scale-free networks
- Generalizations of the clustering coefficient to weighted complex networks
- The statistical mechanics of networks
- Random graphs with clustering
- Patterns of link reciprocity in directed networks
- Classes of complex networks defined by role-to-role connectivity profiles
- Prominence and control: The weighted rich-club effect
- Pattern Detection in Complex Networks: Correlation Profile of the Internet
- Cut-offs and finite size effects in scale-free networks
- The entropy of network ensembles
- The origin of degree correlations in the Internet and other networks
- 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
- The weighted random graph model
- Rich-club vs rich-multipolarization phenomena in weighted networks
- Multi-species grandcanonical models for networks with reciprocity
- Weighted Configuration Model
- Influence of reciprocal arcs on the degree distribution and degree correlations
Cited by in corpus (114)
- 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
- Bitcoin Transaction Networks: an overview of recent results
- Estimating topological properties of weighted networks from limited information
- Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
- Degree correlations in directed scale-free networks
- Complex Networks and Symmetry I: A Review
- Enhanced capital-asset pricing model for the reconstruction of bipartite financial networks
- Brexit and bots: characterizing the behaviour of automated accounts on Twitter during the UK election
- Extracting significant signal of news consumption from social networks: the case of Twitter in Italian political elections
- 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
- Triadic motifs and dyadic self-organization in the World Trade Network
- Reconstructing networks
- Configuration model for correlation matrices preserving the node strength
- Correlations between weights and overlap in ensembles of weighted multiplex networks
- The Grand Canonical ensemble of weighted networks
- Codon Bias Patterns of 's Interacting Proteins
- 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
- A faster horse on a safer trail: generalized inference for the efficient reconstruction of weighted networks
- Epidemics of Liquidity Shortages in Interbank Markets
- Sparse Maximum-Entropy Random Graphs with a Given Power-Law Degree Distribution
- Multiplexity and multireciprocity in directed multiplexes
- Grand canonical validation of the bipartite International Trade Network
- Ensemble nonequivalence in random graphs with modular structure
- Meta-validation of bipartite network projections
- Statistical Mechanics of Multi-Edge Networks
- Centrality anomalies in complex networks as a result of model over-simplification
- The ambiguity of nestedness under soft and hard constraints
- Social dynamics of financial networks
- Randomizing growing networks with a time-respecting null model
- Bow-Tie Structures of Twitter Discursive Communities
- Gene communities in co-expression networks across different tissues
- Reconstructing mesoscale network structures
- Stationarity, non-stationarity and early warning signals in economic networks
- Duality between equilibrium and growing networks
- Networks with arbitrary edge multiplicities
- Low-temperature behaviour of social and economic networks
- Proper network randomization is key to assessing social balance
- Detecting spatial homogeneity in the world trade web with Detrended Fluctuation Analysis
- Pattern detection in bipartite networks: a review of terminology, applications and methods
- Pattern-detection in the global automotive industry: a manufacturer-supplier-product network analysis
- Entropy-based approach to missing-links prediction
- Spatial effects in real networks: measures, null models, and applications
- The role of distances in the World Trade Web
- Entropy-based detection of Twitter echo chambers
- Weighted hypersoft configuration model
- Entropy-based randomisation of rating networks
- 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
- Binary versus non-binary information in real time series: empirical results and maximum-entropy matrix models
- Universal Database for Economic Complexity
- Hamiltonian Dynamics of Preferential Attachment
- The configuration multi-edge model: Assessing the effect of fixing node strengths on weighted network magnitudes
- Entropy-based models to randomize real-world hypergraphs
- Crowded trades, market clustering, and price instability
- Online disinformation in the 2020 U.S. Election: swing vs. safe states
- The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
- Analytic solution of the two-star model with correlated degrees
- Reconstructing topological properties of complex networks using the fitness model
- Weighted network estimation by the use of topological graph metrics
- Geometric randomization of real networks with prescribed degree sequence
- Economic networks in and out of equilibrium
- Patterns of link reciprocity in directed, signed networks
- Statistically validated projection of bipartite signed networks
- Central limit theorem for the principal eigenvalue and eigenvector of Chung-Lu random graphs
- Large deviation and anomalous fluctuations scaling in degree assortativity on configuration networks
- An impossibility result for Markov Chain Monte Carlo sampling from micro-canonical bipartite graph ensembles
- Gravity models of networks: integrating maximum-entropy and econometric approaches
- Local phase transitions in a model of multiplex networks with heterogeneous degrees and inter-layer coupling
- Robust subgraph counting with distribution-free random graph analysis
- A Grand-Canonical Solution to a Class of Random Optimization Problems
- Spectral signatures of structural change in financial networks
- Commodity-specific triads in the Dutch inter-industry production network
- Assessing imbalance in signed brain networks
- Randomisation Algorithms for Large Sparse Matrices
- Italian Twitter semantic network during the Covid-19 epidemic