The Stability Of K-Truss Community

The ever-grow prominence of information networks has brought the study of graph data mining into the spotlight of many researchers.Identifying the critical connections w.r.t.community stability plays a significant role in this field.The breaking of specific connections in the community could cause cascade effect upon the whole community,i.e.,the breaking of connection between core members of the community could potentially cause the entire community to collapse.To better understand and maintain the social networks,it is crucial to identify those edges that corresponds to the vital network connections.The enhancement or editing of those edges could help the social network owners to enhance/reduce the cohesiveness of certain confidential/undesirable community.For social network users,it can be also utilized to help protect users’ privacy.Among the existing community models,k-truss model has drawn more attentions in recent years.We call a subgraph a k-truss if and only if all edges have been contained in at least k-2 triangles.The k-truss has been widely used as a notion of community.This article focuses on the k-truss breaking problem that aims to find a minimal set of edges that upon the removal of those edges,the k-truss no longer exist.In this paper,we propose the scoring function EBD that can measure edges’ potential contribution to the breaking of the k-truss.We firstly mark edges contained in more triangles as candidates and the rest as easy-breaking edge,and then assess candidates’ potential based on the number of easy-breaking edges that are triangle connected to them.Based on this idea,two heuristic algorithms for k-truss breaking problem have been described.It provides us a guidance to choose the edges to delete while enables us to evaluate how close a subgraph is to broken.Based on EBD,we propose EBDH algorithm that could find a high-quality solution to the k-truss breaking with significant less time cost than previous algorithm,and TDA algorithm that refines the solution as time allowed and eventually find the exact solution.TDA is also several orders of magnitudes faster than previous exact algorithm.