Epidemic processes are common out-of-equilibrium phenomena of broad interdisciplinary interest. Recently, dynamic message-passing (DMP) has been proposed as an efficient algorithm for simulating epidemic models on networks, and in particular for estimating the probability that a given node will become infectious at a particular time. To date, DMP has been applied exclusively to models with one-way state changes, as opposed to models like SIS and SIRS where nodes can return to previously inhabited states. Because many real-world epidemics can exhibit such recurrent dynamics, we propose a DMP algorithm for complex, recurrent epidemic models on networks. Our approach takes correlations between neighboring nodes into account while preventing causal signals from backtracking to their immediate source, and thus avoids echo chamber effects'' where a pair of adjacent nodes each amplify the probability that the other is infectious. We demonstrate that this approach well approximates results obtained from Monte Carlo simulation and that its accuracy is often superior to the pair approximation (which also takes second-order correlations into account). Moreover, our approach is more computationally efficient than the pair approximation, especially for complex epidemic models: the number of variables in our DMP approach grows as @math where @math is the number of edges and @math is the number of states, as opposed to @math for the pair approximation. We suspect that the resulting reduction in computational effort, as well as the conceptual simplicity of DMP, will make it a useful tool in epidemic modeling, especially for high-dimensional inference tasks.
Systems of differential equations for , such as , do not appear to have a closed analytic form due to their nonlinearities. On the other hand, we can compute quantities such as epidemic thresholds by linearizing around a stationary point, such as @math where the initial outbreak is small. Given a perturbation @math , the linear stability of the system, i.e., whether or not @math diverges in time, is governed by the eigenvalues of the Jacobian matrix @math of the right hand side of at the stationary point @math . The Jacobian for at @math is (j i),(k j') = - kj ij' + (1- j ^*) (j i),(k j') , . where (j i),(k j') = jj' (1- ik ) , . This definition of @math is another way of saying that the edge @math influences edges @math for @math , but does not backtrack to @math . This corresponds to our assumption that infections, for instance, do not bounce from @math to @math and back again and create an echo chamber effect. For this reason, @math is also known in the literature as the non-backtracking matrix @cite_24 or the Hashimoto matrix @cite_16 .
@cite_24 @cite_16
2024514015 1523808012
Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here, we present a class of spectral algorithms based on a nonbacktracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all of the way down to the theoretical limit. We also show the spectrum of the nonbacktracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering. Publisher Summary This chapter focuses on zeta functions of finite graphs and representations of p-adic groups. It discusses two different subjects: first is a combinatorial problem in algebraic graph theory, and the other is arithmetic of discrete subgroups of p-adic groups and their representations. The chapter presents the notation and basic definitions in graph theory. It also presents a generalization of the definition of zeta function. Spectrum of a finite multigraph is analyzed in the chapter. Moreover, the chapter also describes harmonic functions and the Hodge decomposition. The chapter also presents the computation of zeta functions Zx(u) for some well known families of graphs. These computations give many examples of graphs that are not Ramanujan graphs.