# Coverage details for edu.uci.ics.jung.algorithms.importance.RandomWalkBetweenness

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.importance;`
11 |  | ``
12 |  | `import java.util.Iterator;`
13 |  | ``
14 |  | `import edu.uci.ics.jung.graph.UndirectedGraph;`
15 |  | `import edu.uci.ics.jung.graph.Vertex;`
16 |  | ``
17 |  | `/**`
18 |  | `* Computes betweenness centrality for each vertex in the graph. The betweenness values in this case`
19 |  | `* are based on random walks, measuring the expected number of times a node is traversed by a random walk`
20 |  | `* averaged over all pairs of nodes. The result is that each vertex has a UserData element of type`
21 |  | `* MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality'`
22 |  | `*`
23 |  | `* A simple example of usage is: <br>`
24 |  | `* RandomWalkBetweenness ranker = new RandomWalkBetweenness(someGraph); <br>`
25 |  | `* ranker.evaluate(); <br>`
26 |  | `* ranker.printRankings(); <p>`
27 |  | `*`
28 |  | `* Running time is: O((m+n)*n^2).`
29 |  | `* @see "Mark Newman: A measure of betweenness centrality based on random walks, 2002."`
30 |  | ``
31 |  | `* @author Scott White`
32 |  | `*/`
33 |  | `public class RandomWalkBetweenness extends RandomWalkSTBetweenness {`
34 |  | ``
35 |  | `public static final String CENTRALITY = "centrality.RandomWalkBetweennessCentrality";`
36 |  | ``
37 |  | `/**`
38 |  | `* Constructor which initializes the algorithm`
39 |  | `* @param g the graph whose nodes are to be analyzed`
40 |  | `*/`
41 |  | `public RandomWalkBetweenness(UndirectedGraph g) {`
42 | 1 | `super(g,null,null);`
43 | 1 | `}`
44 |  | ``
45 |  | `protected void computeBetweenness() {`
46 | 1 | `setUp();`
47 |  | ``
48 | 1 | `int numVertices = getGraph().numVertices();`
49 | 1 | `double normalizingConstant = numVertices*(numVertices-1)/2.0;`
50 |  | ``
51 | 1 | `for (Iterator iIt = getGraph().getVertices().iterator();iIt.hasNext();) {`
52 | 11 | `Vertex ithVertex = (Vertex) iIt.next();`
53 |  | ``
54 | 11 | `double ithBetweenness = 0;`
55 | 132 | `for (int t=0;t<numVertices;t++) {`
56 | 726 | `for (int s=0;s<t;s++) {`
57 | 605 | `Vertex sthVertex = (Vertex) getIndexer().getVertex(s);`
58 | 605 | `Vertex tthVertex = (Vertex) getIndexer().getVertex(t);`
59 | 605 | `ithBetweenness += computeSTBetweenness(ithVertex,sthVertex, tthVertex);`
60 |  | `}`
61 |  | `}`
62 | 11 | `setRankScore(ithVertex,ithBetweenness/normalizingConstant);`
63 |  | `}`
64 | 1 | `}`
65 |  | ``
66 |  | ``
67 |  | ``
68 |  | `/**`
69 |  | `* the user datum key used to store the rank scores`
70 |  | `* @return the key`
71 |  | `*/`
72 |  | `public String getRankScoreKey() {`
73 | 38 | `return CENTRALITY;`
74 |  | `}`
75 |  | ``
76 |  | `protected double evaluateIteration() {`
77 | 1 | `computeBetweenness();`
78 | 1 | `return 0;`
79 |  | `}`
80 |  | `}`

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.