# Coverage details for edu.uci.ics.jung.algorithms.cluster.EdgeBetweennessClusterer

Line | Hits | Source
--- | --- | ---
1 |  | `/*`
2 |  | `* Copyright (c) 2003, the JUNG Project and the Regents of the University`
3 |  | `* of California`
4 |  | `* All rights reserved.`
5 |  | `*`
6 |  | `* This software is open-source under the BSD license; see either`
7 |  | `* "license.txt" or`
8 |  | `* http://jung.sourceforge.net/license.txt for a description.`
9 |  | `*/`
10 |  | `package edu.uci.ics.jung.algorithms.cluster;`
11 |  | ``
12 |  | `import java.util.ArrayList;`
13 |  | `import java.util.Iterator;`
14 |  | `import java.util.List;`
15 |  | ``
16 |  | `import edu.uci.ics.jung.algorithms.importance.BetweennessCentrality;`
17 |  | `import edu.uci.ics.jung.algorithms.importance.EdgeRanking;`
18 |  | `import edu.uci.ics.jung.graph.ArchetypeGraph;`
19 |  | `import edu.uci.ics.jung.graph.Edge;`
20 |  | `import edu.uci.ics.jung.graph.Graph;`
21 |  | ``
22 |  | ``
23 |  | `/**`
24 |  | `* An algorithm for computing clusters (community structure) in graphs based on edge betweenness.`
25 |  | `* [Note: The betweenness of an edge measure the extent to which that edge lies along shortest paths`
26 |  | `* between all pairs of nodes.]`
27 |  | `* Edges which are least central to communities are progressively removed until the communities`
28 |  | `* have been adequately seperated.`
29 |  | `*`
30 |  | `* This algorithm works by iteratively following the 2 step process:`
31 |  | `* <ul>`
32 |  | `* <li> Compute edge betweenness for all edges in current graph`
33 |  | `* <li> Remove edge with highest betweenness`
34 |  | `* <p>`
35 |  | `* Running time is: O(kmn) where k is the number of edges to remove, m is the total number of edges, and`
36 |  | `* n is the total number of vertices. For very sparse graphs the running time is closer to O(kn^2) and for`
37 |  | `* graphs with strong community structure, the complexity is even lower.`
38 |  | `* <p>`
39 |  | `* This algorithm is a slight modification of the algorithm discussed below in that the number of edges`
40 |  | `* to be removed is parameterized.`
41 |  | `* @author Scott White`
42 |  | `* @see "Community structure in social and biological networks by Michelle Girvan and Mark Newman"`
43 |  | `*/`
44 |  | `public class EdgeBetweennessClusterer implements GraphClusterer {`
45 |  | `private int mNumEdgesToRemove;`
46 |  | `private List mEdgesRemoved;`
47 |  | ``
48 |  | `/**`
49 |  | `* Constructs a new clusterer for the specified graph.`
50 |  | `* @param numEdgesToRemove the number of edges to be progressively removed from the graph`
51 |  | `*/`
52 | 1 | `public EdgeBetweennessClusterer(int numEdgesToRemove) {`
53 | 1 | `mNumEdgesToRemove = numEdgesToRemove;`
54 | 1 | `mEdgesRemoved = new ArrayList();`
55 | 1 | `}`
56 |  | ``
57 |  | `/**`
58 |  | `* Finds the set of clusters which have the strongest "community structure".`
59 |  | `* The more edges removed the smaller and more cohesive the clusters.`
60 |  | `* @param g the graph`
61 |  | `*/`
62 |  | `public ClusterSet extract(ArchetypeGraph g) {`
63 |  | ``
64 | 1 | `if (!(g instanceof Graph))`
65 | 0 | `throw new IllegalArgumentException("Argument must be of type Graph.");`
66 |  | ``
67 | 1 | `Graph graph = (Graph)g;`
68 |  | ``
69 | 1 | `if (mNumEdgesToRemove < 0 || mNumEdgesToRemove > graph.numEdges()) {`
70 | 0 | `throw new IllegalArgumentException("Invalid number of edges passed in.");`
71 |  | `}`
72 |  | ``
73 | 1 | `mEdgesRemoved.clear();`
74 |  | ``
75 | 4 | `for (int k=0;k<mNumEdgesToRemove;k++) {`
76 | 3 | `BetweennessCentrality bc = new BetweennessCentrality(graph,false);`
77 | 3 | `bc.setRemoveRankScoresOnFinalize(true);`
78 | 3 | `bc.evaluate();`
79 | 3 | `EdgeRanking highestBetweenness = (EdgeRanking) bc.getRankings().get(0);`
80 | 3 | `mEdgesRemoved.add(highestBetweenness.edge.getEqualEdge(graph));`
81 | 3 | `graph.removeEdge(highestBetweenness.edge);`
82 |  | `}`
83 |  | ``
84 | 1 | `WeakComponentClusterer wcSearch = new WeakComponentClusterer();`
85 | 1 | `ClusterSet clusterSet = wcSearch.extract(graph);`
86 | 1 | `for (Iterator iter = mEdgesRemoved.iterator(); iter.hasNext(); )`
87 | 3 | `graph.addEdge((Edge)iter.next());`
88 | 1 | `return clusterSet;`
89 |  | `}`
90 |  | ``
91 |  | `/**`
92 |  | `* Retrieves the list of all edges that were removed (assuming extract(...) was previously called. The edges returned`
93 |  | `* are stored in order in which they were removed`
94 |  | `* @return the edges in the original graph`
95 |  | `*/`
96 |  | `public List getEdgesRemoved() {`
97 | 0 | `return mEdgesRemoved;`
98 |  | `}`
99 |  | `}`

this report was generated by version 1.0.5 of jcoverage. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.