Beyond clustering: mean-field dynamics on networks with arbitrary subgraph composition

Effects of clustering heterogeneity on the spectral density of sparse networks

We derive exact equations for the spectral density of sparse networks with an arbitrary distribution of the number of single edges and triangles per node. These equations enable a systematic investigation of the effects of clustering on the spectral properties of the network adjacency matrix. In the case of heterogeneous networks, we demonstrate that the spectral density becomes more symmetric as the fluctuations in the triangle-degree sequence increase. This phenomenon is explained by the small clustering coefficient of networks with a large variance of the triangle-degree distribution. In the homogeneous case of regular clustered networks, we find that both perturbative and nonperturbative approximations fail to predict the spectral density in the high-connectivity limit. This suggests that traditional large-degree approximations may be ineffective in studying the spectral properties of networks with more complex motifs. Our theoretical results are fully confirmed by numerical diagonalizations of finite adjacency matrices.

Effectiveness of contact tracing on networks with cliques

Contact tracing, the practice of isolating individuals who have been in contact with infected individuals, is an effective and practical way of containing disease spread. Here we show that this strategy is particularly effective in the presence of social groups: Once the disease enters a group, contact tracing not only cuts direct infection paths but can also pre-emptively quarantine group members such that it will cut indirect spreading routes. We show these results by using a deliberately stylized model that allows us to isolate the effect of contact tracing within the clique structure of the network where the contagion is spreading. This will enable us to derive mean-field approximations and epidemic thresholds to demonstrate the efficiency of contact tracing in social networks with small groups. This analysis shows that contact tracing in networks with groups is more efficient the larger the groups are. We show how these results can be understood by approximating the combination of disease spreading and contact tracing with a complex contagion process where every failed infection attempt will lead to a lower infection probability in the following attempts. Our results illustrate how contact tracing in real-world settings can be more efficient than predicted by models that treat the system as fully mixed or the network structure as locally treelike.

Motif-based mean-field approximation of interacting particles on clustered networks

Interacting particles on graphs are routinely used to study magnetic behavior in physics, disease spread in epidemiology, and opinion dynamics in social sciences. The literature on mean-field approximations of such systems for large graphs typically remains limited to specific dynamics, or assumes cluster-free graphs for which standard approximations based on degrees and pairs are often reasonably accurate. Here, we propose a motif-based mean-field approximation that considers higher-order subgraph structures in large clustered graphs. Numerically, our equations agree with stochastic simulations where existing methods fail.

Epidemic threshold in pairwise models for clustered networks: closures and fast correlations

The epidemic threshold is probably the most studied quantity in the modelling of epidemics on networks. For a large class of networks and dynamics, it is well studied and understood. However, it is less so for clustered networks where theoretical results are mostly limited to idealised networks. In this paper we focus on a class of models known as pairwise models where, to our knowledge, no analytical result for the epidemic threshold exists. We show that by exploiting the presence of fast variables and using some standard techniques from perturbation theory we are able to obtain the epidemic threshold analytically. We validate this new threshold by comparing it to the threshold based on the numerical solution of the full system. The agreement is found to be excellent over a wide range of values of the clustering coefficient, transmission rate and average degree of the network. Interestingly, we find that the analytical form of the threshold depends on the choice of closure, highlighting the importance of model selection when dealing with real-world epidemics. Nevertheless, we expect that our method will extend to other systems in which fast variables are present.

Variational principle for scale-free network motifs

For scale-free networks with degrees following a power law with an exponent τ ∈ (2, 3), the structures of motifs (small subgraphs) are not yet well understood. We introduce a method designed to identify the dominant structure of any given motif as the solution of an optimization problem. The unique optimizer describes the degrees of the vertices that together span the most likely motif, resulting in explicit asymptotic formulas for the motif count and its fluctuations. We then classify all motifs into two categories: motifs with small and large fluctuations.