edu.uci.ics.jung.algorithms.cluster
Class ExactFlowCommunity

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.cluster.ExactFlowCommunity

public class ExactFlowCommunity
extends Object

ExactFlowCommunity is an algorithm that uses a set of root nodes that are supposed to be representative of a community to find the entire community using principles based on max-flow/min-cut.

Author:
Scott White
See Also:
"Self-Organization of the Web and Identification of Communities by Gary Flake, Steve Lawrence, Lee Giles, and Frans Coetzee, 2002", "http://www.neci.nec.com/~lawrence/papers/web-computer02/web-computer02.pdf"

Constructor Summary
ExactFlowCommunity(int cohesionThreshold)
          Constructs and initializes the algorithm
 
Method Summary
 Set extract(DirectedGraph graph, Set rootSet)
          Extracts the community according to the cohesion threshold
static Set extract(DirectedGraph graph, Set rootSet, int numIterations)
          Implements the "ApproximateFlowCommunity" algorithm.
protected  void initializeFlowGraph(DirectedGraph flowGraph, Vertex source, Vertex sink, Set rootSet)
          Initialize the flow graph
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

ExactFlowCommunity

public ExactFlowCommunity(int cohesionThreshold)
Constructs and initializes the algorithm

Parameters:
cohesionThreshold - a heuristic value that determines the level of cohesion for the community to be extracted
Method Detail

extract

public Set extract(DirectedGraph graph,
                   Set rootSet)
Extracts the community according to the cohesion threshold

Parameters:
graph - the original graph
rootSet - the set of nodes used to see the community
Returns:
a set of nodes representative of the community used to seed the algorithm

extract

public static Set extract(DirectedGraph graph,
                          Set rootSet,
                          int numIterations)
Implements the "ApproximateFlowCommunity" algorithm. Repeatedly finds the community at low distances from the starting set, and grows outward. UNDERTESTED.

Parameters:
graph - the original graph
rootSet - the set of nodes used to see the community
Returns:
a set of nodes representative of the community used to seed the algorithm

initializeFlowGraph

protected void initializeFlowGraph(DirectedGraph flowGraph,
                                   Vertex source,
                                   Vertex sink,
                                   Set rootSet)
Initialize the flow graph

Parameters:
flowGraph - the flow graph
source - the source node
sink - the sink node
rootSet - the set of nodes used to seed the community