Dynamic hierarchies in temporal directed networks

Temporal networks model a variety of important phenomena involving timed interactions between entities. Existing methods for machine learning on temporal networks generally exhibit at least one of two limitations. First, time is assumed to be discretized, so if the time data is continuous, the user must determine the discretization and discard precise time information. Second, edge representations can only be calculated indirectly from the nodes, which may be suboptimal for t...

Centrality is an important notion in network analysis and is used to measure the degree to which network structure contributes to the importance of a node in a network. While many different centrality measures exist, most of them apply to static networks. Most networks, on the other hand, are dynamic in nature, evolving over time through the addition or deletion of nodes and edges. A popular approach to analyzing such networks represents them by a static network that aggregat...

Description of temporal networks and detection of dynamic communities have been hot topics of research for the last decade. However, no consensual answers to these challenges have been found due to the complexity of the task. Static communities are not well defined objects, and adding a temporal dimension renders the description even more difficult. In this article, we propose a coherent temporal clustering method: the Best Combination of Local Communities (BCLC). Our method ...

Evolving graphs arise in problems where interrelations between data change over time. We present a breadth first search (BFS) algorithm for evolving graphs that computes the most direct influences between nodes at two different times. Using simple examples, we show that naive unfoldings of adjacency matrices miscount the number of temporal paths. By mapping an evolving graph to an adjacency matrix of an equivalent static graph, we prove that our generalization of the BFS algo...

Community finding algorithms for networks have recently been extended to dynamic data. Most of these recent methods aim at exhibiting community partitions from successive graph snapshots and thereafter connecting or smoothing these partitions using clever time-dependent features and sampling techniques. These approaches are nonetheless achieving longitudinal rather than dynamic community detection. We assume that communities are fundamentally defined by the repetition of inte...

We present a method to find the best temporal partition at any time-scale and rank the relevance of partitions found at different time-scales. This method is based on random walkers coevolving with the network and as such constitutes a generalization of partition stability to the case of temporal networks. We show that, when applied to a toy model and real datasets, temporal stability uncovers structures that are persistent over meaningful time-scales as well as important iso...

We initiate an open-source library for the efficient analysis of temporal graphs. We consider one of the standard models of dynamic networks in which each edge has a discrete timestamp and transition time. Recently there has been a massive interest in analyzing such temporal graphs. Common computational data mining and analysis tasks include the computation of temporal distances, centrality measures, and network statistics like topological overlap, burstiness, or temporal dia...

Many social and biological systems are characterized by enduring hierarchies, including those organized around prestige in academia, dominance in animal groups, and desirability in online dating. Despite their ubiquity, the general mechanisms that explain the creation and endurance of such hierarchies are not well understood. We introduce a generative model for the dynamics of hierarchies using time-varying networks in which new links are formed based on the preferences of no...

A temporal graph is a graph in which edges are assigned a time label. Two nodes u and v of a temporal graph are connected one to the other if there exists a path from u to v with increasing edge time labels. We consider the problem of assigning time labels to the edges of a digraph in order to maximize the total reachability of the resulting temporal graph (that is, the number of pairs of nodes which are connected one to the other). In particular, we prove that this problem i...

In this work we consider \emph{temporal networks}, i.e. networks defined by a \emph{labeling} $\lambda$ assigning to each edge of an \emph{underlying graph} $G$ a set of \emph{discrete} time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on \emph{path problems} of temporal networks. In particular, we consider \emph{time-respecting} paths, i.e. paths whose edges are assigned by $\lambda$ a s...