Research On Network Stability Algorithm Based On Cohensive Subgraph Model

With the rapid development of the mobile Internet,the ever-increasing demand for massive computing and real-time feedback requirements have also brought us huge challenges.The stability of a network has been widely studied as an important indicator of network status,e.g.,reliability and activity.By studying the stability of a network,we can manage to increase the stability of the network to make the network more robust.And We can also try to find the weak links in the network to resist the risk of external attacks.A popular model for measuring the(structural)stability of a network is k-core,the maximal induced subgraph in which every vertex has at least k neighbors in the subgraph.As the size of k-core well estimates the stability of a network,the Edge kCore problem is studied to enhance network stability:given a graph G,an integer k and a budget b,add b edges to non-adj acent vertex pairs in G such that the number of vertices in the k-core is maximized.The Edge k-Core problem is introduced by Chitnis and the only existing solution is proposed for graphs with bounded tree-width.However,this assumption usually does not hold in real-life graphs,and their techniques cannot be extended to handle general graphs.In this paper,we systematically studies the Edge k-Core problem,and propose a concise reduction to prove that the problem is NP-hard and APX-hard.Due to the hardness of the problem,we resort to a greedy strategy and propose the EKC algorithm with effective pruning techniques.EKC can produce an acceptable result considering non-submodular property and the significantly better efficiency of EKC.However,EKC is still not efficient enough on large graphs.We further analyze the performance bottleneck of EKC,and propose a novel vertex-centric heuristic algorithm(named VCEK),with a well-designed scoring function to guide the search order.Effective optimization techniques are proposed to prune unpromising candidates and reuse the intermediate results.The runtime of our proposed VCEK is even faster than EKC by 1-3 orders of magnitude.The experiments are conducted on 9 real networks to demonstrate the effectiveness of our model and the efficiency of the proposed methods.