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

LineHitsSource
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     */
521    public EdgeBetweennessClusterer(int numEdgesToRemove) {
531        mNumEdgesToRemove = numEdgesToRemove;
541       mEdgesRemoved = new ArrayList();
551    }
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         
641        if (!(g instanceof Graph))
650            throw new IllegalArgumentException("Argument must be of type Graph.");
66  
671        Graph graph = (Graph)g;
68         
691        if (mNumEdgesToRemove < 0 || mNumEdgesToRemove > graph.numEdges()) {
700            throw new IllegalArgumentException("Invalid number of edges passed in.");
71         }
72  
731        mEdgesRemoved.clear();
74  
754        for (int k=0;k<mNumEdgesToRemove;k++) {
763            BetweennessCentrality bc = new BetweennessCentrality(graph,false);
773            bc.setRemoveRankScoresOnFinalize(true);
783            bc.evaluate();
793            EdgeRanking highestBetweenness = (EdgeRanking) bc.getRankings().get(0);
803            mEdgesRemoved.add(highestBetweenness.edge.getEqualEdge(graph));
813            graph.removeEdge(highestBetweenness.edge);
82         }
83  
841        WeakComponentClusterer wcSearch = new WeakComponentClusterer();
851        ClusterSet clusterSet = wcSearch.extract(graph);
861        for (Iterator iter = mEdgesRemoved.iterator(); iter.hasNext(); )
873            graph.addEdge((Edge)iter.next());
881        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() {
970        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.