Research On The Algorithm For Finding Dense Subgraphs In Vertex-weighted Directed Graphs

Modeling and analyzing large data sets using network-based methods is an emerging research field at present.For example,in biology and medicine,networks are used to simulate the interactions between biomolecules as well as the relationships between patients.Similarly,data coming from social directed networks can be modeled by graphs.Finding and solving dense subgraph problems have always been the core of dealing with complicated network problems,such as discovering communities in social networks,detecting regulatory motifs in DNA,and recognizing real-time events in news,and so on.In addition,it is a classical problem in graph theory as well.In this thesis,we propose two exact algorithms for solving the densest subgraphs of directed graphs.One is the maximum flow algorithm for vertex-weighted directed graphs: given a weighted directed graph,and then assume a predicted value g,through constructing a bipartite graph,set the source and goal vertex,and then in accordance with the maximum flow and the minimum cut theory,the relationship between the maximum density and the cut value is established.At last,use the binary search method to iterate continually to obtain the maximum density and the densest subgraph of this graph.The other one is to adopt the linear programming approach to obtain the maximum dense subgraph of the vertex-weighted directed graph: give the related definitions and prove the algorithm is correct.