Research On The Densest Subgraph Algorithm Of Vertex-weighted Undirected Graphs With Constraints

In reality,many systems can be effectively represented as networks,such as Internet and World Wide Web,social network,citation network,food network and biochemical network.Finding dense subgraphs from these complex networks has always been the key to the study of these large-scale network problems,such as discovering related genes in genomic DNA,finding themes of price value in the financial sector,and studying the natural focus of network structure,dynamics,and evolution,etc.In addition,Extracting dense subgraphs is also one of the classic problems in the field of graph theory.In the current research on the densest subgraph problem of undirected graphs,the situation of vertex weighted graphs is not considered,but in practical problems,such as mining the relationship between communities,it is often necessary to consider the weight between communities.This thesis extends the existing approximation algorithms for densest subgraphs of undirected graphs,and proposes two approximation algorithms for densest subgraphs of constrained undirected graphs with weighted vertex.One is to learn from the algorithm idea of Andersen and Chellapilla’s algorithm for finding the densest subgraph with at least k vertices whose vertices are unweighted,and proposes a densest subgraph finding algorithm with at least k weighted vertices with an approximate ratio of 3 as constraints.The other is to study the algorithm of finding the densest subgraph of at least k vertices proposed by Khuller and Saha,and proposes the densest subgraph search algorithm with constraints that the total weight of vertices with an approximate ratio of 2 is at leastω₀.Finally,the performance of the algorithm is analyzed,and the correctness of the algorithms are proved.