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.展开更多
社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文...社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文提出了规模受限的影响力社区搜索(Size-Constrained Influential Community search,SCIC),设计了基于深度优先搜索的基础算法,在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法,用于减少冗余计算,加速枚举过程.在10个不同规模的数据集上进行实验,实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法,同时,本文提出的优化算法能够显著提升搜索效率,将响应时间缩减至基础算法的1%.展开更多
基金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.
文摘社区搜索用于返回包含给定查询结点且符合查询条件的密集连通子图.目前,大部分已有社区搜索方法主要关注社区的结构,没有考虑到特定应用中资源受限的情况,且忽略了社区的属性特征,无法满足用户对社区搜索的个性化要求.针对该问题,本文提出了规模受限的影响力社区搜索(Size-Constrained Influential Community search,SCIC),设计了基于深度优先搜索的基础算法,在此基础上进一步提出了基于结点预处理、剪枝规则和贪心策略的优化算法,用于减少冗余计算,加速枚举过程.在10个不同规模的数据集上进行实验,实验结果表明基础算法在搜索获得的社区规模和影响力上均优于已有算法,同时,本文提出的优化算法能够显著提升搜索效率,将响应时间缩减至基础算法的1%.
