When? Tuesday June 12 2018, 08:45 - 18:15
Where? L'Ecole de Musique - Republique
We proudly present a high-quality program of speakers representing different lines of research on higher-order models of complex systems.
| Time | Presenter |
|---|---|
| 08:45 - 09:00 | Organizers Opening Statement |
| Track 1 | Beyond Markov models |
| Track chair | Jian Xu |
| 09:00 - 09:30 | Kuansan Wang (Microsoft Research, USA) Invited Talk: A continuous representation of complex systemsDiscrete mathematics has been playing a central role in studying a complex system that can be intuitively represented as a network where its constituent components and their relationships can be modeled as nodes and links of the network. In recent years, however, we have seen more and more real-life data with inherent complexities that challenge the efficacies of the discrete model and the implied symbolic computing underneath it. In this talk, we use the scholarly communication network as an example to highlight the utilities as well as the limitations of a network representation, and describe our recent effort in exploring an alternative framework where the components of a complex system are first mapped into a Hilbert space so that continuous operations can be used to analyzed their behaviors and interactions, both spatially and temporarily. We demonstrate how partially observed or missing observations may be inferred and potentially recovered with continuous operations such as vector calculus and neighborhood search. The talk will also describe an open dataset and software tools with which we continue our exploration on this subject and on quantifying academic impacts presented in another satellite of this conference. |
| 09:30 - 10:00 | Bruno Ribeiro (Purdue University, USA) Invited Talk: High Order Network Embeddings with Subgraph Pattern Neural Networks In this talk we generalize traditional node/link prediction tasks in dynamic heterogeneous networks, to consider joint prediction over larger k-node induced subgraphs. The key insight is incorporating the unavoidable dependencies in the training observations of induced subgraphs into both the input features and the model architecture itself via high-order dependencies. The strength of the representation is its invariance to isomorphisms and varying local neighborhood sizes, while still being able to take node/edge labels into account in an inductive model which can be applied to unseen data. |
| 10:00 - 10:30 | Lucas Lacasa (Queen Mary University of London, UK) Invited Talk: Detecting hidden layers in networks via stochastic decomposition of non-Markovian dynamicsThe architecture of many complex systems is well described by multiplex interaction networks, and their dynamics is often the result of several intertwined processes taking place at different levels. However only in a few cases can such multi-layered architecture be empirically observed, as one usually only has experimental access to such structure from an aggregated projection. A fundamental question is thus to determine whether the hidden underlying architecture of complex systems is better modelled as a single interaction layer or results from the aggregation and interplay of multiple layers. In this talk I will show that, by only using local information provided by a random walker navigating the aggregated network, it is possible to decide in a robust way if the underlying structure is a multiplex and, in the latter case, to determine the most probable number of layers. The proposed methodology would also allow to select the optimal architecture capable of reproducing non-Markovian dynamics taking place on networks, such as human or animal mobility. Applications of this methodology in biophysics are finally discussed. |
| 10:30 - 11:00 | Coffee Break |
| 11:00 - 11:30 | Andrew Mellor (University of Oxford, UK) Invited Talk: Event Graphs: Time-unfolded Second-order Temporal Network ModelsRecent advances in data collection and storage have allowed both companies and researchers alike to collect data in real time. Much of this data comes in the form of 'events', or timestamped interactions, such as email, website clickstreams, or social media. This new data poses new challenges for modelling, especially if we wish to preserve the temporal features that this data permits. We propose a generalised framework to explore temporal networks using second-order time-unfolded models, called event graphs. Through examples we demonstrate how event graphs can be used to understand the topological-temporal structure of temporal networks, to model the evolution of collective behaviour, and to identify significant events in the network. Furthermore, we show that by modelling a temporal network as an event graph we can extend our analysis to non-dyadic interactions (known as hyper-events). |
| 11:30 - 12:00 | Michele Starnini (University of Barcelona, Spain) Invited Talk: Equivalence between non-Markovian and Markovian dynamics in epidemic spreading processesA general formalism is introduced to allow the steady state of non-Markovian processes on networks to be reduced to equivalent Markovian processes on the same substrates. The example of an epidemic spreading process is considered in detail, where all the non-Markovian aspects are shown to be captured within a single parameter, the effective infection rate. Remarkably, this result is independent of the topology of the underlying network, as demonstrated by numerical simulations on two-dimensional lattices and various types of random networks. Furthermore, an analytic approximation for the effective infection rate is introduced, which enables the calculation of the critical point and of the critical exponents for the non-Markovian dynamics. |
| 12:00 - 12:30 | Márton Karsai (Ecole Normale Supérieure de Lyon, France) Invited Talk: Weighted event graphs: a higher-order static representation of temporal-networksThe dynamics of diffusion-like processes on temporal networks are influenced by correlations in the times of contacts. This influence is particularly strong for processes where the spreading agent has a limited lifetime at nodes: disease spreading (recovery time), diffusion of rumors (lifetime of information), and passenger routing (maximum acceptable time between transfers). We introduce weighted event graphs as a powerful and fast framework for studying connectivity determined by time-respecting paths where the allowed waiting times between contacts have an upper limit. We study percolation on the weighted event graphs and in the underlying temporal networks, with simulated and real-world networks. We show that this type of temporal-network percolation is analogous to directed percolation, and that it can be characterized by multiple order parameters. |
| 12:30 - 14:00 | Lunch Break |
| Track 2 | Beyond dyadic interactions |
| Track chair | Michael Schaub |
| 14:00 - 14:30 | Austin Benson (Cornell University, USA) Invited Talk: Higher-order clustering in networks A fundamental property of complex networks is the tendency for edges to cluster. The extent of the clustering is typically quantified by the clustering coefficient, which is the probability that a length-2 path is closed, i.e., induces a triangle in the network. However, higher-order cliques beyond triangles are crucial to understanding complex networks, and the clustering behavior with respect to such higher-order network structures is not well understood. Here we introduce higher-order clustering coefficients that measure the closure probability of higher-order network cliques and provide a more comprehensive view of how the edges of complex networks cluster. Our higher-order clustering coefficients are a natural generalization of the traditional clustering coefficient. We derive several properties about higher-order clustering coefficients and analyze them under common random graph models. Finally, we use higher-order clustering coefficients to gain new insights into the structure of real-world networks from several domains. [Slides] [Software] [Paper] |
| 14:30 - 15:00 | Mariano Beguerisse (University of Oxford, UK) Invited Talk: Interpretable groups from tensor clustering with algebraic constraints In this talk I will present a novel tensor-based clustering method to extract sparse, low-dimensional structure from high-dimensional, multi-indexed datasets. Specifically, this framework is designed to enable the detection of clusters in the presence of structural requirements encoded as algebraic constraints in a linear program. This clustering method is general and can be tailored to a variety of applications in science and industry. I will show an application of the method on a collection of experiments measuring the response of genetically diverse breast cancer cell lines to an array of ligands. Each experiment consists of a cell line-ligand combination, and contains time-course measurements of the early-signalling kinases MAPK and AKT at two different ligand dose levels. By imposing appropriate structural constraints and respecting the multi-indexed structure of the data, the clustering can be optimized for biological interpretation and therapeutic understanding. Finally, I will present a systematic, large-scale exploration of mechanistic models of MAPK-AKT crosstalk for each cluster. This analysis captures the heterogeneity of breast cancer cell subtypes, and leads to hypotheses about the mechanisms by which cell lines respond to ligands. [Slides] |
| 15:00 - 15:30 | Alice Patania (Indiana University, USA) Invited Talk: The high-order shape of collaborations The structure of scientific collaborations has been the object of intense study both for its importance for innovation and scientific advancement, and as a model system for social group coordination and formation thanks to the availability of authorship data. Over the last years, complex networks approach to this problem have yielded important insights and shaped our understanding of scientific communities. We propose to complement the picture provided by network tools with that coming from using simplicial descriptions of publications and the corresponding topological methods. In this work, using papers as high-order representatives of scientific collaboration, we show that it is natural to extend the concept of triadic closure to simplicial complexes and show the presence of strong simplicial closure in a variety of different subjects. Through a topological study of the arXiv dataset we then show how homological cycles, that can intuitively be thought as hole in the network fabric, are an important part of the underlying community linking structure. |
| 15:30 - 16:00 | Coffee break |
| 16:00 - 16:30 | Barbara Mahler (University of Oxford, UK) Invited Talk: Analysis of contagion maps on a class of networks that are spatially embedded in a torus Spreading processes on geometric networks are often influenced by a network’s underlying spatial structure, and one can study the extent to which a spreading process follows that structure. In particular, considering a threshold contagion on a network whose nodes are embedded in a manifold and which has both ‘geometric edges’ that respect the geometry of the underlying manifold, as well as ‘non-geometric edges’ that are not constrained by the geometry of the underlying manifold, one can ask whether the contagion propagates as a wave front along the underlying geometry, or jumps via long non-geometric edges to remote areas of the network. Taylor et al developed a methodology aimed at determining the spreading behavior of threshold contagion models on such ‘noisy geometric networks’ [1]. This methodology is inspired by nonlinear dimensionality reduction and is centered around a so called ‘contagion map’ from the network’s nodes to a point cloud in high dimensional space. The structure of this point cloud reflects the spreading behavior of the contagion. We apply this methodology to a family of noisy-geometric networks that can be construed as being embedded in a torus. Constructing the contagion map and analyzing the structure of the resulting point cloud in terms of dimensionality, geometry and topology leads us to identify a region in the parameter space where the contagion propagates predominantly via wave front propagation. This consolidates contagion map as both a tool for investigating spreading behavior on spatial network, as well as a manifold learning technique. [1] D. Taylor, F. Klimm, H. A. Harrington, M. Kramar, K. Mischaikow, M. A. Porter, and P. J. Mucha. Complex contagions for topological data analysis of networks. Nature Communications, 6(4423) (2015). |
| 16:30 - 17:00 | Vsevolod Salnikov (University of Namur, Belgium) Invited Talk: Metamathematics with Persistent Homology The structure of the state of art of scientific research is an important object of study motivated by the understanding of how research evolves and how new fields of study stem from existing research. In the last years complex networks tools contributed to provide insights on the structure of research, through the study of collaboration, citation and co-occurrence networks, keyword co-occurrence networks in particular proved useful to provide maps of knowledge inside a scientific domain. The network approach focuses on pairwise relationships, often compressing multidimensional data structures and inevitably losing information. In this paper we propose to adopt a simplicial complex approach to word co-occurrences, providing a natural framework for the study of higher-order relations in the space of scientific knowledge. Using topological methods we explore the shape of concepts in mathematical research, focusing on homological cycles, regions with low connectivity in the simplicial structure, and we discuss their role in the understanding of the evolution of scientific research. In addition, we map authors’ contribution to the conceptual space, and explore their role in the formation of homological cycles. |
| 17:00 - 17:30 | Giona Casiraghi (ETH Zürich, Switzerland) Invited Talk: Statistical Selection of non-Dyadic Models for Dyadic Data The analysis of dyadic relational data from the perspective of networks has become a key method in the study of complex systems. However, despite this popularity, we still lack methods to answer a crucial question. Is it justified to model dyadic relational data using a network abstraction? Are higher-order models better suited for this task? In settings where observed interactions do not directly map to an underlying network topology, deciding how these interactions should be modelled is an important challenge. Closing this research gap requires model selection techniques that take into account both the complexity of a model and its explanatory power for the observed data. Going beyond previous works in network inference and graph identification, we exploit the broad class of generalised hypergeometric ensembles to address this gap. Building on this theoretical foundation, we develop a method to test hypotheses about the optimal representation of repeated dyadic interactions between the elements of a complex system. It particularly allows to test whether a network model is justified or not, or whether higher-order alternative models are better suited to explain the data. |
| --- | Live demo session |
| 17:30 - 17:40 | Jian Xu on behalf of Nitesh Chawla (University of Notre Dame) Anomaly detection in sequential data with higher-order network visualization tool HONVis |
| 17:40 - 17:50 | Ingo Scholtes (ETH Zürich) Higher-order network analysis and visualisation with pathpy2 |
| 17:50 - 18:00 | Daniel Edler (University of Umeå) Higher-order community detection with InfoMap |
| 18:00 - 18:15 | Organizers Closing Statement |