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. |