Generalized k-core pruning process on directed networks

DOI10.1088/1742-5468/AA71E0MaRDI QIDQ3303095zbMATH OpenOpenAlexWikidataFDO

Authors Jinhua Zhao

Publication date 11 August 2020

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.03404

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Deterministic network models in operations research (90B10) Percolation (82B43)

Abstract: The resilience of a complex interconnected system concerns the size of the macroscopic functioning node clusters after external perturbations based on a random or designed scheme. For a representation of the interconnected systems with directional or asymmetrical interactions among constituents, the directed network is a convenient choice. Yet how the interaction directions affect the network resilience still lacks thorough exploration. Here, we study the resilience of directed networks with a generalized $k$-core pruning process as a simple failure procedure based on both the in- and out-degrees of nodes, in which any node with an in-degree $<k_{in}$ or an out-degree $<k_{ou}$ is removed iteratively. With an explicitly analytical framework, we can predict the relative sizes of residual node clusters on uncorrelated directed random graphs. We show that the discontinuous transitions rise for cases with $k_{in}geq2$ or $k_{ou}geq2$, and the unidirectional interactions among nodes drive the networks more vulnerable against perturbations based on in- and out-degrees separately.

Recommendations

• Generalized \(k\)-cores of networks under attack with limited knowledge
• Generalized \(K\)-core percolation in networks with community structure
• Core structure: the coupling failure procedure in multiplex networks
• Generalized \(k\)-core percolation on higher-order dependent networks
• Dynamics ofk-core percolation

Cites work

• scientific article; zbMATH DE number 6118220 (Why is no real title available?)
• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A spin glass approach to the directed feedback vertex set problem
• Clustering and community detection in directed networks: a survey
• Collective dynamics of `small-world' networks
• Complex networks: structure and dynamics
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Depth-First Search and Linear Graph Algorithms
• Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks
• Emergence of Scaling in Random Networks
• Factor graphs and the sum-product algorithm
• Information, Physics, and Computation
• On the origins of hierarchy in complex networks
• Statistical mechanics of complex networks
• Statistical theory of superlattices
• Sudden emergence of a giant \(k\)-core in a random graph
• The Structure and Function of Complex Networks

Cited in

(1)

• Hierarchical cycle-tree packing model for optimal \(K\)-core attack

This page was built for publication: Generalized \(k\)-core pruning process on directed networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3303095)