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

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

All Implemented Interfaces:

GraphClusterer

public class EdgeBetweennessClusterer

extends java.lang.Object

implements GraphClusterer

An algorithm for computing clusters (community structure) in graphs based on edge betweenness. [Note: The betweenness of an edge measure the extent to which that edge lies along shortest paths between all pairs of nodes.] Edges which are least central to communities are progressively removed until the communities have been adequately seperated. This algorithm works by iteratively following the 2 step process:

• Compute edge betweenness for all edges in current graph
• Remove edge with highest betweenness

  Running time is: O(kmn) where k is the number of edges to remove, m is the total number of edges, and n is the total number of vertices. For very sparse graphs the running time is closer to O(kn^2) and for graphs with strong community structure, the complexity is even lower.

  This algorithm is a slight modification of the algorithm discussed below in that the number of edges to be removed is parameterized.

  Author:

  Scott White

  See Also:

  "Community structure in social and biological networks by Michelle Girvan and Mark Newman"

  Constructor Summary

  EdgeBetweennessClusterer(int numEdgesToRemove)
  Constructs a new clusterer for the specified graph.

  Method Summary

  ClusterSet	extract(Graph graph) Finds the set of clusters which have the strongest "community structure".
  java.util.List	getEdgesRemoved() Retrieves the list of all edges that were removed (assuming extract(...) was previously called.

  Methods inherited from class java.lang.Object

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

  Constructor Detail

  EdgeBetweennessClusterer

  public EdgeBetweennessClusterer(int numEdgesToRemove)

  Constructs a new clusterer for the specified graph.

  Parameters:

  numEdgesToRemove - the number of edges to be progressively removed from the graph

  Method Detail

  extract

  public ClusterSet extract(Graph graph)

  Finds the set of clusters which have the strongest "community structure". The more edges removed the smaller and more cohesive the clusters.

  Specified by:

  extract in interface GraphClusterer

  Parameters:

  graph - the graph

  Returns:

  the set of clusters

  getEdgesRemoved

  public java.util.List getEdgesRemoved()

  Retrieves the list of all edges that were removed (assuming extract(...) was previously called. The edges returned are stored in order in which they were removed

  Returns:

  the edges in the original graph