Past Networks Seminar

The talk introduces an analytical framework for examining socio-spatial segregation across various spatial scales. This framework considers regional connectivity and population distribution, using an information theoretic approach to measure changes in socio-spatial segregation patterns across scales. It identifies scales where both high segregation and low connectivity occur, offering a topological and spatial perspective on segregation. Illustrated through a case study in Ecuador, the method is demonstrated to identify disconnected and segregated regions at different scales, providing valuable insights for planning and policy interventions.

Complex networks have become the main paradigm for modeling the dynamics of interacting systems. However, networks are intrinsically limited to describing pairwise interactions, whereas real-world systems are often characterized by interactions involving groups of three or more units. In this talk, I will consider social systems as a natural testing ground for higher-order network approaches (hypergraphs and simplicial complexes). I will briefly introduce models of social contagion and norm evolution on hypergraphs to show how the inclusion of higher-order mechanisms can lead to the emergence of novel phenomena such as discontinuous transitions and critical mass effects. I will then present some recent results on the role that structural features play on the emergent dynamics, and introduce a measure of hyper-coreness to characterize the centrality of nodes and inform seeding strategies. Finally, I will delve into the microscopic dynamics of empirical higher-order structures. I will study the mechanisms governing their temporal dynamics both at the node and group level, characterizing how individuals navigate groups and how groups form and dismantle. I will conclude by proposing a dynamical hypergraph model that closely reproduces the empirical observations.
 

TBA

Complex networks usually exhibit a rich architecture organized over multiple intertwined scales. Information pathways are expected to pervade these scales reflecting structural insights that are not manifest from analyses of the network topology. Moreover, small-world effects correlate with the different network hierarchies complicating identifying coexisting mesoscopic structures and functional cores. We present a communicability analysis of effective information pathways throughout complex networks based on information diffusion to shed further light on these issues. This leads us to formulate a new renormalization group scheme for heterogeneous networks. The Renormalization Group is the cornerstone of the modern theory of universality and phase transitions, a powerful tool to scrutinize symmetries and organizational scales in dynamical systems. However, its network counterpart is particularly challenging due to correlations between intertwined scales. The Laplacian RG picture for complex networks defines both the supernodes concept à la Kadanoff, and the equivalent momentum space procedure à la Wilson for graphs.

What do football passes and financial transactions have in common? Both are observable events in some real-world walk process that is happening over some network that is, however, not directly observable. In both cases, the basis for record-keeping is that these events move something tangible from one node to another. Here we explore process-driven approaches towards analyzing such data, with the goal of answering domain-specific research questions. First, we consider transaction data from a digital community currency recorded over 16 months. Because these are records of a real-world walk process, we know that the time-aggregated network is a flow network. Flow-based network analysis techniques let us concisely describe where and among whom this community currency was circulating. Second, we use a technique called trajectory extraction to transform football match event data into passing sequence data. This allows us to replicate classic results from sports science about possessions and uncover intriguing dynamics of play in five first-tier domestic leagues in Europe during the 2017-18 club season. Taken together, these two applied examples demonstrate the interpretability of process-driven approaches as opposed to, e.g., temporal network analysis, when the data are records of a real-world walk processes.

Understanding the stability of ecological communities is a matter of increasing importance in the context of global environmental change. Yet it has proved to be a challenging task. Different metrics are used to assess the stability of ecological systems, and the choice of one metric over another may result in conflicting conclusions. While the need to consider this multitude of stability metrics has been clearly stated in the ecological literature for decades, little is known about how different stability metrics relate to each other. I’ll present results of dynamical simulations of ecological communities investigating the correlations between frequently used stability metrics, and I will discuss how these results may contribute to make progress in the quantification of stability in theory and in practice.

Zoom Link: https://zoom.us/j/93174968155?pwd=TUJ3WVl1UGNMV0FxQTJQMFY0cjJNdz09

Meeting ID: 931 7496 8155

Passcode: 502784

Many networks exhibit some community structure. There exists a wide variety of approaches to detect communities in networks, each offering different interpretations and associated algorithms. For large networks, there is the additional requirement of speed. In this context, the so-called label propagation algorithm (LPA) was proposed, which runs in near linear time. In partitions uncovered by LPA, each node is ensured to have most links to its assigned community. We here propose a fast variant of LPA (FLPA) that is based on processing a queue of nodes whose neighbourhood recently changed. We test FLPA exhaustively on benchmark networks and empirical networks, finding that it runs up to 700 times faster than LPA. In partitions found by FLPA, we prove that each node is again guaranteed to have most links to its assigned community. Our results show that FLPA is generally preferable to LPA.

Spectral methods offer a tractable, global framework for clustering in graphs via eigenvector computations on graph matrices. Hypergraph data, in which entities interact on edges of arbitrary size, poses challenges for matrix representations and therefore for spectral clustering. We study spectral clustering for arbitrary hypergraphs based on the hypergraph nonbacktracking operator. After reviewing the definition of this operator and its basic properties, we prove a theorem of Ihara-Bass type which allows eigenpair computations to take place on a smaller matrix, often enabling faster computation. We then propose an alternating algorithm for inference in a hypergraph stochastic blockmodel via linearized belief-propagation which involves a spectral clustering step, again using nonbacktracking operators. We provide proofs related to this algorithm that both formalize and extend several previous results. We pose several conjectures about the limits of spectral methods and detectability in hypergraph stochastic blockmodels in general, supporting these with in-expectation analysis of the eigeinpairs of our studied operators. We perform experiments with real and synthetic data that demonstrate the benefits of hypergraph methods over graph-based ones when interactions of different sizes carry different information about cluster structure.

Joint work with Nicole Eikmeier (Grinnell) and Jamie Haddock (Harvey Mudd).

Identifying the hidden organizational principles and relevant structures of complex networks is fundamental to understand their properties. To this end, uncovering the structures involving the prominent nodes in a network is an effective approach. In temporal networks, the simultaneity of connections is crucial for temporally stable structures to arise. In this work, we propose a measure to quantitatively investigate the tendency of well-connected nodes to form simultaneous and stable structures in a temporal network. We refer to this tendency as the temporal rich club phenomenon, characterized by a coefficient defined as the maximal value of the density of links between nodes with a minimal required degree, which remain stable for a certain duration. We illustrate the use of this concept by analysing diverse data sets and their temporal properties, from the role of cohesive structures in relation to processes unfolding on top of the network to the study of specific moments of interest in the evolution of the network.

Article link: https://www.nature.com/articles/s41567-022-01634-8

The structure of complex networks can be characterized by counting and analyzing network motifs, which are small graph structures that occur repeatedly in a network, such as triangles or chains. Recent work has generalized motifs to temporal and dynamic network data. However, existing techniques do not generalize to sequential or trajectory data, which represents entities walking through the nodes of a network, such as passengers moving through transportation networks. The unit of observation in these data is fundamentally different, since we analyze observations of walks (e.g., a trip from airport A to airport C through airport B), rather than independent observations of edges or snapshots of graphs over time. In this work, we define sequential motifs in trajectory data, which are small, directed, and sequenced-ordered graphs corresponding to patterns in observed sequences. We draw a connection between counting and analysis of sequential motifs and Higher-Order Network (HON) models. We show that by mapping edges of a HON, specifically a kth-order DeBruijn graph, to sequential motifs, we can count and evaluate their importance in observed data, and we test our proposed methodology with two datasets: (1) passengers navigating an airport network and (2) people navigating the Wikipedia article network. We find that the most prevalent and important sequential motifs correspond to intuitive patterns of traversal in the real systems, and show empirically that the heterogeneity of edge weights in an observed higher-order DeBruijn graph has implications for the distributions of sequential motifs we expect to see across our null models.

ArXiv link: https://arxiv.org/abs/2112.05642

Social, biological and physical systems are widely studied through the modeling of dynamical processes over networks, and one commonly investigates the interplay between structure and dynamics. I will discuss how cyclic patterns in networks can influence models for collective and diffusive processes, including generalized models in which dynamics are defined over simplicial complexes and multiplex networks. Our approach relies on homology theory, which is the subfield of mathematics that formally studies cycles (and more generally, k-dimensional holes). We will make use of techniques including persistent homology and Hodge theory to examine the role of cycles in helping organize dynamics onto low-dimensional manifolds. This pursuit represents an emerging interface between the fields of network-coupled dynamical systems and topological data analysis.

Combining physics with machine learning is a rapidly growing field of research. Thereby, most work focuses on leveraging machine learning methods to solve problems in physics. Here, however, we focus on the reverse direction of leveraging structure of physical systems (e.g. dynamical systems modeled by ODEs or PDEs) to construct novel machine learning algorithms, where the existence of highly desirable properties of the underlying method can be rigorously proved. In particular, we propose several physics-inspired deep learning architectures for sequence modelling as well as for graph representation learning. The proposed architectures mitigate central problems in each corresponding domain, such as the vanishing and exploding gradients problem for recurrent neural networks or the oversmoothing problem for graph neural networks. Finally, we show that this leads to state-of-the-art performance on several widely used benchmark problems.

Chimera states have attracted significant attention as symmetry-broken states exhibiting the coexistence of coherence and incoherence. Despite the valuable insights gained by analyzing specific systems, the understanding of the physical mechanism underlying the emergence of chimeras has been incomplete. In this presentation, I will argue that an important class of stable chimeras arise because coherence in part of the system is sustained by incoherence in the rest of the system. This mechanism may be regarded as a deterministic analog of noise-induced synchronization and is shown to underlie the emergence of so-called strong chimeras. These are chimera states whose coherent domain is formed by identically synchronized oscillators. The link between coherence and incoherence revealed by this mechanism also offers insights into the dynamics of a broader class of states, including switching chimera states and incoherence-mediated remote synchronization.

Synchronization, epidemic processes and information spreading are natural processes that emerge from the interaction between people. Mathematically, all of them can be described by models that, despite their simplicity, they can predict collective behaviors. In addition, they have in common a very interesting feature: a phase transition from an active state to an absorbing state. For example, the spread of an epidemic is characterized by the infection rate, the control parameter, which basically determines whether the epidemic will spread in the network or, if this rate is very low, few people become infected and the system falls into an absorbing state where there are no more infected people. In this presentation we will present the analytical and computational approaches used to investigate these classical models of statistical physics that present phase transitions and we will also show how the network topology influences such dynamical processes. The behavior of such dynamics can be much richer than we imagine.

Co-occurrence networks formed by bipartite projection are widely studied in many contexts, including politics (bill co-sponsorship), bibliometrics (paper co-authorship), ecology (species co-habitation), and genetics (protein co-expression). It is often useful to focus on the backbone, a binary representation that includes only the most important edges, however many different backbone extraction models exist. In this talk, I will demonstrate the "backbone" package for R, which implements many such models. I will also use it to compare two promising null models: the fixed degree sequence model (FDSM) that imposes hard constraints, and the stochastic degree sequence model (SDSM) that imposes soft constraints, on the bipartite degree sequences. While FDSM is more statistically powerful, SDSM is more efficient and offers a close approximation.

In this talk I will present network-theoretic tools [1-2] to filter information in large-scale datasets and I will show that these are powerful tools to study complex datasets. In particular I will introduce correlation-based information filtering networks and the planar filtered graphs (PMFG) and I will show that applications to financial data-sets can meaningfully identify industrial activities and structural market changes [3-4].

It has been shown that by making use of the 3-clique structure of the PMFG a clustering can be extracted allowing dimensionality reduction that keeps both local information and global hierarchy in a deterministic manner without the use of any prior information [5-6]. However, the algorithm so far proposed to construct the PMFG is numerically costly with O(N3) computational complexity and cannot be applied to large-scale data. There is therefore scope to search for novel algorithms that can provide, in a numerically efficient way, such a reduction to planar filtered graphs. I will introduce a new algorithm, the TMFG (Triangulated Maximally Filtered Graph), that efficiently extracts a planar subgraph which optimizes an objective function. The method is scalable to very large datasets and it can take advantage of parallel and GPUs computing [7]. Filtered graphs are valuable tools for risk management and portfolio optimization too [8-9] and they allow to construct probabilistic sparse modeling for financial systems that can be used for forecasting, stress testing and risk allocation [10].

Filtered graphs can be used not only to extract relevant and significant information but more importantly to extract knowledge from an overwhelming quantity of unstructured and structured data. I will provide a practitioner example by a successful Silicon Valley start-up, Yewno. The key idea underlying Yewno’s products is the concept of the Knowledge Graph, a framework based on filtered graph research, whose goal is to extract signals from evolving corpus of data. The common principle is that a methodology leveraging on developments in Computational linguistics and graph theory is used to build a graph representation of knowledge [11], which can be automatically analysed to discover hidden relations between components in many different complex systems. This Knowledge Graph based framework and inference engine has a wide range of applications, including finance, economics, biotech, law, education, marketing and general research.

[1] T. Aste, T. Di Matteo, S. T. Hyde, Physica A 346 (2005) 20.

[2] T. Aste, Ruggero Gramatica, T. Di Matteo, Physical Review E 86 (2012) 036109.

[3] M. Tumminello, T. Aste, T. Di Matteo, R. N. Mantegna, PNAS 102, n. 30 (2005) 10421.

[4] N. Musmeci, Tomaso Aste, T. Di Matteo, Journal of Network Theory in Finance 1(1) (2015) 1-22.

[5] W.-M. Song, T. Di Matteo, and T. Aste, PLoS ONE 7 (2012) e31929.

[6] N. Musmeci, T. Aste, T. Di Matteo, PLoS ONE 10(3): e0116201 (2015).

[7] Guido Previde Massara, T. Di Matteo, T. Aste, Journal of Complex networks 5 (2), 161 (2016).

[8] F. Pozzi, T. Di Matteo and T. Aste, Scientific Reports 3 (2013) 1665.

[9] N. Musmeci, T. Aste and T. Di Matteo, Scientific Reports 6 (2016) 36320.

[10] Wolfram Barfuss, Guido Previde Massara, T. Di Matteo, T. Aste, Phys.Rev. E 94 (2016) 062306.

[11] Ruggero Gramatica, T. Di Matteo, Stefano Giorgetti, Massimo Barbiani, Dorian Bevec and Tomaso Aste, PLoS One (2014) PLoS ONE 9(1): e84912.

Pair combination repurposing of drugs is a common challenge faced by researchers in the pharmaceutical industry. Network biology and molecular machine learning based drug pair scoring techniques offer computation tools to predict the interaction, polypharmacy side effects and synergy of drugs. In this talk we overview of three things: (a) the theory and unified model of drug pair scoring (b) a relational machine learning model that can solve the pair scoring task (c) the design of large-scale machine learning systems needed to tackle the pair scoring task.

ArXiv links: https://arxiv.org/abs/2111.02916, https://arxiv.org/abs/2110.15087, https://arxiv.org/abs/2202.05240.

ML library: https://github.com/AstraZeneca/chemicalx

Random walks are a common model for the exploration and discovery of complex networks. While numerous algorithms have been proposed to map out an unknown network, a complementary question arises: in a known network, which nodes and edges are most likely to be discovered by a random walker in finite time? In this talk we introduce exposure theory, a statistical mechanics framework that predicts the learning of nodes and edges across several types of networks, including weighted and temporal, and show that edge learning follows a universal trajectory. While the learning of individual nodes and edges is noisy, exposure theory produces a highly accurate prediction of aggregate exploration statistics. As a specific application, we extend exposure theory to better understand human learning with its typical mental errors, and thus account for distortions of learned networks.

This talk is based on https://arxiv.org/abs/2202.11262

In this talk we will look at the different ways to define city boundaries, and the relevance to consider socio-demographic and spatial connectivity in urban systems, in particular if interventions are to be considered.

Data that have an intrinsic network structure are becoming increasingly common in various scientific applications. Compressing such data for storage or transmission is an important problem, especially since networks are increasingly large. From an information theoretic perspective, the limit to compression of a random graph is given by the Shannon entropy of its distribution. A relevant question is how much of the information content of a random graph pertains to its structure (i.e., the unlabelled version of the graph), and how much of it is contained in the labels attached to the structure. Furthermore, in applications in which one is interested only in structural properties of a graph (e.g., node degrees, connectedness, frequency of occurrence of certain motifs), the node labels are irrelevant, such that only the structure of the graph needs to be compressed, leading to a more compact representation. In this talk, I will consider the random geometric graph (RGG), where pairs of nodes are connected based on the distance between them in some latent space. This model captures well important characteristics of biological systems, information networks, social networks, or economic networks. Since determination of the entropy is extremely difficult for this model, I will present upper bounds we obtained for the entropy of the labelled RGG. Then, we will focus on the structural information in the one-dimensional RGG. I will show our latest results in terms of the number of structures in the considered model and bounds on the structural entropy, together with the asymptotic behaviour of the bounds for different regimes of the connection range. Finally, I will also present a simple encoding scheme for one-dimensional RGG structures that asymptotically achieves the obtained upper limit on the structural entropy.

arXiv link: https://arxiv.org/abs/2107.13495

The non-backtracking matrix and its eigenvalues have many applications in network science and graph mining. For example, in network epidemiology, the reciprocal of the largest eigenvalue of the non-backtracking matrix is a good approximation for the epidemic threshold of certain network dynamics. In this work, we develop techniques that identify which nodes have the largest impact on the leading non-backtracking eigenvalue. We do so by studying the behavior of the spectrum of the non-backtracking matrix after a node is removed from the graph, which can be thought of as immunizing a node against the spread of disease. From this analysis we derive a centrality measure which we call X-degree, which is then used to predict which nodes have a large influence in the epidemic threshold. Finally, we discuss work currently in progress on connections with eigenvector localization and percolation theory.

Measures of discrete curvature are a recent addition to the toolkit of network analysts and data scientists. At the basis lies the idea that networks and other discrete objects exhibit distinct geometric properties that resemble those of smooth objects like surfaces and manifolds, and that we can thus find inspiration in the tools of differential geometry to study these discrete objects. In this talk, I will introduce how this has lead to the development of notions of discrete curvature, and what they are good for. Furthermore, I will discuss our latest results on a new notion of curvature on graphs, based on the effective resistance. These new "resistance curvatures" are related to other well-known notions of discrete curvature (Ollivier, Forman, combinatorial curvature), we find evidence for convergence to continuous curvature in the case of Euclidean random graphs and there is a naturally associated discrete Ricci flow.

A preprint on this work is available on arXiv: https://arxiv.org/abs/2201.06385