Random graph models for dynamic networks
arXiv:1607.07570 · doi:10.1140/epjb/e2017-80122-8
Abstract
We propose generalizations of a number of standard network models, including the classic random graph, the configuration model, and the stochastic block model, to the case of time-varying networks. We assume that the presence and absence of edges are governed by continuous-time Markov processes with rate parameters that can depend on properties of the nodes. In addition to computing equilibrium properties of these models, we demonstrate their use in data analysis and statistical inference, giving efficient algorithms for fitting them to observed network data. This allows us, for instance, to estimate the time constants of network evolution or infer community structure from temporal network data using cues embedded both in the probabilities over time that node pairs are connected by edges and in the characteristic dynamics of edge appearance and disappearance. We illustrate our methods with a selection of applications, both to computer-generated test networks and real-world examples.
arXiv comment15 pages, four figures
References in corpus (24)
- Random graphs with arbitrary degree distributions and their applications
- The structure and dynamics of multilayer networks
- Comparing community structure identification
- Temporal Networks
- Hierarchical structure and the prediction of missing links in networks
- Stochastic blockmodels and community structure in networks
- Missing and spurious interactions and the reconstruction of complex networks
- Activity driven modeling of time varying networks
- The physics of spreading processes in multilayer networks
- Modern temporal network theory: A colloquium
- Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys
- Phase transition in the detection of modules in sparse networks
- Controlling Contagion Processes in Time-Varying Networks
- A state-space mixed membership blockmodel for dynamic network tomography
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Clustering Network Layers With the Strata Multilayer Stochastic Block Model
- Consistent estimation of dynamic and multi-layer block models
- Stability of Spreading Processes over Time-Varying Large-Scale Networks
- Generalization of Blonder-Tinkham-Klapwijk theory to particle-hole mixing boundary conditions: π-shift and conductance dips
- Thermoelectric transport in the topological phase due to the coexistence of superconductivity and spin-density-wave
- Dynamic stochastic blockmodels: Statistical models for time-evolving networks
- Stochastic Block Transition Models for Dynamic Networks
- Nonparametric Multi-group Membership Model for Dynamic Networks
- A semiparametric extension of the stochastic block model for longitudinal networks
Cited by in corpus (37)
- Social physics
- A Review of Stochastic Block Models and Extensions for Graph Clustering
- Bayesian stochastic blockmodeling
- Randomized reference models for temporal networks
- A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
- Reciprocity, community detection, and link prediction in dynamic networks
- Gillespie algorithms for stochastic multiagent dynamics in populations and network
- Randomizing growing networks with a time-respecting null model
- Generative model for reciprocity and community detection in networks
- A framework to generate hypergraphs with community structure
- Bayesian Graph Convolutional Neural Networks using Node Copying
- Fast Change Point Detection on Dynamic Social Networks
- General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
- Dynamic Hidden-Variable Network Models
- Using Motif Transitions for Temporal Graph Generation
- SWNet: Small-World Neural Networks and Rapid Convergence
- Characterization of interactions' persistence in time-varying networks
- Higher-order temporal network effects through triplet evolution
- Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model
- Isolation probabilities in dynamic soft random geometric graphs
- Analysis of the competition among viral strains using a temporal interaction-driven contagion model
- Spectral clustering in the dynamic stochastic block model
- Queues on a dynamically evolving graph
- Node Copying: A Random Graph Model for Effective Graph Sampling
- Temporal networks with node-specific memory: unbiased inference of transition probabilities, relaxation times and structural breaks
- SIS Epidemics in Multilayer-based Temporal Networks
- Compressing the chronology of a temporal network with graph commutators
- Dynamics of cold random hyperbolic graphs with link persistence
- Dynamic Erdős-Rényi graphs
- Constant State of Change: Engagement Inequality in Temporal Dynamic Networks
- Size Agnostic Change Point Detection Framework for Evolving Networks
- Block-Structure Based Time-Series Models For Graph Sequences
- Broken Detailed Balance and Non-Equilibrium Dynamics in Noisy Social Learning Models
- -temporal random hyperbolic graphs
- Divide and Rule: Recurrent Partitioned Network for Dynamic Processes
- State-Driven Dynamic Graphon Model
- Effects of concurrency on epidemic spreading in Markovian temporal networks