V
 Type of verticesE
 Type of edgespublic abstract class GoldbergMaximumDensitySubgraphAlgorithmBase<V,E> extends Object implements MaximumDensitySubgraphAlgorithm<V,E>
getEdgeWeightFromSourceToVertex(Object)
and
getEdgeWeightFromVertexToSink(Object)
as proposed in the paper. After the computation the density is
computed using MaximumDensitySubgraphAlgorithm.getDensity()
.
In the simplest case of an unweighted graph $G=(V,E)$ the density of $G$ can be defined to be
\[\frac{\left{E}\right}{\left{V}\right}\], where a directed graph can be considered as undirected.
Therefore it is in this case equal to half the average vertex degree. This variant is implemented in
GoldbergMaximumDensitySubgraphAlgorithm
; because the following math translates directly to other variants
the full math is only fully explained once.
Using this network one can show some important properties, that are essential for the algorithm to work. The capacity of a st of N is given by: \[C(S,T) = m\left{V}\right + 2\left{V_1}\right\left(g  D_1\right)\] where $V_1 \dot{\cup} V_2=V$ and $V_1 = S\setminus \{s\}, V_2= T\setminus \{t\}$ and $D_1$ shall be the density of the induced subgraph of $V_1$ regarding $G$.
Especially important is the capacity of minimum st Cut. Using the above equation, one can derive that given a minimum st Cut of $N$ and the maximum density of $G$ to be $D$, then $g\geq D$ if $V_1=\emptyset$,otherwise $g\leq D$. Moreover the induced subgraph of $V_1$ regarding G is guaranteed to have density greater $g$, otherwise it can be used to proof that there can't exist any subgraph of $G$ greater $g$. Based on this property one can use a binary search approach to shrink the possible interval which contains the solution.
Because the density is per definition guaranteed to be rational, the distance of 2 possible
solutions for the maximum density can't be smaller than $\frac{1}{n(n1)}$. This means shrinking
the binary search interval to this size, the correct solution is found.
The runtime can in this case be given by $O(M(n,n+m)\log{n}$, where $M(n,m)$ is the runtime of
the internally used MinimumSTCutAlgorithm
. Especially for large networks it is advised to use a
MinimumSTCutAlgorithm
whose runtime doesn't depend on the number of edges, because the network $N$ has
$O(n+m)$ edges. Preferably one should use PushRelabelMFImpl
, leading
to a runtime of $O(n^{3}\log{n})$.
Similar to the above explanation the same argument can be applied for other definitions of density by adapting the definitions and the network accordingly. Some generalizations can be found in the paper. As these more general variants including edge weights are only guaranteed to terminate for integer edge weights, instead of using the natural termination property, the algorithm needs to be called with $\varepsilon$ in the constructor. The computation then ensures, that the returned maximum density only differs at most $\varepsilon$ from the correct solution. This is why subclasses of this class might have a little different runtime analysis regarding the $\log{n}$ part.
Modifier and Type  Field and Description 

protected Graph<V,E> 
graph 
protected double 
guess 
Constructor and Description 

GoldbergMaximumDensitySubgraphAlgorithmBase(Graph<V,E> graph,
V s,
V t,
boolean checkWeights,
double epsilon,
Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor

Modifier and Type  Method and Description 

Graph<V,E> 
calculateDensest()
Algorithm to compute max density subgraph
Performs binary search on the initial interval lowerupper until interval is smaller than epsilon
In case no solution is found because epsilon is too big, the computation continues until a
(first) solution is found, thereby avoiding to return an empty graph.

protected abstract double 
computeDensityDenominator(Graph<V,E> g) 
protected abstract double 
computeDensityNumerator(Graph<V,E> g) 
double 
getDensity()
Computes density of a maximum density subgraph.

protected abstract double 
getEdgeWeightFromSourceToVertex(V vertex)
Getter for network weights of edges su for u in V

protected abstract double 
getEdgeWeightFromVertexToSink(V vertex)
Getter for network weights of edges ut for u in V

public GoldbergMaximumDensitySubgraphAlgorithmBase(Graph<V,E> graph, V s, V t, boolean checkWeights, double epsilon, Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
graph
 input for computations
 additional source vertext
 additional target vertexcheckWeights
 if true implementation will enforce all internal weights to be positiveepsilon
 to use for internal computationalgFactory
 function to construct the subalgorithmpublic Graph<V,E> calculateDensest()
calculateDensest
in interface MaximumDensitySubgraphAlgorithm<V,E>
public double getDensity()
getDensity
in interface MaximumDensitySubgraphAlgorithm<V,E>
protected abstract double getEdgeWeightFromSourceToVertex(V vertex)
vertex
 of Vprotected abstract double getEdgeWeightFromVertexToSink(V vertex)
vertex
 of Vprotected abstract double computeDensityNumerator(Graph<V,E> g)
g
 the graph to compute the numerator density fromCopyright © 2019. All rights reserved.