Module org.jgrapht.core
Package org.jgrapht.alg.densesubgraph

Class GoldbergMaximumDensitySubgraphAlgorithmNodeWeights<V extends Pair<?,Double>,E>

java.lang.Object
org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmBase<V,E>
org.jgrapht.alg.densesubgraph.GoldbergMaximumDensitySubgraphAlgorithmNodeWeights<V,E>
Type Parameters:
V - Type of vertices
E - Type of edges
All Implemented Interfaces:
MaximumDensitySubgraphAlgorithm<V,E>
public class GoldbergMaximumDensitySubgraphAlgorithmNodeWeights<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)}{\left|{V}\right|}\] 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'+2g-d_i-2w(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$.
For details see GoldbergMaximumDensitySubgraphAlgorithmBase. All the math to prove the correctness of these weights is the same.

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 all edge and vertex weights from $G$.

Author:
Andre Immig