Design And Implementation Of The Densest Subgraph Algorithm For Vertex-weighted Graphs

As a data structure which can effectively describe the complex relationships among various entities in the real world,graph is widely used in social relations network,co-author network,communication network,biological information network and other practical fields.With the rapid development of these new large-scale networks,the related applications are constantly emerging and enriched,and the data of the map are increasing rapidly and updated frequently,making the demand for processing of large scale graphs more and more urgent.The densest subgraphs query is a hot research topic in graph data processing.It plays a very important role in complex network analysis.Given a graph,the problem of the dense subgraph is designed to find a subgraph with at least some density.However,most existing dense subgraph algorithms do not take the influence of weights of vertices into account.In many realistic graphs,vertices are of different importance.For example,in social networks,there are many QQ groups,WeChat groups,and so on.The problem of calculating the most connected groups on average within a certain range can be transformed into the densest subgraph problem of the vertex-weighted graph.And the number of members in a group can be treated as the weight of the vertex of a graph.In this paper,we propose the problem of finding the densest subgraphs(DS)of vertex-weighted graphs,and present an algorithm for the densest subgraphs of vertex-weighted graphs.To our knowledge,no one studied this problem.We began to study it in the paper.We firstly introduce a notion of DS of vertex-weighted graphs,and then we proposed an algorithm.And we have proved that this algorithm is polynomial.The basic idea of the proposed algorithm is as follows.Firstly,we assume a vertex-weighted graph G,G’ is its densest subgraph.Let D be the density of G’.Assuming that the density of the densest subgraph is D,we can guess the value of D is g.Secondly,we try to construct a new graph whose edges’ weights relate to g and divide the graph by using the min-cut algorithms.At last,we find the densest subgraph of G by a binary search.And then,the time complexity of the algorithm is analyzed and the correctness of the algorithm is proved.The validity of thealgorithm is verified by the simulation on graphs from the real world,and relevant conclusions are obtained.In addition,an approximation algorithm based on the greedy strategy is proposed to solve the densest subgraph problem of the Vertex-Weighted Graphs with large amount of data.This algorithm removes the vertices of the average minimum value recursively to get the approximate densest subgraph,and we have already proved the approximate ratio of the approximate algorithm.