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 temporal greedy walks as probes of temporal network structure. Given a temporal network (a sequence of contacts), temporal 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 taken 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.
Similar content being viewed by others
References
P. Holme, J. Saramäki, Phys. Rep. 519, 97 (2012)
A.L. Barabási, Nature 435, 207 (2005)
A. Vazquez, B. Rácz, A. Lukács, A.L. Barabási, Phys. Rev. Lett. 98, 158702 (2007)
J. Iribarren, E. Moro, Phys. Rev. Lett. 103, 038702 (2009)
M. Karsai, M. Kivelä, R.K. Pan, K. Kaski, J. Kertész, A.L. Barabási, J. Saramäki, Phys. Rev. E 83, 025102 (2011)
M. Karsai, K. Kaski, A.L. Barabási, J. Kertész, Sci. Rep. 2, 397 (2012)
L. Kovanen, M. Karsai, K. Kaski, J. Kertész, J. Saramäki, J. Stat. Mech. Theor. Exp. 2011, P11005 (2011)
L. Kovanen, K. Kaski, J. Kertész, J. Saramäki, Proc. Natl. Acad. Sci. USA 110, 18070 (2013)
I. Scholtes, N. Wider, R. Pfitzner, A. Garas, C.J. Tessone, F. Schweitzer, Nat. Commun. 5, 5024 (2014)
V.P. Backlund, J. Saramäki, R.K. Pan, Phys. Rev. E 89, 062815 (2014)
R. Pfizner, I. Scholtes, A. Garas, C. Tessone, F. Schweitzer, Phys. Rev. Lett. 110, 198701 (2013)
M. Karsai, K. Kaski, J. Kertész, PLoS One 7, e40612 (2012)
Q. Zhao, Y. Tian, Q. He, N. Oliver, R. Jin, W.C. Lee, Communication motifs: A tool to characterize social communications, in Proc. of the 19th ACM International Conference on Information and Knowledge Management (2010), pp. 1645–1648
N. Perra, A. Baronchelli, D. Mocanu, B. Gonçalves, R. Pastor-Satorras, A. Vespignani, Phys. Rev. Lett. 109, 238701 (2012)
M. Starnini, A. Baronchelli, A. Barrat, R. Pastor-Satorras, Phys. Rev. E 85, 056115 (2012)
L.E.C. Rocha, N. Masuda, New J. Phys. 16, 063023 (2014)
J.C. Delvenne, R. Lambiotte, L.E.C. Rocha, Nat. Commun. 6, 7366 (2015)
L. Speidel, R. Lambiotte, K. Aihara, N. Masuda, Phys. Rev. E 91, 012806 (2015)
T. Hoffmann, M.A. Porter, R. Lambiotte, Phys. Rev. E 86, 046102 (2012)
N. Masuda, K. Klemm, V.M. Eguíluz, Phys. Rev. Lett. 111, 188701 (2013)
A. Barrat, B. Fernandez, K.K. Lin, L.S. Young, Phys. Rev. Lett. 110, 158702 (2013)
J.C. Delvenne, S.N. Yaliraki, M. Barahona, Proc. Natl. Acad. Sci. USA 107, 12755 (2010)
B. Ribeiro, N. Perra, A. Baronchelli, Sci. Rep. 3, 3006 (2013)
A. Albano, J.L. Guillaume, S. Heymann, B. Le Grand, A matter of time – intrinsic or extrinsic – for diffusion in evolving complex networks, in 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM) (2013), pp. 202–206
H. Ebel, L.I. Mielsch, S. Bornholdt, Phys. Rev. E 66, 035103 (2002)
J.P. Eckmann, E. Moses, D. Sergi, Proc. Natl. Acad. Sci. USA 101, 14333 (2004)
B. Viswanath, A. Mislove, M. Cha, K.P. Gummadi, On the evolution of user interaction in facebook, in Proc. of the 2nd ACM Workshop on Online Social Networks (ACM, 2009), pp. 37–42
F. Karimi, V.C. Ramenzoni, P. Holme, Physica A 414, 263 (2014)
P. Vanhems, A. Barrat, C. Cattuto, J.F. Pinton, N. Khanafer, C. Régis, B.A. Kim, B. Comte, N. Voirin, PLoS One 8, e73970 (2013)
P. Holme, C.R. Edling, F. Liljeros, Soc. Networks 26, 155 (2004)
N. Eagle, A.S. Pentland, D. Lazer, Proc. Natl. Acad. Sci. USA 106, 15274 (2009)
C.M. Song, Z.H. Qu, N. Blumm, A.L. Barabási, Science 327, 1018 (2010)
T. Takaguchi, M. Nakamura, N. Sato, K. Yano, N. Masuda, Phys. Rev. X 1, 011008 (2011)
J. Ziv, A. Lempel, IEEE Trans. Inform. Theory 23, 337 (1977)
P. Shields, Ann. Probab. 20, 403 (1992)
T. Schurmann, P. Grassberger, Chaos 6, 414 (1996)
P. Grindrod, M.C. Parsons, D.J. Higham, E. Estrada, Phys. Rev. E 83, 046120 (2011)
G. Miritello, E. Moro, R. Lara, Phys. Rev. E 83, 045102 (2011)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Saramäki, J., Holme, P. Exploring temporal networks with greedy walks. Eur. Phys. J. B 88, 334 (2015). https://doi.org/10.1140/epjb/e2015-60660-9
Received:
Revised:
Published:
DOI: https://doi.org/10.1140/epjb/e2015-60660-9