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

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

public class ExactFlowCommunity

extends java.lang.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 cohestionThreshold)
Constructs and initializes the algorithm

Method Summary

java.util.Set	extract(DirectedGraph graph, java.util.Set rootSet) Extracts the community according to the cohesion threshold
static java.util.Set	extract(DirectedGraph graph, java.util.Set rootSet, int numIterations) Implements the "ApproximateFlowCommunity" algorithm.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ExactFlowCommunity

public ExactFlowCommunity(int cohestionThreshold)

Constructs and initializes the algorithm

Parameters:

cohestionThreshold - a heuristic value that determines the level of cohesion for the community to be extracted

Method Detail

extract

public java.util.Set extract(DirectedGraph graph,
                             java.util.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 java.util.Set extract(DirectedGraph graph,
                                    java.util.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