Class GoldbergMaximumDensitySubgraphAlgorithmBase<V,E>
- java.lang.Object
-
- org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmBase<V,E>
-
- Type Parameters:
V
- Type of verticesE
- Type of edges
- All Implemented Interfaces:
MaximumDensitySubgraphAlgorithm<V,E>
- Direct Known Subclasses:
GoldbergMaximumDensitySubgraphAlgorithm
,GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight
,GoldbergMaximumDensitySubgraphAlgorithmNodeWeights
public abstract class GoldbergMaximumDensitySubgraphAlgorithmBase<V,E> extends java.lang.Object implements MaximumDensitySubgraphAlgorithm<V,E>
This abstract base class computes a maximum density subgraph based on the algorithm described by Andrew Vladislav Goldberg in Finding Maximum Density Subgraphs, 1984, University of Berkley. Each subclass decides which concrete definition of density is used by implementinggetEdgeWeightFromSourceToVertex(Object)
andgetEdgeWeightFromVertexToSink(Object)
as proposed in the paper. After the computation the density is computed usingMaximumDensitySubgraphAlgorithm.getDensity()
.
The basic concept is to construct a network that can be used to compute the maximum density subgraph using a binary search approach.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
The idea of the algorithm is to construct a network based on the input graph $G=(V,E)$ and some guess $g$ for the density. This network $N=(V_N, E_N)$ is constructed as follows: \[V_N=V\cup {s,t}\] \[E_N=\{(i,j)| \{i,j\} \in E\} \cup \{(s,i)| i\in V\} \cup \{(i,t)| i \in V\}\]GoldbergMaximumDensitySubgraphAlgorithm
; because the following math translates directly to other variants the full math is only fully explained once.
Additionally one defines the following weights for the network: \[c_{ij}=1 \forall \{i,j\}\in E\] \[c_{si}=m \forall i \in V\] \[c_{it}=m+2g-d_i \forall i \in V\] where $m=\left|{E}\right|$ and $d_i$ is the degree of vertex $i$.
As seen later these weights depend on the definition of the density. Therefore these weights and the following applies to the definition of density from above. Definitions suitable for other cases in can be found in the corresponding subclasses.Using this network one can show some important properties, that are essential for the algorithm to work. The capacity of a s-t 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 s-t Cut. Using the above equation, one can derive that given a minimum s-t 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(n-1)}$. 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 aMinimumSTCutAlgorithm
whose runtime doesn't depend on the number of edges, because the network $N$ has $O(n+m)$ edges. Preferably one should usePushRelabelMFImpl
, 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.
-
-
Field Summary
Fields Modifier and Type Field Description private boolean
checkWeights
private Graph<V,DefaultWeightedEdge>
currentNetwork
private java.util.Set<V>
currentVertices
private Graph<V,E>
densestSubgraph
private double
epsilon
protected Graph<V,E>
graph
protected double
guess
private double
lower
private MinimumSTCutAlgorithm<V,DefaultWeightedEdge>
minSTCutAlg
private V
s
private V
t
private double
upper
-
Constructor Summary
Constructors Constructor Description GoldbergMaximumDensitySubgraphAlgorithmBase(Graph<V,E> graph, V s, V t, boolean checkWeights, double epsilon, java.util.function.Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor
-
Method Summary
All Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description private Graph<V,DefaultWeightedEdge>
buildNetwork()
Helper method for constructing the internally used networkGraph<V,E>
calculateDensest()
Algorithm to compute max density subgraph Performs binary search on the initial interval lower-upper 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.private void
checkForEmptySolution()
Check if denominator will be empty to avoid dividing by 0.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 Vprotected abstract double
getEdgeWeightFromVertexToSink(V vertex)
Getter for network weights of edges ut for u in Vprivate double
getMinimalCapacity()
private void
initializeNetwork()
Initializes network (only once) for Min-Cut computation Adds s,t to vertex set Adds every v in V to vertex set Adds edge sv and vt for each v in V to edge set Adds every edge uv and vu from E to edge set Sets edge weights for all edges from Eprivate void
updateNetwork()
Updates network for next computation, e.g edges from v to t and from s to v Enforces positivity on network weights if specified by adding subtracting the lowest weights to all edges $(v,t)$ and $(v,s)$.
-
-
-
Field Detail
-
lower
private double lower
-
upper
private double upper
-
epsilon
private double epsilon
-
guess
protected double guess
-
currentNetwork
private Graph<V,DefaultWeightedEdge> currentNetwork
-
currentVertices
private java.util.Set<V> currentVertices
-
s
private V s
-
t
private V t
-
minSTCutAlg
private MinimumSTCutAlgorithm<V,DefaultWeightedEdge> minSTCutAlg
-
checkWeights
private boolean checkWeights
-
-
Constructor Detail
-
GoldbergMaximumDensitySubgraphAlgorithmBase
public GoldbergMaximumDensitySubgraphAlgorithmBase(Graph<V,E> graph, V s, V t, boolean checkWeights, double epsilon, java.util.function.Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor- Parameters:
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 subalgorithm
-
-
Method Detail
-
buildNetwork
private Graph<V,DefaultWeightedEdge> buildNetwork()
Helper method for constructing the internally used network
-
updateNetwork
private void updateNetwork()
Updates network for next computation, e.g edges from v to t and from s to v Enforces positivity on network weights if specified by adding subtracting the lowest weights to all edges $(v,t)$ and $(v,s)$.
-
getMinimalCapacity
private double getMinimalCapacity()
- Returns:
- the minimal capacity of all edges vt and sv
-
initializeNetwork
private void initializeNetwork()
Initializes network (only once) for Min-Cut computation Adds s,t to vertex set Adds every v in V to vertex set Adds edge sv and vt for each v in V to edge set Adds every edge uv and vu from E to edge set Sets edge weights for all edges from E
-
calculateDensest
public Graph<V,E> calculateDensest()
Algorithm to compute max density subgraph Performs binary search on the initial interval lower-upper 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.- Specified by:
calculateDensest
in interfaceMaximumDensitySubgraphAlgorithm<V,E>
- Returns:
- max density subgraph of the graph
-
getDensity
public double getDensity()
Computes density of a maximum density subgraph.- Specified by:
getDensity
in interfaceMaximumDensitySubgraphAlgorithm<V,E>
- Returns:
- the actual density of the maximum density subgraph
-
getEdgeWeightFromSourceToVertex
protected abstract double getEdgeWeightFromSourceToVertex(V vertex)
Getter for network weights of edges su for u in V- Parameters:
vertex
- of V- Returns:
- weight of the edge (s,v)
-
getEdgeWeightFromVertexToSink
protected abstract double getEdgeWeightFromVertexToSink(V vertex)
Getter for network weights of edges ut for u in V- Parameters:
vertex
- of V- Returns:
- weight of the edge (v,t)
-
computeDensityNumerator
protected abstract double computeDensityNumerator(Graph<V,E> g)
- Parameters:
g
- the graph to compute the numerator density from- Returns:
- numerator part of the density
-
computeDensityDenominator
protected abstract double computeDensityDenominator(Graph<V,E> g)
- Parameters:
g
- the graph to compute the denominator density from- Returns:
- numerator part of the density
-
checkForEmptySolution
private void checkForEmptySolution()
Check if denominator will be empty to avoid dividing by 0.
-
-