Random graph models for dynamic networks

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.

15 pages, four figures

References in corpus (8)

• The structure and dynamics of multilayer networks
• Comparing community structure identification
• 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
• Phase transition in the detection of modules in sparse networks
• Dynamic stochastic blockmodels: Statistical models for time-evolving 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
• $({\omega }_1,{\omega }_2)$-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