Article,
Exploring temporal networks with greedy walks
The European Physical Journal B, (Dec 14, 2015)
DOI: 10.1140/epjb/e2015-60660-9
Abstract
Temporal networks come with a wide variety of heterogeneities, from
burstiness of event sequences to correlations between timingsof 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.
