Ecosystems generally have the self-adapting ability to resist various external pressures or disturbances,which is always called resilience.However,once the external disturbances exceed the tipping points of the system...Ecosystems generally have the self-adapting ability to resist various external pressures or disturbances,which is always called resilience.However,once the external disturbances exceed the tipping points of the system resilience,the consequences would be catastrophic,and eventually lead the ecosystem to complete collapse.We capture the collapse process of ecosystems represented by plant-pollinator networks with the k-core nested structural method,and find that a sufficiently weak interaction strength or a sufficiently large competition weight can cause the structure of the ecosystem to collapse from its smallest k-core towards its largest k-core.Then we give the tipping points of structure and dynamic collapse of the entire system from the one-dimensional dynamic function of the ecosystem.Our work provides an intuitive and precise description of the dynamic process of ecosystem collapse under multiple interactions,and provides theoretical insights into further avoiding the occurrence of ecosystem collapse.展开更多
Kinetically constrained spin systems are toy models of supercooled liquids and amorphous solids. In this perspective,we revisit the prototypical Fredrickson–Andersen(FA) kinetically constrained model from the viewpoi...Kinetically constrained spin systems are toy models of supercooled liquids and amorphous solids. In this perspective,we revisit the prototypical Fredrickson–Andersen(FA) kinetically constrained model from the viewpoint of K-core combinatorial optimization. Each kinetic cluster of the FA system, containing all the mutually visitable microscopic occupation configurations, is exactly the solution space of a specific instance of the K-core attack problem. The whole set of different jammed occupation patterns of the FA system is the configuration space of an equilibrium K-core problem. Based on recent theoretical results achieved on the K-core attack and equilibrium K-core problems, we discuss the thermodynamic spin glass phase transitions and the maximum occupation density of the fully unfrozen FA kinetic cluster, and the minimum occupation density and extreme vulnerability of the partially frozen(jammed) kinetic clusters. The equivalence between K-core attack and the fully unfrozen FA kinetic cluster also implies a new way of sampling K-core attack solutions.展开更多
In this paper,we investigate the problem of a size-constrained k-core group query (SCCGQ)in social networks, taking both user closeness and network topology into consideration.More specifically,SCCGQ intends to find a...In this paper,we investigate the problem of a size-constrained k-core group query (SCCGQ)in social networks, taking both user closeness and network topology into consideration.More specifically,SCCGQ intends to find a group of h users that has the highest social closeness while being a k-core.SCCGQ can be widely applied to event planning,task assignment,social analysis,and many other fields.In contrast to existing work on the k-core detection problem,which aims to find a k-core in a social network,SCCGQ not only focuses on k-core detection but also takes size constraints into consideration.Although the conventional k-core detection problem can be solved in linear time,SCCGQ has a higher complexity.To solve the problem of SCCGQ,we propose a Blast Scatter (BS)algorithm,which appoints the query node as the center to begin outward expansions via breadth search.In each outward expansion,BS finds a new center through a greedy strategy and then selects multiple neighbors of the center.To speed up the BS algorithm,we propose an advanced search algorithm,called Bounded Extension (BE).Specifically,BE combines an effective social distance pruning strategy and a tight upper bound of social closeness to prune the search space considerably.In addition,we propose an offiine social-aware index to accelerate the query processing.Finally,our experimental results demonstrate the efficiency and effectiveness of our proposed algorithms on large real-world social networks.展开更多
The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuou...The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack(CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erd?s-Rényi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems.展开更多
基金Project supported by the National Natural Science Foundation of China(Grant Nos.72071153 and 72231008)the Natural Science Foundation of Shaanxi Province(Grant No.2020JM-486)the Fund of the Key Laboratory of Equipment Integrated Support Technology(Grant No.6142003190102)。
文摘Ecosystems generally have the self-adapting ability to resist various external pressures or disturbances,which is always called resilience.However,once the external disturbances exceed the tipping points of the system resilience,the consequences would be catastrophic,and eventually lead the ecosystem to complete collapse.We capture the collapse process of ecosystems represented by plant-pollinator networks with the k-core nested structural method,and find that a sufficiently weak interaction strength or a sufficiently large competition weight can cause the structure of the ecosystem to collapse from its smallest k-core towards its largest k-core.Then we give the tipping points of structure and dynamic collapse of the entire system from the one-dimensional dynamic function of the ecosystem.Our work provides an intuitive and precise description of the dynamic process of ecosystem collapse under multiple interactions,and provides theoretical insights into further avoiding the occurrence of ecosystem collapse.
基金Project supported by the National Natural Science Foundation of China (Grant Nos. 12247104 and 12047503)。
文摘Kinetically constrained spin systems are toy models of supercooled liquids and amorphous solids. In this perspective,we revisit the prototypical Fredrickson–Andersen(FA) kinetically constrained model from the viewpoint of K-core combinatorial optimization. Each kinetic cluster of the FA system, containing all the mutually visitable microscopic occupation configurations, is exactly the solution space of a specific instance of the K-core attack problem. The whole set of different jammed occupation patterns of the FA system is the configuration space of an equilibrium K-core problem. Based on recent theoretical results achieved on the K-core attack and equilibrium K-core problems, we discuss the thermodynamic spin glass phase transitions and the maximum occupation density of the fully unfrozen FA kinetic cluster, and the minimum occupation density and extreme vulnerability of the partially frozen(jammed) kinetic clusters. The equivalence between K-core attack and the fully unfrozen FA kinetic cluster also implies a new way of sampling K-core attack solutions.
基金the National Research Foundation,Prime Ministers Office,Singapore,under its International Research Centres in Singapore Funding Initiative and Pinnacle Lab for Analytics at Singapore Management University,the National Natural Science Foundation of China under Grant Nos.61572119,61622202,61732003,61729201,61702086,and U1401256the Fundamental Research Funds for the Central Universities of China under Grant No.N150402005.
文摘In this paper,we investigate the problem of a size-constrained k-core group query (SCCGQ)in social networks, taking both user closeness and network topology into consideration.More specifically,SCCGQ intends to find a group of h users that has the highest social closeness while being a k-core.SCCGQ can be widely applied to event planning,task assignment,social analysis,and many other fields.In contrast to existing work on the k-core detection problem,which aims to find a k-core in a social network,SCCGQ not only focuses on k-core detection but also takes size constraints into consideration.Although the conventional k-core detection problem can be solved in linear time,SCCGQ has a higher complexity.To solve the problem of SCCGQ,we propose a Blast Scatter (BS)algorithm,which appoints the query node as the center to begin outward expansions via breadth search.In each outward expansion,BS finds a new center through a greedy strategy and then selects multiple neighbors of the center.To speed up the BS algorithm,we propose an advanced search algorithm,called Bounded Extension (BE).Specifically,BE combines an effective social distance pruning strategy and a tight upper bound of social closeness to prune the search space considerably.In addition,we propose an offiine social-aware index to accelerate the query processing.Finally,our experimental results demonstrate the efficiency and effectiveness of our proposed algorithms on large real-world social networks.
基金supported by the National Natural Science Foundation of China(Grant Nos.11975295,and 12047503)and the Chinese Academy of Sciences(Grant Nos.QYZDJ-SSW-SYS018,and XDPD15)。
文摘The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack(CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erd?s-Rényi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems.
