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

Constructors

Constructor and Description
ExactFlowCommunity(int cohesionThreshold) Constructs and initializes the algorithm

Method Summary

Methods

Modifier and Type	Method and Description
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.
protected void	initializeFlowGraph(DirectedGraph flowGraph, Vertex source, Vertex sink, java.util.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 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

initializeFlowGraph

protected void initializeFlowGraph(DirectedGraph flowGraph,
                       Vertex source,
                       Vertex sink,
                       java.util.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