  Densest Subgraph Problem (DSP) is an important primitive problem with a wide
range of applications, including fraud detection, community detection and DNA
motif discovery. Edge-based density is one of the most common metrics in DSP.
Although a maximum flow algorithm can exactly solve it in polynomial time, the
increasing amount of data and the high complexity of algorithms motivate
scientists to find approximation algorithms. Among these, its duality of linear
programming derives several iterative algorithms including Greedy++,
Frank-Wolfe and FISTA which redistribute edge weights to find the densest
subgraph, however, these iterative algorithms vibrate around the optimal
solution, which are not satisfactory for fast convergence. We propose our main
algorithm Locally Optimal Weight Distribution (LOWD) to distribute the
remaining edge weights in a locally optimal operation to converge to the
optimal solution monotonically. Theoretically, we show that it will reach the
optimal state of a specific linear programming which is called locally-dense
decomposition. Besides, we show that it is not necessary to consider most of
the edges in the original graph. Therefore, we develop a pruning algorithm
using a modified Counting Sort to prune graphs by removing unnecessary edges
and nodes, and then we can search the densest subgraph in a much smaller graph.
