Thursday Lightnings

Turing patterns, hallmarks of self-organized processes, emerge when ordered structures arise from initial disorder due to the complex nonlinear interactions between the elements of a system. Initially studied in continuous settings, these patterns have recently been explored on networks, where nodes represent spatial regions hosting local reactions between two chemical species, the activator and the inhibitor, while edges model the diffusion process. This approach has made it possible to study Turing instability on graphs, but also on undirected hypergraphs. In this work, we develop a theory of Turing instability on m-directed hypergraphs. These structures generalize hypergraphs by dividing the nodes of a hyperedge into two disjoint sets: tail nodes and head nodes. This directionality introduces a privileged mechanism in which the collective action of tail nodes drives the reactions involving head nodes. This generalization thus provides an extended framework compared to traditional directed networks. Using linear stability analysis, we demonstrate that the directionality of m-directed hypergraphs promotes Turing instability, enabling the emergence of stationary or wave-like patterns within parameter regimes inaccessible to symmetric configurations. We also derive two specific Laplace matrices that allow for a rigorous analytical characterization of these patterns. The theoretical findings are validated through simulations using the Brusselator model, applied to a directed m-hyperring and a directed random hypergraph. Our work highlights the crucial role of directionality in the emergence of Turing patterns and broadens the traditional frameworks of network theory.

In this work, we developed a high-performance individual-based simulation to investigate biofilm formation driven by mutualistic interactions. Our results reveal that the system undergoes a sharp phase transition from a planktonic state to a biofilm state as the ratio of mutualistic to competitive interactions increases. Furthermore, we find that the critical point of this transition depends on the specific topology of the interaction network. Using mathematical arguments, we explain this transition as being driven by nucleation processes, characterized by the formation of bacterial clusters of critical size that, once established, can only grow and not be dismantled. This work not only provides a compelling hypothesis that biofilm formation is driven by nucleation processes but also introduces a versatile model capable of generating sharp phase transitions, with broad applicability.

Message Passing Graph Neural Networks are known to suffer from two problems that are sometimes believed to be diametrically opposed: over-squashing and over-smoothing. The former results from topological bottlenecks that hamper the information flow from distant nodes and are mitigated by spectral gap maximization, primarily, by means of edge additions. However, such additions often promote over-smoothing that renders nodes of different classes less distinguishable. Inspired by the Braess phenomenon, we argue that deleting edges can address over-squashing and over-smoothing simultaneously. This insight explains how edge deletions can improve generalization, thus connecting spectral gap optimization to a seemingly disconnected objective of reducing computational resources by pruning graphs for lottery tickets. To this end, we propose a computationally effective spectral gap optimization framework to add or delete edges and demonstrate its effectiveness on the long range graph benchmark and on larger heterophilous datasets.

The dynamics of diffusion in complex networks are widely studied to understand how entities, such as information, diseases, or behaviors, spread in an interconnected environment. Complex networks often present community structure, and tools to analyze diffusion processes on networks with communities are needed. In this paper, we develop theoretical tools using multi-type branching processes to model and analyze diffusion processes, following a simple contagion mechanism, across a broad class of networks with community structure. We show how, by using limited information about the network --- the degree distribution within and between communities --- we can calculate standard statistical characteristics of propagation dynamics, such as the extinction probability, hazard function, and cascade size distribution. These properties can be estimated not only for the entire network but also for each community separately. Furthermore, we estimate the probability of spread crossing from one community to another where it is not currently spreading. We demonstrate the accuracy of our framework by applying it to two specific examples: the Stochastic Block Model and a log-normal network with community structure. We show how the initial seeding location affects the observed cascade size distribution on a heavy-tailed network and that our framework accurately captures this effect.

Persistent homology, a technique from computational topology, has recently gained attention in graph machine learning. Previous work bridges the gap between computational topology and graph machine learning, by analyzing persistent homology expressivity for graph learning tasks. However, they do not provide theoretical foundations in the choice of graph filtration methods in terms of their expressivity as in the k-FWL test. On the other hand, it has been recently shown that a proper graph weighting method based on chordless cycles can help identify the latent dimension of networks. In this work, we propose a new class of filtrations in persistent homology based on the density of edge triangles, squares, and pentagons and its application in graph learning. After choosing a filtration, we expand the graph by filling in all (k + 1)-cliques with filtration values and calculating persistent homology up to dimension k. Our persistent homology calculations result in a set of persistence diagrams for each graph, which we compare in a pairwise manner using the bottleneck distance, to decide if two graphs are different. We address the graph isomorphism problem, aiming to distinguish graphs from various datasets like BREC, strongly regular graphs (SSR), minimal Cayley graphs, or cubic graphs. Our proposed filtration outperforms curvature- or Laplacian-based filtration in the BREC dataset for k = 1 and k = 2. Moreover, for SSRs for k = 1 only our filtration can distinguish non-isomorphic graphs. We also study how expressive different filtrations are by comparing them to the k-FWL test. Our results demonstrate the strength of density-based filtrations in distinguishing non-isomorphic graphs, particularly in challenging datasets. Besides graph learning tasks, our method could find applications in chemistry or biology. For example, in molecular graphs. Density-based filtrations could capture structural variations, complementing existing geometric and chemical approaches.

The human microbiota is a complex ecosystem of microorganisms inhabiting the human body and it influences human health and well-being. Recent studies showed its interplay with social behavior, suggesting that part of the microbiota might be socially transmissible [1, 2]. One of the main challenges encountered in these studies is accurately measuring the network of social interactions, typically estimated from known, long-standing relations. While information on these associations is readily available, using such relationships does not allow the study of the microbiota’s similarities among individuals with social contacts reaching beyond their closest social circle. We investigate the association between social interactions and oral microbiota composition in 35 primary school children. This cohort comprises individuals from different families, allowing us to consider interactions beyond the familiar social circle. We characterized the participants’ oral microbiota with saliva sampling during class hours and 16S rRNA gene sequencing. In parallel, we objectively measured a close-range proximity network among children with wearable sensors, developed by the SocioPatterns collaboration [3]. The results summarized in Figure 1 show that prolonged interactions are associated with a significantly higher microbiota similarity. We identify a set of 19 taxa whose distribution across children better correlates with the structure of the proximity network and finally show that the most central children in the proximity network have a higher number of these taxa in their microbiota. In conclusion, our study shows a strong association between oral microbiota and close-range proximity of non-cohabiting children in a primary school setting, complementing the results on cohabiting individuals. This suggests that microbiota might be transmitted in social settings, and it motivates further research on the interplay between the social network structure and the microbiota composition.

The probability of a link between two nodes is commonly said to be $d_i d_j / (2L-1)$, but this is demonstrably false since it is based on an approximation. This probability appears in the formula of Newman’s modularity, which plays a crucial rule in detecting community structures in networks. We derive an exact analytic form for the probability in simple graphs and show that correcting Newman’s modularity formula with our exact probability can lead to different communities being detected.

Social networks, ecological networks, technological networks, financial networks, cultural and historical networks, linguistic networks, ...: Among the many applied domains listed in the call for abstracts at NetSci 2025, legal networks are a notable absence. In this work, we review how network methods have been used in the legal domain, clarify how legal networks differ from social networks and other domain-specific networks, and introduce our conceptual framework for studying networks in law – laying the foundation for our living survey of legal network science. Building on our extensive prior research, we highlight what challenges researchers face in modeling and measuring legal networks, and we discuss how joint efforts to tackle these challenges can inspire methodological innovation in the broader network-science community. In legal systems, individuals and institutions that operate in different branches of the public or the private sector, at different levels of the legal hierarchy (above, on, or below the national level), continuously create, modify, and interpret legal texts in response to system-internal and system-external stimuli – "the law" emerges from these myriad interactions. As such, legal systems are naturally higher-order, multilayer, temporal, adaptive, and intricately coupled with other systems (e.g., social, ecological, and technological systems), combining features from multiple advanced network models. By demonstrating how legal networks are distinct from, yet closely connected to, other topics of interest to network scientists, we hope to draw more researchers into this exciting field – and to help bring together those already active in the area. Thus, we also argue the case for including legal networks in future NetSci calls as a separate category.

Understanding how an epidemic spreads through a network is crucial for devising effective mitigation strategies. While there exists a large body of literature concerning the spread of epidemics on static networks, our understanding of how the dynamics of epidemic spreading interact with the temporal properties of a network is limited. Although, temporal characteristics, such as burstiness or causal temporal motifs, have been shown to fundamentally alter the spread of an epidemic, an accessible method of analysing such phenomena is missing. One promising approach to tackle this problem has been presented through mapping temporal networks to static graphs, which encode the relevant temporal information and unlock static network tools for the analysis of temporal networks. The temporal event graph representation takes this approach by mapping temporal events into nodes and connecting them via links directed forward in time, if they represent temporally adjacent event pairs. The result is a causal directed acyclic graph (DAG), which encodes all time-respecting paths in the network and allows for advantages computing the reachable sets of events. In a temporal network, an event - or node - can be reached from a source through time-respecting paths. The set of reachable nodes, or out-component, forms an upper bound for a spreading process. This representation maps into a reinforcing susceptible-infected-susceptible (rSIS) model evolving on the temporal structure, where each event will re-infect an already infected node, thus restarting its recovery clock. Importantly, this model appears as an upper bound approximation for a conventional SIS process. Our goal in this research is to explore this mapping and approximation to understand how we can use the event graph representation to study epidemic processes without performing costly simulations.

A feature of complexity in connected systems is the emergence of mesoscale patterns in a geometric space, such as groupings in bird flocks. These patterns are formed by groups of points that tend to separate from each other, creating mesoscale structures. When multidimensional data or complex networks are embedded in a geometric space, some mesoscale patterns can appear respectively as clusters or communities, and their geometric separability is a feature according to which the performance of an algorithm for network embedding can be evaluated. Here, we introduce a framework for the definition and measure of the geometric separability (linear and nonlinear) of mesoscale patterns by solving the travelling salesman problem (TSP), and we offer experimental evidence on embedding and visualization of multidimensional data or complex networks, which are generated artificially or are derived from real complex systems. For the first time in literature the TSP’s solution is used to define a criterion of nonlinear separability of points in a geometric space, hence redefining the separability problem in terms of the travelling salesman problem is an innovation which impacts both computer science and complexity theory.

We examine the Random Walkers Induced temporal Graph (RWIG) model, which generates temporal graphs based on the co-location principle of $M$ independent walkers that traverse the underlying Markov graph with different transition probabilities. Given the assumption that each random walker is in the steady state, we determine the steady-state vector $\Tilde{s}$ and the Markov transition matrix $P_i$ of each walker $w_i$ that can reproduce the observed temporal network \(G_0,{...},G_{K{-}1}\) with the lowest mean squared error. We also show how to identify the number of states $N$ and the initial Markov graph of $M$ walkers from the $K$-length contact sequence of the random walkers. Finally, we examine the performance of RWIG for periodic temporal graph sequences.