Research On Dense Subgraph Maximization Algorithms Based On K-core And K-truss

Cohesive substructure identification is a fundamental task of graph mining.Dense subgraphs can be used to analyze the connectivity,centrality and robustness of graphs.Among the numerous dense subgraph models,the k-core and k-truss models have become the focus of research,thanks to the fact that they can be obtained in polynomial time.Also,a graph can be decomposed by these two subgraphs into hierarchical structures.Recently,a useful problem of dense subgraph maximization is particularly useful on various real-life applications,such as social group engagement,identifying missing defence nodes and links in military networks,and improving stability for resource exchanging in P2P networks.The k-core maximization problem mainly includes inserting some new edges into the graph to enlarge the k-core subgraph.However,existing heuristic approaches suffer from the inefficiency limitation,which is hard to be scalable on large graphs.The problem of k-truss maximization has not been studied yet,but it is very valuable in many real-world applications.This paper focuses on these two dense graph models of k-core and k-truss.First,this paper aims at addressing the problem of low efficiency of the existing k-core maximization algorithm.We propose a novel algorithm FactCM+based on graph partition and several fast search strategies.The core idea is applying graph partition to divide important vertices into different components.Then,FactCM+considers each component independently to convert different layered vertices into k-core,in two manners of completely and partially,leveraging dynamic programming combinations of different components.We theoretically analyze the time complexity of FactCM+in O(n(m+b))which is much faster than the state-of-the-art algorithm EKC’s O(bmn2),where n,m,b are the number of vertices and edges in G,and the number of edge insertions,respectively.Experimental results on eleven datasets demonstrate that our algorithm runs 74,000x faster than EKC on large graphs,meanwhile achieving better answers.Furthermore,this paper proposes and studies the k-truss maximization problem for the first time.Since the k-truss maximization problem has not been studied yet,we first demonstrate that this new problem has rich application scenarios from the two practical applications,i.e.,the fight network connectivity improvement and social group engagement.Then,we theoretically prove the NP-hardness of the k-truss maximization problem.To efficiently tackle it,we analyze the non-submodular property of the k-truss newcomers function and develop non-conventional heuristic strategies.We first identify high-quality candidate edges with regard to subgraphs and propose a greedy algorithm using per-edge insertion.Besides improving the efficiency by pruning disqualified candidate edges,we also develop a component-based dynamic programming algorithm for enlarging k-truss mostly,which makes a balance of budget assignment and inserts multiple edges simultaneously into all components.Extensive experiments on nine real-world graphs demonstrate the efficiency and effectiveness of the proposed new methods.Through the above two studies,this paper improves the solution efficiency of the current subgraph maximization problem,and expands its application scope,which may provides a new way to design and apply the subgraph maximization algorithm.