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.展开更多
针对城市重要公交线路识别与优化问题,以西安市公交系统作为研究对象,利用高阶网络模型甄别和优化西安市公交系统的重要公交线路.首先,考虑到城市公交系统具有典型的路径依赖特征,基于高阶网络模型方法构建高阶公交网络.其次,基于公交...针对城市重要公交线路识别与优化问题,以西安市公交系统作为研究对象,利用高阶网络模型甄别和优化西安市公交系统的重要公交线路.首先,考虑到城市公交系统具有典型的路径依赖特征,基于高阶网络模型方法构建高阶公交网络.其次,基于公交站点道路等级、站点与轨道交通接驳情况、站点服务范围内兴趣点(Point of Interest,POI)、站点所在区域的人口密度4项位置属性指标,提出改进的加权k核分解算法,将高阶公交网络分为核心层、桥层和外围层.最后,以西安市为例进行实证分析,以各层中连边承担的平均线路数为依据甄别重要公交线路,并根据路段在重要连边中出现的次数识别出最重要的公交路段,针对存在的问题提出优化建议.研究结果表明:西安市公交系统中存在234条重要的公交路段以及经过6条最重要路段的55条公交线路;西安市存在城市新区及近郊区域与中心城区连接不畅的问题,桥层中有524个公交站点与核心层中的任意一个站点都没有直达的公交线路;通过对13条非直达线路进行优化,站点直达率提高4.72%,增加了13条线路中247个站点与核心层站点的直达路线选择,改善了城市居民的出行便利性.展开更多
基金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.
文摘针对城市重要公交线路识别与优化问题,以西安市公交系统作为研究对象,利用高阶网络模型甄别和优化西安市公交系统的重要公交线路.首先,考虑到城市公交系统具有典型的路径依赖特征,基于高阶网络模型方法构建高阶公交网络.其次,基于公交站点道路等级、站点与轨道交通接驳情况、站点服务范围内兴趣点(Point of Interest,POI)、站点所在区域的人口密度4项位置属性指标,提出改进的加权k核分解算法,将高阶公交网络分为核心层、桥层和外围层.最后,以西安市为例进行实证分析,以各层中连边承担的平均线路数为依据甄别重要公交线路,并根据路段在重要连边中出现的次数识别出最重要的公交路段,针对存在的问题提出优化建议.研究结果表明:西安市公交系统中存在234条重要的公交路段以及经过6条最重要路段的55条公交线路;西安市存在城市新区及近郊区域与中心城区连接不畅的问题,桥层中有524个公交站点与核心层中的任意一个站点都没有直达的公交线路;通过对13条非直达线路进行优化,站点直达率提高4.72%,增加了13条线路中247个站点与核心层站点的直达路线选择,改善了城市居民的出行便利性.
