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

Class GoldbergMaximumDensitySubgraphAlgorithm<V,​E>

  • Type Parameters:
    V - Type of vertices
    E - Type of edges
    All Implemented Interfaces:
    MaximumDensitySubgraphAlgorithm<V,​E>
    public class GoldbergMaximumDensitySubgraphAlgorithm<V,​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. See GoldbergMaximumDensitySubgraphAlgorithmBase for further details

    This variant of the algorithm assumes the density of a positive real-weighted graph G=(V,E) to be defined as \[\frac{\sum\limits_{e \in E} w(e)}{\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\,\forall i \in V\] \[c_{si}=m\,\forall i \in V\] where $m=\left|{E}\right|$ and $d_i$ is the degree of vertex $i$.
    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 weights from $G$.

    Author:
    Andre Immig

    • Constructor Detail

      • GoldbergMaximumDensitySubgraphAlgorithm

        public GoldbergMaximumDensitySubgraphAlgorithm​(Graph<V,​E> graph,
                                               V s,
                                               V t,
                                               double epsilon,
                                               Function<Graph<V,​DefaultWeightedEdge>,​MinimumSTCutAlgorithm<V,​DefaultWeightedEdge>> algFactory)
        Constructor
        Parameters:
        algFactory - factory to construct the algorithm to use
        graph - input for computation
        s - additional source vertex
        t - additional target vertex
        epsilon - to use for internal computation

      • GoldbergMaximumDensitySubgraphAlgorithm

        public GoldbergMaximumDensitySubgraphAlgorithm​(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