Class GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight<V extends Pair<?,java.lang.Double>,E>
- java.lang.Object
-
- org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmBase<V,E>
-
- org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight<V,E>
-
- Type Parameters:
V
- Type of verticesE
- Type of edges
- All Implemented Interfaces:
MaximumDensitySubgraphAlgorithm<V,E>
public class GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight<V extends Pair<?,java.lang.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 inGoldbergMaximumDensitySubgraphAlgorithmBase
.
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 MinimumSTCutAlgorithmGoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight(Graph<V,E> graph, V s, V t, double epsilon, java.util.function.Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor
-
Method Summary
All Methods Instance Methods Concrete Methods 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 Vprotected 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
-
-
-
-
Constructor Detail
-
GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight
public GoldbergMaximumDensitySubgraphAlgorithmNodeWeightPerEdgeWeight(Graph<V,E> graph, V s, V t, double epsilon, java.util.function.Function<Graph<V,DefaultWeightedEdge>,MinimumSTCutAlgorithm<V,DefaultWeightedEdge>> algFactory)
Constructor- Parameters:
graph
- input for computations
- additional source vertext
- additional target vertexepsilon
- to use for internal computationalgFactory
- 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 computations
- additional source vertext
- additional target vertexepsilon
- to use for internal computation
-
-
Method Detail
-
computeDensityNumerator
protected double computeDensityNumerator(Graph<V,E> g)
- Specified by:
computeDensityNumerator
in classGoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,java.lang.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 classGoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,java.lang.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 classGoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,java.lang.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 classGoldbergMaximumDensitySubgraphAlgorithmBase<V extends Pair<?,java.lang.Double>,E>
- Parameters:
v
- of V- Returns:
- weight of the edge (v,t)
-
-