Abstract: Signs of hierarchy are prevalent in a wide range of systems in nature and society. One of the key problems is quantifying the importance of hierarchical organisation in the structure of the network representing the interactions or connections between the fundamental units of the studied system. Although a number of notable methods are already available, their vast majority is treating all directed acyclic graphs as already maximally hierarchical. Here we propose a hierarchy measure based on random walks on the network. The novelty of our approach is that directed trees corresponding to multi level pyramidal structures obtain higher hierarchy scores compared to directed chains and directed stars. Furthermore, in the thermodynamic limit the hierarchy measure of regular trees is converging to a well defined limit depending only on the branching number. When applied to real networks, our method is computationally very effective, as the result can be evaluated with arbitrary precision by subsequent multiplications of the transition matrix describing the random walk process. In addition, the tests on real world networks provided very intuitive results, e.g., the trophic levels obtained from our approach on a food web were highly consistent with former results from ecology.

Abstract: Several real-world spreading and diffusion processes take place on time-varying networks. In general, the process dynamics are affected by changes of the topological structure. To understand the impact of temporal connectivity patterns, several studies have focused on the analysis of random walks, as they represent a paradigm for all diffusion processes. It was shown that the temporal connectivity patterns introduce features not found in the equivalent processes in quenched or annealed networks. The case of random walks on activity driven networks, where each node engages in interaction according to a fixed activity rate, is particularly transparent since its stationary state was derived analytically. However, this model accounts only for the heterogeneous activity of nodes, irrespectively of their potential to attract other connections. Here, we focus on the role played by the distribution of nodes with respect to their attractiveness, clarifying its impact on the diffusion of random walk processes and on the transport dynamics. We introduce a time-varying network model where each node is characterized by a fixed activity rate, giving the probability of engaging in interaction per time unit, and a fixed attractiveness rate, specifying the probability to receive a connection from an active node. We derive analytically the stationary state of the process and study the interplay between the distributions of nodes’ activity and attractiveness. Interestingly, the introduction of heterogeneous attractiveness distributions alters substantially the dynamical properties of the process and creates a rich phenomenology. Models based on heterogeneous attractiveness were introduced to explain features of face-to-face interaction networks, where the attractiveness may account for individuals’ different degree of social appeal. By clarifying the impact of this characteristic network feature on the diffusion of random walks, our findings can potentially shed light on real-world dynamical processes such as opinion and epidemics spreading on social networks.

Abstract: A link stream L models interactions over time: a link (b, e, u, v) is in L if two entities (nodes) u and v have continuously interacted from time b to time e. Link streams, also called temporal networks or time-varying graphs, model many real-world interactions between individuals, email exchanges, or network traffic. Real-world link streams typically contain millions, or even billions of interactions, and handling them computationally is a challenge in itself. Hence, module decomposition based aggregation is a possible approach to construct a smaller and more observable image of a link stream. In our study, we generalize the definition of modules to link streams. In a graph, a module M is a subset of nodes that have the same neighborhood. Analogously, we define a module in a link stream as a couple (M, T) consisting of a set of nodes M and a time duration T (not necessarily an interval) such that all nodes in M share the same neighborhood over T. With the goal of achieving more meaningful (yet lossy) module decomposition of real world datasets, we reduce the stringency of module definition to introduce “relaxed” modules. Intuitively, a relaxed module (M, T) is such that the neighborhoods’ similarities of nodes in M over T are higher than a given threshold. We define a relevant measure of spatiotemporal neighborhood similarity. Beyond the theoretical scope of our work, we use modules in link streams as a mean of compression of large real-world datasets. In addition to reducing the amount of computational resources to process the stream, compression has applications in event and mesoscale structure detection, at the cost of optimizable loss in information. Hence, we finally investigate the reconstruction error induced by link stream compression, and discuss possible ways to minimize this error.

Abstract: To speed up information propagation or mitigate disease spreading calls for an investigation of the interplay between dynamical processes and temporal network. Temporal (e.g. burstiness) and topological (e.g. community structure) network characteristics have been indeed shown to influence such processes. Following these findings, techniques to influence the dynamics of a process have been built on using either temporal or structural informations, but designing such intervention strategy on their coupling is still challenging. Here we propose a generative model of temporal networks where we can control separately temporal and topological structures and combine them. A temporal network is built from subnetworks whose links have a correlated activity. The underlying assumption is that individuals are usually engaged in different social activities (e.g. work, spare time) involving different people at different times (e.g. week, week-end). Each subnetwork can be seen as representing one of these social activities. Moreover, the hypothesis of such modeling is supported by previous works using tensor factorization, that both shows the existence of correlated activity patterns in networks and enables to extract them. Using this model, we generated synthetic networks resulting from several subnetworks. Each subnetwork is built from a static network whose activity is modulated in time. We considered subnetworks with various clustering coefficients and activity profiles. We simulated a susceptible-infected process over each network and over the networks generated by the removal of one subnetwork at a time to measure the impact of each of them on the dynamic process. It led to the identification of subnetworks - with their respective temporal and topological structure - having an impact on the process. The clustering coefficient value was found to be the most decisive factor to predict the impact on the spreading process. The model architecture allows to extend the study to richer temporal patterns.