# Class GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight<V extends Pair<?,Double>,E>

java.lang.Object
org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmBase<V,E>
org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight<V,E>
Type Parameters:
V - Type of vertices
E - Type of edges
All Implemented Interfaces:
MaximumDensitySubgraphAlgorithm<V,E>

public class GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight<V extends Pair<?,Double>,E> extends GoldbergMaximumDensitySubgraphAlgorithmBase<V,E>
This class computes a maximum density subgraph based on the algorithm described by Andrew Vladislav Goldberg in Finding Maximum Density Subgraphs, 1984, University of Berkley.
The basic concept is to construct a network that can be used to compute the maximum density subgraph using a binary search approach.

This variant of the algorithm assumes the density of a positive real edge and vertex weighted graph G=(V,E) to be defined as $\frac{\sum\limits_{e \in E} w(e)}{\sum\limits_{v \in V} w(v)}$ and sets the weights of the network from GoldbergMaximumDensitySubgraphAlgorithmBase as proposed in the above paper. For this case the weights of the network must be chosen to be: $c_{ij}=w(ij)\,\forall \{i,j\}\in E$ $c_{it}=m'+2gw(i)-d_i\,\forall i \in V$ $c_{si}=m'\,\forall i \in V$ where $m'$ is such, that all weights are positive and $d_i$ is the degree of vertex $i$ and $w(v)$ is the weight of vertex $v$.
All the math to prove the correctness of these weights is the same as in GoldbergMaximumDensitySubgraphAlgorithmBase.

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}{W(W-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{W})$, where $M(n,m)$ is the runtime of the internally used MinimumSTCutAlgorithm and $W$ is the sum of all edge weights from $G$.

Author:
Andre Immig
• ## Field Summary

### Fields inherited from class org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmBase

graph, guess
• ## Constructor Summary

Constructors
Constructor
Description
GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight(Graph<V,E> graph, V s, V t, double epsilon)
Convenience constructor that uses PushRelabel as default MinimumSTCutAlgorithm
GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight(Graph<V,E> graph, V s, V t, double epsilon, Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor
• ## Method Summary

Modifier and Type
Method
Description
protected double
computeDensityDenominator(Graph<V,E> g)

protected double
computeDensityNumerator(Graph<V,E> g)

protected double
getEdgeWeightFromSourceToVertex(V v)
Getter for network weights of edges su for u in V
protected double
getEdgeWeightFromVertexToSink(V v)
Getter for network weights of edges ut for u in V

### Methods inherited from class org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmBase

calculateDensest, getDensity

### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ## Constructor Details

• ### GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight

public GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight(Graph<V,E> graph, V s, V t, double epsilon, Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor
Parameters:
graph - input for computation
s - additional source vertex
t - additional target vertex
epsilon - to use for internal computation
algFactory - function to construct the subalgorithm
• ### GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight

public GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight(Graph<V,E> graph, V s, V t, double epsilon)
Convenience constructor that uses PushRelabel as default MinimumSTCutAlgorithm
Parameters:
graph - input for computation
s - additional source vertex
t - additional target vertex
epsilon - to use for internal computation
• ## Method Details

• ### computeDensityNumerator

protected double computeDensityNumerator(Graph<V,E> g)
Specified by:
computeDensityNumerator in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>
Parameters:
g - the graph to compute the numerator density from
Returns:
numerator part of the density
• ### computeDensityDenominator

protected double computeDensityDenominator(Graph<V,E> g)
Specified by:
computeDensityDenominator in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>
Parameters:
g - the graph to compute the denominator density from
Returns:
numerator part of the density
• ### getEdgeWeightFromSourceToVertex

protected double getEdgeWeightFromSourceToVertex(V v)
Description copied from class: GoldbergMaximumDensitySubgraphAlgorithmBase
Getter for network weights of edges su for u in V
Specified by:
getEdgeWeightFromSourceToVertex in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>
Parameters:
v - of V
Returns:
weight of the edge (s,v)
• ### getEdgeWeightFromVertexToSink

protected double getEdgeWeightFromVertexToSink(V v)
Description copied from class: GoldbergMaximumDensitySubgraphAlgorithmBase
Getter for network weights of edges ut for u in V
Specified by:
getEdgeWeightFromVertexToSink in class GoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,Double>,E>
Parameters:
v - of V
Returns:
weight of the edge (v,t)