Module org.jgrapht.core

Package org.jgrapht.alg.densesubgraph

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)