| 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. |
copyright © 2003, jcoverage ltd. all rights reserved. |