Minimum Long-Loop Feedback Vertex Set and Network Dismantling

Abstract

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. But the existing loop-focusing methods treat the short loops within densely connected local clusters (e.g., cliques) as equally important as the long loops connecting different clusters. Here we propose for highly clustered artificial and real-world networks a bipartite factor-graph formulation that retains all the long loops while simplifies the local dense clusters as individual factor nodes. We develop a mean-field theory for the associated long-loop feedback vertex set problem and apply its message-passing equation as a solver for network dismantling. The proposed factor-graph loop algorithm outperforms the current state-of-the-art graph loop algorithms by a considerable margin on various real networks. Further improvement in dismantling performance is achievable by optimizing the choice of the local dense clusters.

References in corpus (31)

• Community structure in social and biological networks
• Uncovering the overlapping community structure of complex networks in nature and society
• The Dynamics of Viral Marketing
• Community detection in networks: A user guide
• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• Control Principles of Complex Networks
• Random graphs with clustering
• Properties of highly clustered networks
• Graph Evolution: Densification and Shrinking Diameters
• Network dismantling
• Generalized Network Dismantling
• Robust network community detection using balanced propagation
• Identifying optimal targets of network attack by belief propagation
• Fast and simple decycling and dismantling of networks
• Immunization and targeted destruction of networks using explosive percolation
• Message passing on networks with loops
• Articulation Points in Complex Networks
• Bond percolation on a class of clustered random networks
• Spin glass approach to the feedback vertex set problem
• Optimal Deployment of Resources for Maximizing Impact in Spreading Processes
• Optimizing spread dynamics on graphs by message passing
• GEMSEC: Graph Embedding with Self Clustering
• Belief-propagation algorithm and the Ising model on networks with arbitrary distributions of motifs
• Belief propagation for networks with loops
• Spectra of networks containing short loops
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Statistical Mechanics of the Minimum Dominating Set Problem
• A loop enhancement strategy for network robustness
• Spectral estimation of the percolation transition in clustered networks
• Spin-glass model for the C-dismantling problem

Cited by in corpus (4)

• Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm
• Belief propagation on networks with cliques and chordless cycles
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Superexponential growth of epidemics in networks with cliques