Exploring Temporal Networks with Greedy Walks

Abstract

Temporal networks come with a wide variety of heterogeneities, from burstiness of event sequences to correlations between timings of node and link activations. In this paper, we set to explore the latter by using greedy walks as probes of temporal network structure. Given a temporal network (a sequence of contacts), greedy walks proceed from node to node by always following the first available contact. Because of this, their structure is particularly sensitive to temporal-topological patterns involving repeated contacts between sets of nodes. This becomes evident in their small coverage per step as compared to a temporal reference model -- in empirical temporal networks, greedy walks often get stuck within small sets of nodes because of correlated contact patterns. While this may also happen in static networks that have pronounced community structure, the use of the temporal reference model takes the underlying static network structure out of the equation and indicates that there is a purely temporal reason for the observations. Further analysis of the structure of greedy walks indicates that burst trains, sequences of repeated contacts between node pairs, are the dominant factor. However, there are larger patterns too, as shown with non-backtracking greedy walks. We proceed further to study the entropy rates of greedy walks, and show that the sequences of visited nodes are more structured and predictable in original data as compared to temporally uncorrelated references. Taken together, these results indicate a richness of correlated temporal-topological patterns in temporal networks.

References in corpus (6)

• Small But Slow World: How Network Topology and Burstiness Slow Down Spreading
• Structure and Time-Evolution of an Internet Dating Community
• Random walks and search in time-varying networks
• Steady state and mean recurrence time for random walks on stochastic temporal networks
• Modeling temporal networks using random itineraries
• Structural differences between open and direct communication in an online community

Cited by in corpus (13)

• Random walks and diffusion on networks
• Stream Graphs and Link Streams for the Modeling of Interactions over Time
• Bursty Human Dynamics
• Randomized reference models for temporal networks
• Using higher-order Markov models to reveal flow-based communities in networks
• Universal patterns in egocentric communication networks
• Circulation of a digital community currency
• Navigating temporal networks
• An embedding-based distance for temporal graphs
• Event Graphs: Advances and Applications of Second-Order Time-Unfolded Temporal Network Models
• A Markov model for inferring flows in directed contact networks
• Rock-Paper-Scissors Random Walks on Temporal Multilayer Networks
• Networks of monetary flow at native resolution