Temporal network

Last updated

A temporal network, also known as a time-varying network, is a network whose links are active only at certain points in time. Each link carries information on when it is active, along with other possible characteristics such as a weight. Time-varying networks are of particular relevance to spreading processes, like the spread of information and disease, since each link is a contact opportunity and the time ordering of contacts is included.


Examples of time-varying networks include communication networks where each link is relatively short or instantaneous, such as phone calls or e-mails. [1] [2] Information spreads over both networks, and some computer viruses spread over the second. Networks of physical proximity, encoding who encounters whom and when, can be represented as time-varying networks. [3] Some diseases, such as airborne pathogens, spread through physical proximity. Real-world data on time resolved physical proximity networks has been used to improve epidemic modeling. [4] Neural networks and brain networks can be represented as time-varying networks since the activation of neurons are time-correlated. [5]

Time-varying networks are characterized by intermittent activation at the scale of individual links. This is in contrast to various models of network evolution, which may include an overall time dependence at the scale of the network as a whole.


Time-varying networks are inherently dynamic, and used for modeling spreading processes on networks. Whether using time-varying networks will be worth the added complexity depends on the relative time scales in question. Time-varying networks are most useful in describing systems where the spreading process on a network and the network itself evolve at similar timescales. [6]

Let the characteristic timescale for the evolution of the network be , and the characteristic timescale for the evolution of the spreading process be . A process on a network will fall into one of three categories:

The flow of data over the internet is an example for the first case, where the network changes very little in the fraction of a second it takes for a network packet to traverse it. [7] The spread of sexually transmitted diseases is an example of the second, where the prevalence of the disease spreads in direct correlation to the rate of evolution of the sexual contact network itself. [8] Behavioral contagion is an example of the third case, where behaviors spread through a population over the combined network of many day-to-day social interactions. [9]


There are three common representations for time-varying network data. [10]


The measures used to characterize static networks are not immediately transferable to time-varying networks. See Path, Connectedness, Distance, Centrality. However, these network concepts have been adapted to apply to time-varying networks.

Time respecting paths

Time respecting paths are the sequences of links that can be traversed in a time-varying network under the constraint that the next link to be traversed is activated at some point after the current one. Like in a directed graph, a path from to does not mean there is a path from to . In contrast to paths in static and evolving networks, however, time respecting paths are also non-transitive. That is to say, just because there is a path from to and from to does not mean that there is a path from to . Furthermore, time respecting paths are themselves time-varying, and are only valid paths during a specific time interval. [11]


While analogous to connectedness in static networks, reachability is a time-varying property best defined for each node in the network. The set of influence of a node is the set of all nodes that can be reached from via time respecting paths, note that it is dependent on the start time . The source set of a node is the set of all nodes that can reach via time respecting paths within a given time interval. The reachability ratio can be defined as the average over all nodes of the fraction of nodes within the set of influence of . [12]

Connectedness of an entire network is less conclusively defined, although some have been proposed. A component may be defined as strongly connected if there is a directed time respecting path connecting all nodes in the component in both directions. A component may be defined as weakly connected if there is an undirected time respecting path connecting all nodes in the component in both directions. [13] Also, a component may be defined as transitively connected if transitivity holds for the subset of nodes in that component.

Causal fidelity

Causal fidelity quantifies the goodness of the static approximation of a temporal network. Such a static approximation is generated by aggregating the edges of a temporal network over time. The idea of causal fidelity is to compare the number of paths between all node pairs in the temporal network (that is, all time respecting paths) with the number of paths between all nodes in the static approximation of the network. [14] The causal fidelity is then defined by


Since in only time respecting paths are considered, , and consequently . A high causal fidelity means that the considered temporal network is well approximated by its static (aggregated) counterpart. If , then most node pairs that are reachable in the static representation are not connected by time respecting paths in the temporal network.


Also called temporal distance, latency is the time-varying equivalent to distance. In a time-varying network any time respecting path has a duration, namely the time it takes to follow that path. The fastest such path between two nodes is the latency, note that it is also dependent on the start time. The latency from node to node beginning at time is denoted by .

Centrality measures

Measuring centrality on time-varying networks involves a straightforward replacement of distance with latency. [15] For discussions of the centrality measures on a static network see Centrality.

The time-varying nature of latency, specifically that it will become infinity for all node pairs as the time approaches the end of the network interval used, makes an alternative measure of closeness useful. Efficiency uses instead the reciprocal of the latency, so the efficiency approaches zero instead of diverging. Higher values for efficiency correspond to more central nodes in the network.

Temporal patterns

Time-varying network allow for analysis of explicit time dependent properties of the network. It is possible to extract recurring and persistent patterns of contact from time-varying data in many ways. This is an area of ongoing research.


Time-varying networks allow for the analysis of an entirely new dimension of dynamic processes on networks. In cases where the time scales of evolution of the network and the process are similar, the temporal structure of time-varying networks has a dramatic impact on the spread of the process over the network.


The time between two consecutive events, for an individual node or link, is called the inter-event time. The distribution of inter-event times of a growing number of important, real-world, time-varying networks have been found to be bursty, meaning inter-event times are very heterogeneous – they have a heavy-tailed distribution. This translates to a pattern of activation where activity comes in bursts separated by longer stretches of inactivity. [20]

Burstiness of inter-event times can dramatically slow spreading processes on networks, [21] which has implications for the spread of disease, information, ideas, and computer viruses. However, burstiness can also accelerate spreading processes, and other network properties also have an effect on spreading speed. [22] Real-world time-varying networks may thus promote spreading processes despite having a bursty inter-event time distribution. [23]

Burstiness as an empirical quantity can be calculated for any sequence of inter-event times, , by comparing the sequence to one generated by a Poisson process. The ratio of the standard deviation, , to the mean, , of a Poisson process is 1. This measure compares to 1.

Burstiness varies from −1 to 1. B = 1 indicates a maximally bursty sequence, B = 0 indicates a Poisson distribution, and B = −1 indicates a periodic sequence. [24]

See also

Related Research Articles

<span class="mw-page-title-main">Scale-free network</span> Network whose degree distribution follows a power law

A scale-free network is a network whose degree distribution follows a power law, at least asymptotically. That is, the fraction P(k) of nodes in the network having k connections to other nodes goes for large values of k as

<span class="mw-page-title-main">Nonlinear dimensionality reduction</span> Summary of algorithms for nonlinear dimensionality reduction

Nonlinear dimensionality reduction, also known as manifold learning, refers to various related techniques that aim to project high-dimensional data onto lower-dimensional latent manifolds, with the goal of either visualizing the data in the low-dimensional space, or learning the mapping itself. The techniques described below can be understood as generalizations of linear decomposition methods used for dimensionality reduction, such as singular value decomposition and principal component analysis.

<span class="mw-page-title-main">Centrality</span> Degree of connectedness within a graph

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

Dynamic network analysis (DNA) is an emergent scientific field that brings together traditional social network analysis (SNA), link analysis (LA), social simulation and multi-agent systems (MAS) within network science and network theory. Dynamic networks are a function of time to a set of graphs; for each time point there is a graph. This is akin to the definition of dynamical systems, in which the function is from time to an ambient space, where instead of ambient space time is translated to relationships between pairs of vertices.

<span class="mw-page-title-main">Community structure</span> Concept in graph theory

In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally. In the particular case of non-overlapping community finding, this implies that the network divides naturally into groups of nodes with dense connections internally and sparser connections between groups. But overlapping communities are also allowed. The more general definition is based on the principle that pairs of nodes are more likely to be connected if they are both members of the same community(ies), and less likely to be connected if they do not share communities. A related but different problem is community search, where the goal is to find a community that a certain vertex belongs to.

In complex network theory, the fitness model is a model of the evolution of a network: how the links between nodes change over time depends on the fitness of nodes. Fitter nodes attract more links at the expense of less fit nodes.

<span class="mw-page-title-main">Network science</span> Academic field

Network science is an academic field which studies complex networks such as telecommunication networks, computer networks, biological networks, cognitive and semantic networks, and social networks, considering distinct elements or actors represented by nodes and the connections between the elements or actors as links. The field draws on theories and methods including graph theory from mathematics, statistical mechanics from physics, data mining and information visualization from computer science, inferential modeling from statistics, and social structure from sociology. The United States National Research Council defines network science as "the study of network representations of physical, biological, and social phenomena leading to predictive models of these phenomena."

<span class="mw-page-title-main">Modularity (networks)</span> Measure of network community structure

Modularity is a measure of the structure of networks or graphs which measures the strength of division of a network into modules. Networks with high modularity have dense connections between the nodes within modules but sparse connections between nodes in different modules. Modularity is often used in optimization methods for detecting community structure in networks. Biological networks, including animal brains, exhibit a high degree of modularity. However, modularity maximization is not statistically consistent, and finds communities in its own null model, i.e. fully random graphs, and therefore it cannot be used to find statistically significant community structures in empirical networks. Furthermore, it has been shown that modularity suffers a resolution limit and, therefore, it is unable to detect small communities.

The clique percolation method is a popular approach for analyzing the overlapping community structure of networks. The term network community has no widely accepted unique definition and it is usually defined as a group of nodes that are more densely connected to each other than to other nodes in the network. There are numerous alternative methods for detecting communities in networks, for example, the Girvan–Newman algorithm, hierarchical clustering and modularity maximization.

<span class="mw-page-title-main">Evolving network</span>

Evolving networks are networks that change as a function of time. They are a natural extension of network science since almost all real world networks evolve over time, either by adding or removing nodes or links over time. Often all of these processes occur simultaneously, such as in social networks where people make and lose friends over time, thereby creating and destroying edges, and some people become part of new social networks or leave their networks, changing the nodes in the network. Evolving network concepts build on established network theory and are now being introduced into studying networks in many diverse fields.

<span class="mw-page-title-main">Betweenness centrality</span> Measure of a graphs centrality, based on shortest paths

In graph theory, betweenness centrality is a measure of centrality in a graph based on shortest paths. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that either the number of edges that the path passes through or the sum of the weights of the edges is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex.

In statistics, burstiness is the intermittent increases and decreases in activity or frequency of an event. One measure of burstiness is the Fano factor—a ratio between the variance and mean of counts.

<span class="mw-page-title-main">Multidimensional network</span> Networks with multiple kinds of relations

In network theory, multidimensional networks, a special type of multilayer network, are networks with multiple kinds of relations. Increasingly sophisticated attempts to model real-world systems as multidimensional networks have yielded valuable insight in the fields of social network analysis, economics, urban and international transport, ecology, psychology, medicine, biology, commerce, climatology, physics, computational neuroscience, operations management, and finance.

In mathematical modeling of social networks, link-centric preferential attachment is a node's propensity to re-establish links to nodes it has previously been in contact with in time-varying networks. This preferential attachment model relies on nodes keeping memory of previous neighbors up to the current time.

<span class="mw-page-title-main">Biased random walk on a graph</span> Structural analysis of a network

In network science, a biased random walk on a graph is a time path process in which an evolving variable jumps from its current state to one of various potential new states; unlike in a pure random walk, the probabilities of the potential new states are unequal.

<span class="mw-page-title-main">Bianconi–Barabási model</span>

The Bianconi–Barabási model is a model in network science that explains the growth of complex evolving networks. This model can explain that nodes with different characteristics acquire links at different rates. It predicts that a node's growth depends on its fitness and can calculate the degree distribution. The Bianconi–Barabási model is named after its inventors Ginestra Bianconi and Albert-László Barabási. This model is a variant of the Barabási–Albert model. The model can be mapped to a Bose gas and this mapping can predict a topological phase transition between a "rich-get-richer" phase and a "winner-takes-all" phase.

<span class="mw-page-title-main">Hub (network science)</span> Node with a number of links that greatly exceeds the average

In network science, a hub is a node with a number of links that greatly exceeds the average. Emergence of hubs is a consequence of a scale-free property of networks. While hubs cannot be observed in a random network, they are expected to emerge in scale-free networks. The uprise of hubs in scale-free networks is associated with power-law distribution. Hubs have a significant impact on the network topology. Hubs can be found in many real networks, such as the brain or the Internet.

<span class="mw-page-title-main">Mediation-driven attachment model</span> Mathematics concept

In the scale-free network theory, a mediation-driven attachment (MDA) model appears to embody a preferential attachment rule tacitly rather than explicitly. According to MDA rule, a new node first picks a node from the existing network at random and connect itself not with that but with one of the neighbors also picked at random.

A set of networks that satisfies given structural characteristics can be treated as a network ensemble. Brought up by Ginestra Bianconi in 2007, the entropy of a network ensemble measures the level of the order or uncertainty of a network ensemble.

In network science, the network entropy is a disorder measure derived from information theory to describe the level of randomness and the amount of information encoded in a graph. It is a relevant metric to quantitatively characterize real complex networks and can also be used to quantify network complexity


  1. Karsai, M.; Perra, N.; Vespignani, A. (2015). "Time-varying networks and the weakness of strong ties" (PDF). Sci. Rep. 4: 4001. arXiv: 1303.5966 . Bibcode:2014NatSR...4E4001K. doi:10.1038/srep04001. PMC   3918922 . PMID   24510159.
  2. J.-P. Eckmann, E. Moses, and D. Sergi. Entropy of dialogues creates coherent structures in e-mail traffic" Proc. Natl. Acad. Sci. USA 2004; 101:14333–14337. https://www.weizmann.ac.il/complex/EMoses/pdf/EntropyDialogues.pdf
  3. Eagle, N.; Pentland, A. (2006). "Reality mining: sensing complex social systems". Pers Ubiquit Comput. 10 (4): 255–268. doi:10.1007/s00779-005-0046-3. S2CID   1766202.
  4. Stehle, J.; Voirin, N.; Barrat, A.; Cattuto, C.; Colizza, V.; Isella, L.; Regis, C.; Pinton, J.-F.; Khanafer, N.; Vanhems, P. (2011). "Simulation of an SEIR infectious disease model on the dynamic contact network of conference attendees". BMC Medicine. 9: 87. arXiv: 1108.4841 . doi: 10.1186/1741-7015-9-87 . PMC   3162551 . PMID   21771290.
  5. Holme, P.; Saramäki, J. (2012). "Temporal Networks". Phys. Rep. 519 (3): 102. arXiv: 1108.1780 . Bibcode:2012PhR...519...97H. doi:10.1016/j.physrep.2012.03.001. S2CID   1920175.
  6. Holme, P.; Saramäki, J. (2012). "Temporal Networks". Phys. Rep. 519 (3): 99–100. arXiv: 1108.1780 . Bibcode:2012PhR...519...97H. doi:10.1016/j.physrep.2012.03.001. S2CID   1920175.
  7. Pastor-Satorras, R., and Alessandro Vespignani. Evolution and Structure of the Internet: A Statistical Physics Approach. Cambridge, UK: Cambridge UP, 2004. <http://fizweb.elte.hu/download/Fizikus-MSc/Infokommunikacios-halozatok-modelljei/Evo-and-Struct-of-Internet.pdf>
  8. Masuda, N; Holme, P (2013). "Predicting and controlling infectious disease epidemics using temporal networks". F1000Prime Rep. 5: 6. doi: 10.12703/P5-6 . PMC   3590785 . PMID   23513178.
  9. Thompson, Clive. "Are Your Friends Making You Fat?" The New York Times. The New York Times, 12 Sept. 2009. Web. <https://www.nytimes.com/2009/09/13/magazine/13contagion-t.html?pagewanted=all&_r=0>
  10. P. Holme, J. Saramäki. Temporal Networks. Phys. Rep. 519, 103–104; 10.1016/j.physrep.2012.03.001 (2012)
  11. P. Holme, J. Saramäki. Temporal Networks. Phys. Rep. 519, 104–105; 10.1016/j.physrep.2012.03.001 (2012)
  12. Holme, P. (2005). "Network reachability of real-world contact sequences". Phys Rev E. 71 (4): 046119. arXiv: cond-mat/0410313 . Bibcode:2005PhRvE..71d6119H. doi:10.1103/physreve.71.046119. PMID   15903738. S2CID   13249467.
  13. V. Nicosia, J. Tang, M. Musolesi, G. Russo, C. Mascolo, and V. Latora. Components in time-varying graphs. e-print arXiv : 1106.2134.
  14. 1 2 Lentz, Hartmut H. K.; Selhorst, Thomas; Sokolov, Igor M. (2013-03-11). "Unfolding Accessibility Provides a Macroscopic Approach to Temporal Networks". Physical Review Letters. 110 (11). American Physical Society (APS): 118701. arXiv: 1210.2283 . Bibcode:2013PhRvL.110k8701L. doi:10.1103/physrevlett.110.118701. ISSN   0031-9007. PMID   25166583. S2CID   10932514.
  15. Grindrod, P.; Parsons, M. C.; Higham, D. J.; Estrada, E. (2011). "Communicability across evolving networks" (PDF). Phys. Rev. E. 81 (4): 046120. Bibcode:2011PhRvE..83d6120G. doi:10.1103/PhysRevE.83.046120. PMID   21599253.
  16. Pan, R. K.; Saramaki, J. (2011). "Path lengths, correlations, and centrality in temporal networks". Phys. Rev. E. 84 (1): 016105. arXiv: 1101.5913 . Bibcode:2011PhRvE..84a6105P. doi:10.1103/PhysRevE.84.016105. PMID   21867255. S2CID   9306683.
  17. M. Lahiri and T. Y. Berger-Wolf. Mining periodic behavior in dynamic social networks. Eighth IEEE International Conference on Data Mining, 2008. http://compbio.cs.uic.edu/papers/LahiriBergerWolf_PeriodicBehavior08.pdf
  18. Q. Zhao, Y. Tian, Q. He, N. Oliver, R. Jin, and W.-C. Lee.Communication motifs: A tool to characterize social communications. In Proceedings of the 19th ACM international conference on Information and knowledge management, page 1645, 2010.
  19. A. Longa, G. Cencetti, B. Lepri and A. Passerini. An efficient procedure for mining egocentric temporal motifs. In Data Mining and Knowledge Discovery 36.1 (2022): 355-378
  20. Holme, P.; Saramäki, J. (2012). "Temporal Networks". Phys. Rep. 519 (3): 118–120. arXiv: 1108.1780 . Bibcode:2012PhR...519...97H. doi:10.1016/j.physrep.2012.03.001. S2CID   1920175.
  21. A. Vazquez, B. Racz, A. Lukacs, and A.-L. Barabasi. Impact of non-poissonian activity patterns on spreading processes" Phys. Rev. Lett. 98:158702, 2007. http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.98.158702
  22. Horváth, Dávid X; Kertész, János (2014-07-28). "Spreading dynamics on networks: the role of burstiness, topology and non-stationarity". New Journal of Physics. 16 (7): 073037. arXiv: 1404.2468 . Bibcode:2014NJPh...16g3037H. doi: 10.1088/1367-2630/16/7/073037 . ISSN   1367-2630.
  23. Gernat, Tim; Rao, Vikyath D.; Middendorf, Martin; Dankowicz, Harry; Goldenfeld, Nigel; Robinson, Gene E. (2018-02-13). "Automated monitoring of behavior reveals bursty interaction patterns and rapid spreading dynamics in honeybee social networks". Proceedings of the National Academy of Sciences. 115 (7): 1433–1438. Bibcode:2018PNAS..115.1433G. doi: 10.1073/pnas.1713568115 . ISSN   0027-8424. PMC   5816157 . PMID   29378954.
  24. Goh, K.-I.; Barabasi, A.-L. (2008). "Burstiness and memory in complex systems" (PDF). EPL. 81 (4): 48002. arXiv: physics/0610233 . Bibcode:2008EL.....8148002G. doi:10.1209/0295-5075/81/48002. S2CID   8352442.