There is an ever-increasing interest in investigating dynamics in time-varying graphs (TVGs). Nevertheless, so far, the notion of centrality in TVG scenarios usually refers to metrics that assess the relative importance of nodes along the temporal evolution of the dynamic complex network. For some TVG scenarios, however, more important than identifying the central nodes under a given node centrality definition is identifying the key time instants for taking certain actions. In this paper, we thus introduce and investigate the notion of time centrality in TVGs. Analogously to node centrality, time centrality evaluates the relative importance of time instants in dynamic complex networks. In this context, we present two time centrality metrics related to diffusion processes. We evaluate the two defined metrics using both a real-world dataset representing an in-person contact dynamic network and a synthetically generated randomized TVG. We validate the concept of time centrality showing that diffusion starting at the best ranked time instants (i.e., the most central ones), according to our metrics, can perform a faster and more efficient diffusion process.
A large number of works on dynamic complex networks concerns both data structures to model TVGs and different definitions of node centrality in that context. The first works that attempted to represent TVGs were influenced by traditional graph modeling. For instance, a number of works model TVGs through a sequence of static subgraphs that represents the network dynamics in a discrete way as time passes @cite_0 @cite_17 @cite_13 @cite_12 @cite_5 @cite_3 @cite_22 .
@cite_22 @cite_3 @cite_0 @cite_5 @cite_13 @cite_12 @cite_17
2059763605 2139322472 2739147373 2164641477 1981599289 1982459859
Connections in complex networks are inherently fluctuating over time and exhibit more dimensionality than analysis based on standard static graph measures can capture. Here, we introduce the concepts of temporal paths and distance in time-varying graphs. We define as temporal small world a time-varying graph in which the links are highly clustered in time, yet the nodes are at small average temporal distances. We explore the small-world behavior in synthetic time-varying networks of mobile agents and in real social and biological time-varying systems. The study of influential members of human networks is an important research question in social network analysis. However, the current state-of-the-art is based on static or aggregated representation of the network topology. We argue that dynamically evolving network topologies are inherent in many systems, including real online social and technological networks: fortunately the nature of these systems is such that they allow the gathering of large quantities of finegrained temporal data on interactions amongst the network members. In this paper we propose novel temporal centrality metrics which take into account such dynamic interactions over time. Using a real corporate email dataset we evaluate the important individuals selected by means of static and temporal analysis taking two perspectives: firstly, from a semantic level, we investigate their corporate role in the organisation; and secondly, from a dynamic process point of view, we measure information dissemination and the role of information mediators. We find that temporal analysis provides a better understanding of dynamic processes and a more accurate identification of important people compared to traditional static methods. New technologies and the deployment of mobile and nomadic services are driving the emergence of complex communications networks, that have a highly dynamic behavior. This naturally engenders new route-discovery problems under changing conditions over these networks. In this paper, we use and extend a recently proposed graph theoretic model, which helps capture the evolving characteristic of such networks, in order to propose and formally analyze least cost journeys (the analog of paths in usual graphs) in a class of dynamic networks, where the changes in the topology can be predicted in advance. Cost measures investigated here are hop count (shortest journeys), arrival date (foremost journeys), and time span (fastest journeys). The analysis of social and technological networks has attracted a lot of attention as social networking applications and mobile sensing devices have given us a wealth of real data. Classic studies looked at analysing static or aggregated networks, i.e., networks that do not change over time or built as the results of aggregation of information over a certain period of time. Given the soaring collections of measurements related to very large, real network traces, researchers are quickly starting to realise that connections are inherently varying over time and exhibit more dimensionality than static analysis can capture. In this paper we propose new temporal distance metrics to quantify and compare the speed (delay) of information diffusion processes taking into account the evolution of a network from a local and global view. We show how these metrics are able to capture the temporal characteristics of time-varying graphs, such as delay, duration and time order of contacts (interactions), compared to the metrics used in the past on static graphs. As a proof of concept we apply these techniques to two classes of time-varying networks, namely connectivity of mobile devices and e-mail exchanges. We use real-world contact sequences, time-ordered lists of contacts from one person to another, to study how fast information or disease can spread across network of contacts. Specifically we measure the reachability time the average shortest time for a series of contacts to spread information between a reachable pair of vertices (a pair where a chain of contacts exists leading from one person to the other) and the reachability ratio the fraction of reachable vertex pairs. These measures are studied using conditional uniform graph tests. We conclude, among other things, that the network reachability depends much on a core where the path lengths are short and communication frequent, that clustering of the contacts of an edge in time tends to decrease the reachability, and that the order of the contacts really does make sense for dynamical spreading processes. Wireless technologies and the deployment of mobile and nomadic services are driving the emergence of complex ad hoc networks that have a highly dynamic behavior. Modeling such dynamics and creating a reference model on which results could be compared and reproduced, was stated as a fundamental issue by a recent NSF workshop on networking. In this article we show how the modeling of time-changes unsettles old questions and allows for new insights into central problems in networking, such as routing metrics, connectivity, and spanning trees. Such modeling is made possible through evolving graphs, a simple combinatorial model that helps capture the behavior or dynamic networks over time.