Belief propagation for networks with loops

Tensor Network Message Passing

When studying interacting systems, computing their statistical properties is a fundamental problem in various fields such as physics, applied mathematics, and machine learning. However, this task can be quite challenging due to the exponential growth of the state space as the system size increases. Many standard methods have significant weaknesses. For instance, message-passing algorithms can be inaccurate and even fail to converge due to short loops, while tensor network methods can have exponential computational complexity in large graphs due to long loops. In this Letter, we propose a new method called "tensor network message passing." This approach allows us to compute local observables like marginal probabilities and correlations by combining the strengths of tensor networks in contracting small subgraphs with many short loops and the strengths of message-passing methods in globally sparse graphs, thus addressing the crucial weaknesses of both approaches. Our algorithm is exact for systems that are globally treelike and locally dense-connected when the dense local graphs have a limited tree width. We have conducted numerical experiments on synthetic and real-world graphs to compute magnetizations of Ising models and spin glasses, and have demonstrated the superiority of our approach over standard belief propagation and the recently proposed loopy message-passing algorithm. In addition, we discuss the potential applications of our method in inference problems in networks, combinatorial optimization problems, and decoding problems in quantum error correction.

Cavity approach for the approximation of spectral density of graphs with heterogeneous structures

Graphs have become widely used to represent and study social, biological, and technological systems. Statistical methods to analyze empirical graphs were proposed based on the graph's spectral density. However, their running time is cubic in the number of vertices, precluding direct application to large instances. Thus, efficient algorithms to calculate the spectral density become necessary. For sparse graphs, the cavity method can efficiently approximate the spectral density of locally treelike undirected and directed graphs. However, it does not apply to most empirical graphs because they have heterogeneous structures. Thus, we propose methods for undirected and directed graphs with heterogeneous structures using a new vertex's neighborhood definition and the cavity approach. Our methods' time and space complexities are O(|E|h_{max}^{3}t) and O(|E|h_{max}^{2}t), respectively, where |E| is the number of edges, h_{max} is the size of the largest local neighborhood of a vertex, and t is the number of iterations required for convergence. We demonstrate the practical efficacy by estimating the spectral density of simulated and real-world undirected and directed graphs.

Nature of hypergraph k-core percolation problems

Hypergraphs are higher-order networks that capture the interactions between two or more nodes. Hypergraphs can always be represented by factor graphs, i.e., bipartite networks between nodes and factor nodes (representing groups of nodes). Despite this universal representation, here we reveal that k-core percolation on hypergraphs can be significantly distinct from k-core percolation on factor graphs. We formulate the theory of hypergraph k-core percolation based on the assumption that a hyperedge can be intact only if all its nodes are intact. This scenario applies, for instance, to supply chains where the production of a product requires all raw materials and all processing steps; in biology it applies to protein-interaction networks where protein complexes can function only if all the proteins are present; and it applies as well to chemical reaction networks where a chemical reaction can take place only when all the reactants are present. Formulating a message-passing theory for hypergraph k-core percolation, and combining it with the theory of critical phenomena on networks, we demonstrate sharp differences with previously studied factor graph k-core percolation processes where it is allowed for hyperedges to have one or more damaged nodes and still be intact. To solve the dichotomy between k-core percolation on hypegraphs and on factor graphs, we define a set of pruning processes that act either exclusively on nodes or exclusively on hyperedges and depend on their second-neighborhood connectivity. We show that the resulting second-neighbor k-core percolation problems are significantly distinct from each other. Moreover we reveal that although these processes remain distinct from factor graphs k-core processes, when the pruning process acts exclusively on hyperedges the phase diagram is reduced to the one of factor graph k-cores.

Heterogeneous message passing for heterogeneous networks

Message passing (MP) is a computational technique used to find approximate solutions to a variety of problems defined on networks. MP approximations are generally accurate in locally treelike networks but require corrections to maintain their accuracy level in networks rich with short cycles. However, MP may already be computationally challenging on very large networks and additional costs incurred by correcting for cycles could be prohibitive. We show how the issue can be addressed. By allowing each node in the network to have its own level of approximation, one can focus on improving the accuracy of MP approaches in a targeted manner. We perform a systematic analysis of 109 real-world networks and show that our node-based MP approximation is able to increase both the accuracy and speed of traditional MP approaches. We find that, compared to conventional MP, a heterogeneous approach based on a simple heuristic is more accurate in 81% of tested networks, faster in 64% of cases, and both more accurate and faster in 49% of cases.

The dynamic resilience of urban labour networks

Both cities and markets are well understood as complex systems which are amenable to analysis using physically inspired methods. Cities have shown fascinating universality with size, while labour markets modelled as networks have considerable explanatory power. Labour markets are a particularly attractive domain of study in this context due to societal importance, the influx of high-resolution data as well as exogenous influence of automation. While much previous work has studied the economic characteristics of cities as a function of size and examined the exposure of urban economies to automation, this has often been from a static perspective. In this work, we examine the diffusive properties of labour markets and examine their variance across cities. More specifically, we identify the occupations which are most important in promoting the diffusion of beneficial or deleterious properties. To this end, we propose a new measure of node centrality empSI. We find that these properties of influence vary considerably with city size.

Belief propagation on networks with cliques and chordless cycles

It is well known that tree-based theories can describe the properties of undirected clustered networks with extremely accurate results [S. Melnik et al., Phys. Rev. E 83, 036112 (2011)10.1103/PhysRevE.83.036112]. It is reasonable to suggest that a motif-based theory would be superior to a tree one, since additional neighbor correlations are encapsulated in the motif structure. In this paper, we examine bond percolation on random and real world networks using belief propagation in conjunction with edge-disjoint motif covers. We derive exact message passing expressions for cliques and chordless cycles of finite size. Our theoretical model gives good agreement with Monte Carlo simulation and offers a simple, yet substantial improvement on traditional message passing, showing that this approach is suitable to study the properties of random and empirical networks.

Message passing methods on complex networks

Networks and network computations have become a primary mathematical tool for analyzing the structure of many kinds of complex systems, ranging from the Internet and transportation networks to biochemical interactions and social networks. A common task in network analysis is the calculation of quantities that reside on the nodes of a network, such as centrality measures, probabilities or model states. In this perspective article we discuss message passing methods, a family of techniques for performing such calculations, based on the propagation of information between the nodes of a network. We introduce the message passing approach with a series of examples, give some illustrative applications and results and discuss the deep connections between message passing and phase transitions in networks. We also point out some limitations of the message passing approach and describe some recently introduced methods that address these limitations.

Efficiency of Algorithms for Computing Influence and Information Spreading on Social Networks

Modelling interactions on complex networks needs efficient algorithms for describing processes on a detailed level in the network structure. This kind of modelling enables more realistic applications of spreading processes, network metrics, and analyses of communities. However, different real-world processes may impose requirements for implementations and their efficiency. We discuss different transmission and spreading processes and their interrelations. Two pseudo-algorithms are presented, one for the complex contagion spreading mechanism using non-self-avoiding paths in the modelling, and one for simple contagion processes using self-avoiding paths in the modelling. The first algorithm is an efficient implementation that can be used for describing social interaction in a social network structure. The second algorithm is a less efficient implementation for describing specific forms of information transmission and epidemic spreading.

Hypergraph assortativity: A dynamical systems perspective

The largest eigenvalue of the matrix describing a network's contact structure is often important in predicting the behavior of dynamical processes. We extend this notion to hypergraphs and motivate the importance of an analogous eigenvalue, the expansion eigenvalue, for hypergraph dynamical processes. Using a mean-field approach, we derive an approximation to the expansion eigenvalue in terms of the degree sequence for uncorrelated hypergraphs. We introduce a generative model for hypergraphs that includes degree assortativity, and use a perturbation approach to derive an approximation to the expansion eigenvalue for assortative hypergraphs. We define the dynamical assortativity, a dynamically sensible definition of assortativity for uniform hypergraphs, and describe how reducing the dynamical assortativity of hypergraphs through preferential rewiring can extinguish epidemics. We validate our results with both synthetic and empirical datasets.

Long-loop feedback vertex set and dismantling on bipartite factor graphs

Network dismantling aims at breaking a network into disconnected components and attacking vertices that intersect with many loops has proven to be a most efficient strategy. Yet existing loop-focusing methods do not distinguish the short loops within densely connected local clusters (e.g., cliques) from the long loops connecting different clusters, leading to lowered performance of these algorithms. Here we propose a new solution framework for network dismantling based on a two-scale bipartite factor-graph representation, in which long loops are maintained while local dense clusters are simplistically represented as individual factor nodes. A mean-field spin-glass theory is developed for the corresponding long-loop feedback vertex set problem. The framework allows for the advancement of various existing dismantling algorithms; we developed the new version of two benchmark algorithms BPD (which uses the message-passing equations of the spin-glass theory as the solver) and CoreHD (which is fastest among well-performing algorithms). New solvers outperform current state-of-the-art algorithms by a considerable margin on networks of various sorts. Further improvement in dismantling performance is achievable by opting flexibly the choice of local clusters.