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

java.lang.Object
  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