Research On Dense Subgraph Discovery Algorithm Based On K-clique Core

With the continuous development of large-scale networks,related applications continue to emerge,at the same time,graph data also grows fastly and is frequently updated,which places higher,requirements on large-scale network processing.Dense subgraph discovery is a basic graph mining problem that has become a primitive in a wide range of data analysis tasks.As a hot issue in network processing,the quality and efficiency of dense subgraph discovery directly affect complex network analysis.In this paper,the relevant theories of dense subgraphs and k-core are studied.Based on the characteristics of dense subgraphs on static and dynamic graphs,a k-clique core-based dense subgraph discovery method is proposed,the main research contents include:1.A new dense subgraph model are proposed.k-clique core model can not only capture the number of clique cores of nodes,but also ensure the tightness of the subgraph.The number of clique cores obtained based on the k-clique core decomposition algorithm effectively obtains the tight upper and lower limits of the hypothetical value of the density,thereby reducing the number of binary searches.2.An accurate and approximate algorithm for static dense subgraph discovery based on k-clique cores to achieve fast dense subgraph discovery on large-scale graphs are proposed.The precise algorithm uses k-clique cores,proposes three optimization rules to improve efficiency,and uses the core decomposition algorithm to build a stream network on a specific core.The maximum flow problem is solved by using the binary search method to find the dense subgraph.In order to further improve the efficiency,instead of using the core decomposition algorithm,a new method is proposed to directly calculate the largest k-clique core,and prove that the largest k-clique core is an approximate solution to the problem of dense subgraph discovery.3.Dense subgraph discovery algorithm on the dynamic graph are proposed.During the processing of dense subgraph discovery,when the graph data is frequently updated,only the number of clique degrees of some vertices changes.Therefore,a data structure for storing high clique-degree vertices is proposed.The sliding time window is used to process dynamic graphs,design algorithms for adding and deleting nodes and edges to achieve dense subgraph discovery.4.A large number of experiments have been performed on the real dataset,which verifies the effectiveness of the k-clique core-based dense subgraph discovery method and the dynamic dense subgraph discovery method.Experiments show that this method can ensure better quality of subgraph in a faster running time,and it has good scalability on static and dynamic graphs in practical applications.