Cross-linked structure of network evolution

Abstract

We study the temporal co-variation of network co-evolution via the cross-link structure of networks, for which we take advantage of the formalism of hypergraphs to map cross-link structures back to network nodes. We investigate two sets of temporal network data in detail. In a network of coupled nonlinear oscillators, hyperedges that consist of network edges with temporally co-varying weights uncover the driving co-evolution patterns of edge weight dynamics both within and between oscillator communities. In the human brain, networks that represent temporal changes in brain activity during learning exhibit early co-evolution that then settles down with practice. Subsequent decreases in hyperedge size are consistent with emergence of an autonomous subgraph whose dynamics no longer depends on other parts of the network. Our results on real and synthetic networks give a poignant demonstration of the ability of cross-link structure to uncover unexpected co-evolution attributes in both real and synthetic dynamical systems. This, in turn, illustrates the utility of analyzing cross-links for investigating the structure of temporal networks.

FIG. 1.

Co-evolution cross-links and hyperedges. A set of (a) node-node edges with (b) similar edge-weight time series are (c) cross-linked to one another, which yields (d) a hyperedge that connects them.

FIG. 2.

Co-evolution properties of Kuramoto oscillator network dynamics. (a) Community structure in a network of Kuramoto oscillators. (b) A box plot of the standard deviation in edge weights over time for a temporal network of Kuramoto oscillators. (c) Strength of network co-evolution ${\nu }_{A_t}$ of the real temporal network and a box plot indicating the distribution of ${\nu }_{A_t}$ obtained from 1000 instantiations of a null-model network. (d) Fraction of significant edge-edge correlations (i.e., cross-links) that connect a pair of within-community edges (“Within”), that connect a pair of between-community edges (“Between”), and that connect a within-community edge to a between-community edge (“Across”). We calculated the statistical significance of differences in these fraction values across the 3 cross-link types by permuting labels uniformly at random between each type of pair. (e) Fraction of (blue) within-community and (peach) between-community edges in each of the 5 edge sets extracted from ${\mathbf{\Lambda }}^{\prime }$ using community detection. We give values on a logarithmic scale. Insets: Mean synchronization $[S(t)={\sum }_{(i,j)\in h}{A}_{\mathit{i}\mathit{j}}(t)]$ of these edges as a function of time for each hyperedge h.

FIG. 3.

Co-evolution properties of brain network dynamics. (a) A histogram of the number of edges as a function of the standard deviation in edge weights over time for the 4 temporal networks. (b) Strength of network co-evolution ${\nu }_{A_t}$ of 4 temporal networks and the respective null-model networks (gray). Error bars indicate standard deviation of the mean over study participants. (c) Cumulative probability distribution Pr of the size s of hyperedges in the 4 learning hypergraphs. (d) Anatomical distribution of early-learning hypergraph node degree (averaged over the 20 participants). We obtain qualitatively similar results from the early, middle, late, and extended learning temporal networks. In panels (a)-(c), color and shape indicate the temporal network corresponding to (black circles) naive, (orange stars) early, (green diamonds) middle, and (blue squares) late learning.