Latent Poisson models for networks with heterogeneous density

Abstract

Empirical networks are often globally sparse, with a small average number of connections per node, when compared to the total size of the network. However, this sparsity tends not to be homogeneous, and networks can also be locally dense, for example with a few nodes connecting to a large fraction of the rest of the network, or with small groups of nodes with a large probability of connections between them. Here we show how latent Poisson models which generate hidden multigraphs can be effective at capturing this density heterogeneity, while being more tractable mathematically than some of the alternatives that model simple graphs directly. We show how these latent multigraphs can be reconstructed from data on simple graphs, and how this allows us to disentangle disassortative degree-degree correlations from the constraints of imposed degree sequences, and to improve the identification of community structure in empirically relevant scenarios.

arXiv comment19 pages, 16 figures

References in corpus (31)

• Emergence of scaling in random networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Cooperative Game Theory Approaches for Network Partitioning
• Mixing patterns in networks
• Resolution limit in community detection
• Spatial Networks
• Stochastic blockmodels and community structure in networks
• Community detection in complex networks using Extremal Optimization
• The performance of modularity maximization in practical contexts
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Dynamics of person-to-person interactions from distributed RFID sensor networks
• High resolution dynamical mapping of social interactions with active RFID
• Bose-Einstein condensation in complex networks
• 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
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Parsimonious module inference in large networks
• The origin of degree correlations in the Internet and other networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Evaluating Overfit and Underfit in Models of Network Community Structure
• All scale-free networks are sparse
• Network reconstruction and community detection from dynamics
• The entropic origin of disassortativity in complex networks
• Breaking of ensemble equivalence in networks
• Gibbs entropy of networks ensembles by cavity methods
• Reconstructing networks with unknown and heterogeneous errors
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Consistency of community structure in complex networks
• Software systems through complex networks science: Review, analysis and applications

Cited by in corpus (5)

• Hypergraph reconstruction from network data
• Merge-split Markov chain Monte Carlo for community detection
• Revealing consensus and dissensus between network partitions
• Disentangling homophily, community structure and triadic closure in networks
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks