Foundations (F) Session 11
Time and Date: 16:00  17:20 on 22nd Sep 2016
Room: A  Administratiezaal
Chair: Rick Quax
311  Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star?
[abstract]
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.
Close

Gergely Palla and Daniel Czegel 
10  The effects of the interplay between nodes’ activity and attractiveness on random walks in timevarying networks
[abstract]
Abstract: Several realworld spreading and diﬀusion processes take place on timevarying networks. In general, the process dynamics are aﬀected 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 diﬀusion 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 ﬁxed 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 diﬀusion of random walk processes and on the transport dynamics. We introduce a timevarying network model where each node is characterized by a ﬁxed activity rate, giving the probability of engaging in interaction per time unit, and a ﬁxed 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 facetoface interaction networks, where the attractiveness may account for individuals’ diﬀerent degree of social appeal. By clarifying the impact of this characteristic network feature on the diﬀusion of random walks, our ﬁndings can potentially shed light on realworld dynamical processes such as opinion and epidemics spreading on social networks.
Close

Laura Maria Alessandretti, Andrea Baronchelli and Nicola Perra 
191  Aggregation of link streams for multiscale analysis
[abstract]
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 timevarying graphs, model many realworld interactions between individuals, email exchanges, or network traffic. Realworld 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 realworld 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.
Close

Hindol Rakshit, Tiphaine Viard and Robin LamarchePerrin 
214  Systematic ranking of temporal and topological patterns for controlling dynamical processes on networks
[abstract]
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, weekend). 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 susceptibleinfected 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.
Close

Anna Sapienza, Laetitia Gauvin and Ciro Cattuto 