|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object edu.uci.ics.jung.algorithms.cluster.EdgeBetweennessClusterer<V,E>
public class EdgeBetweennessClusterer<V,E>
An algorithm for computing clusters (community structure) in graphs based on edge betweenness. The betweenness of an edge is defined as the extent to which that edge lies along shortest paths between all pairs of nodes. This algorithm works by iteratively following the 2 step process:
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.
Constructor Summary | |
---|---|
EdgeBetweennessClusterer(int numEdgesToRemove)
Constructs a new clusterer for the specified graph. |
Method Summary | |
---|---|
List<E> |
getEdgesRemoved()
Retrieves the list of all edges that were removed (assuming extract(...) was previously called). |
Set<Set<V>> |
transform(Graph<V,E> graph)
Finds the set of clusters which have the strongest "community structure". |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public EdgeBetweennessClusterer(int numEdgesToRemove)
numEdgesToRemove
- the number of edges to be progressively removed from the graphMethod Detail |
---|
public Set<Set<V>> transform(Graph<V,E> graph)
transform
in interface org.apache.commons.collections15.Transformer<Graph<V,E>,Set<Set<V>>>
graph
- the graphpublic List<E> getEdgesRemoved()
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |