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

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.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) {
421       super(g,null,null);
431    }
44  
45     protected void computeBetweenness() {
461        setUp();
47  
481        int numVertices = getGraph().numVertices();
491        double normalizingConstant = numVertices*(numVertices-1)/2.0;
50  
511        for (Iterator iIt = getGraph().getVertices().iterator();iIt.hasNext();) {
5211            Vertex ithVertex = (Vertex) iIt.next();
53  
5411            double ithBetweenness = 0;
55132            for (int t=0;t<numVertices;t++) {
56726                for (int s=0;s<t;s++) {
57605                    Vertex sthVertex = (Vertex) getIndexer().getVertex(s);
58605                    Vertex tthVertex = (Vertex) getIndexer().getVertex(t);
59605                    ithBetweenness += computeSTBetweenness(ithVertex,sthVertex, tthVertex);
60                 }
61             }
6211            setRankScore(ithVertex,ithBetweenness/normalizingConstant);
63         }
641    }
65  
66  
67  
68     /**
69      * the user datum key used to store the rank scores
70      * @return the key
71      */
72     public String getRankScoreKey() {
7338        return CENTRALITY;
74     }
75  
76     protected double evaluateIteration() {
771        computeBetweenness();
781        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.