Two models of sparse and clustered dynamic networks

We present two models of sparse dynamic networks that display transitivity—the tendency for nodes sharing a common neighbour to be neighbours of one another. Our first network is a continuous time Markov chain G=ₜ=(V, Eₜ),t≥ 0\ whose states are graphs with the common set of nodes V=\1 , , n\. The transitions are defined as follows. Given t, the node pairs , j\⊂ V are assigned independent exponential waiting times Aᵢⱼ. At time t+minᵢⱼAᵢⱼ the pair ₀,j₀\ with A_i₀j₀=minᵢⱼAᵢⱼ toggles its adjacency status. To mimic clustering patterns of sparse real networks we set intensities aᵢⱼ of exponential times Aᵢⱼ to be decreasing functions of the degrees of common neighbours of nodes i and j in Gₜ. Our second network G^=^ₜ=(E^ₜ,V),t≥ 0\ is the affiliation network based on a latent Markov chain H=ₜ=(V∪ W, Eₜ),t≥ 0\ whose states are bipartite graphs with the bipartition V∪ W, where W=\1 , , m\ is an auxiliary set of attributes/affiliations. Nodes i₁,i₂∈ V are adjacent in G^ₜ whenever i₁ and i₂ have a common neighbour in Hₜ. We analyse geometric properties of both dynamic networks at stationarity and show that networks possess high clustering. They admit tunable degree distribution and clustering coefficients.