Dynamic hierarchies in temporal directed networks

Social networks contain implicit knowledge that can be used to infer hierarchical relations that are not explicitly present in the available data. Interaction patterns are typically affected by users' social relations. We present an approach to inferring such information that applies a link-analysis ranking algorithm at different levels of time granularity. In addition, a voting scheme is employed for obtaining the hierarchical relations. The approach is evaluated on two data...

Complex networks have emerged as a simple yet powerful framework to represent and analyze a wide range of complex systems. The problem of ranking the nodes and the edges in complex networks is critical for a broad range of real-world problems because it affects how we access online information and products, how success and talent are evaluated in human activities, and how scarce resources are allocated by companies and policymakers, among others. This calls for a deep underst...

An important concept in organisational behaviour is how hierarchy affects the voice of individuals, whereby members of a given organisation exhibit differing power relations based on their hierarchical position. Although there have been prior studies of the relationship between hierarchy and voice, they tend to focus on more qualitative small-scale methods and do not account for structural aspects of the organisation. This paper develops large-scale computational techniques u...

In this paper we explore the PageRank of temporal networks on both discrete and continuous time scales in the presence of personalization vectors that vary over time. Also the underlying interplay between the discrete and continuous settings arising from discretization is highlighted. Additionally, localization results that set bounds to the estimated influence of the personalization vector on the ranking of a particular node are given. The theoretical results are illustrated...

We present a physically-inspired model and an efficient algorithm to infer hierarchical rankings of nodes in directed networks. It assigns real-valued ranks to nodes rather than simply ordinal ranks, and it formalizes the assumption that interactions are more likely to occur between individuals with similar ranks. It provides a natural statistical significance test for the inferred hierarchy, and it can be used to perform inference tasks such as predicting the existence or di...

Graphs offer a generic abstraction for modeling entities, and the interactions and relationships between them. Most real world graphs, such as social and cooperation networks evolve over time, and exploring their evolution may reveal important information. In this paper, we present TempoGRAPHer, a system for visualizing and analyzing the evolution of a temporal attributed graph. TempoGRAPHer supports both temporal and attribute aggregation. It also allows graph exploration by...

The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems -- delay-tolerant networks, opportunistic-mobility networks, social networks -- obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe; and the formal models proposed so far to express some specific concepts are components of a larger formal description of this univ...

This document is the first part of the author's habilitation thesis (HDR), defended on June 4, 2018 at the University of Bordeaux. Given the nature of this document, the contributions that involve the author have been emphasized; however, these four chapters were specifically written for distribution to a larger audience. We hope they can serve as a broad introduction to the domain of highly dynamic networks, with a focus on temporal graph concepts and their interaction with ...

A temporal graph is a graph in which connections between vertices are active at specific times, and such temporal information leads to completely new patterns and knowledge that are not present in a non-temporal graph. In this paper, we study traversal problems in a temporal graph. Graph traversals, such as DFS and BFS, are basic operations for processing and studying a graph. While both DFS and BFS are well-known simple concepts, it is non-trivial to adopt the same notions f...

Real world networks exhibit rich temporal information: friends are added and removed over time in online social networks; the seasons dictate the predator-prey relationship in food webs; and the propagation of a virus depends on the network of human contacts throughout the day. Recent studies have demonstrated that static network analysis is perhaps unsuitable in the study of real world network since static paths ignore time order, which, in turn, results in static shortest p...