2 * Created on Jul 10, 2007
4 * Copyright (c) 2007, the JUNG Project and the Regents of the University
8 * This software is open-source under the BSD license; see either
10 * http://jung.sourceforge.net/license.txt for a description.
12 package edu.uci.ics.jung.algorithms.scoring;
14 import java.util.HashMap;
17 import org.apache.commons.collections15.Transformer;
19 import edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance;
20 import edu.uci.ics.jung.algorithms.shortestpath.Distance;
21 import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
22 import edu.uci.ics.jung.graph.Hypergraph;
25 * Assigns scores to vertices based on their distances to each other vertex
28 * This class optionally normalizes its results based on the value of its
29 * 'averaging' constructor parameter. If it is <code>true</code>,
30 * then the value returned for vertex v is 1 / (_average_ distance from v to all other vertices);
31 * this is sometimes called <i>closeness centrality</i>.
32 * If it is <code>false</code>, then the value returned is 1 / (_total_ distance from
33 * v to all other vertices); this is sometimes referred to as <i>barycenter centrality</i>.
34 * (If the average/total distance is 0, the value returned is {@code Double.POSITIVE_INFINITY}.)
36 * @see BarycenterScorer
37 * @see ClosenessCentrality
39 public class DistanceCentralityScorer<V,E> implements VertexScorer<V, Double>
42 * The graph on which the vertex scores are to be calculated.
44 protected Hypergraph<V, E> graph;
47 * The metric to use for specifying the distance between pairs of vertices.
49 protected Distance<V> distance;
52 * The cache for the output results. Null encodes "not yet calculated",
53 * < 0 encodes "no such distance exists".
55 protected Map<V, Double> output;
58 * Specifies whether the values returned are the sum of the v-distances
59 * or the mean v-distance.
61 protected boolean averaging;
64 * Specifies whether, for a vertex <code>v</code> with missing (null) distances,
65 * <code>v</code>'s score should ignore the missing values or be set to 'null'.
68 protected boolean ignore_missing;
71 * Specifies whether the values returned should ignore self-distances
72 * (distances from <code>v</code> to itself).
75 protected boolean ignore_self_distances;
78 * Creates an instance with the specified graph, distance metric, and
81 * @param graph The graph on which the vertex scores are to be calculated.
82 * @param distance The metric to use for specifying the distance between
84 * @param averaging Specifies whether the values returned is the sum of all
85 * v-distances or the mean v-distance.
86 * @param ignore_missing Specifies whether scores for missing distances
87 * are to ignore missing distances or be set to null.
88 * @param ignore_self_distances Specifies whether distances from a vertex
89 * to itself should be included in its score.
91 public DistanceCentralityScorer(Hypergraph<V,E> graph, Distance<V> distance,
92 boolean averaging, boolean ignore_missing,
93 boolean ignore_self_distances)
96 this.distance = distance;
97 this.averaging = averaging;
98 this.ignore_missing = ignore_missing;
99 this.ignore_self_distances = ignore_self_distances;
100 this.output = new HashMap<V, Double>();
104 * Equivalent to <code>this(graph, distance, averaging, true, true)</code>.
106 * @param graph The graph on which the vertex scores are to be calculated.
107 * @param distance The metric to use for specifying the distance between
109 * @param averaging Specifies whether the values returned is the sum of all
110 * v-distances or the mean v-distance.
112 public DistanceCentralityScorer(Hypergraph<V,E> graph, Distance<V> distance,
115 this(graph, distance, averaging, true, true);
119 * Creates an instance with the specified graph and averaging behavior
120 * whose vertex distances are calculated based on the specified edge
123 * @param graph The graph on which the vertex scores are to be
125 * @param edge_weights The edge weights to use for specifying the distance
126 * between pairs of vertices.
127 * @param averaging Specifies whether the values returned is the sum of
128 * all v-distances or the mean v-distance.
129 * @param ignore_missing Specifies whether scores for missing distances
130 * are to ignore missing distances or be set to null.
131 * @param ignore_self_distances Specifies whether distances from a vertex
132 * to itself should be included in its score.
134 public DistanceCentralityScorer(Hypergraph<V,E> graph,
135 Transformer<E, ? extends Number> edge_weights, boolean averaging,
136 boolean ignore_missing, boolean ignore_self_distances)
138 this(graph, new DijkstraDistance<V,E>(graph, edge_weights), averaging,
139 ignore_missing, ignore_self_distances);
143 * Equivalent to <code>this(graph, edge_weights, averaging, true, true)</code>.
144 * @param graph The graph on which the vertex scores are to be
146 * @param edge_weights The edge weights to use for specifying the distance
147 * between pairs of vertices.
148 * @param averaging Specifies whether the values returned is the sum of
149 * all v-distances or the mean v-distance.
151 public DistanceCentralityScorer(Hypergraph<V,E> graph,
152 Transformer<E, ? extends Number> edge_weights, boolean averaging)
154 this(graph, new DijkstraDistance<V,E>(graph, edge_weights), averaging,
159 * Creates an instance with the specified graph and averaging behavior
160 * whose vertex distances are calculated on the unweighted graph.
162 * @param graph The graph on which the vertex scores are to be
164 * @param averaging Specifies whether the values returned is the sum of
165 * all v-distances or the mean v-distance.
166 * @param ignore_missing Specifies whether scores for missing distances
167 * are to ignore missing distances or be set to null.
168 * @param ignore_self_distances Specifies whether distances from a vertex
169 * to itself should be included in its score.
171 public DistanceCentralityScorer(Hypergraph<V,E> graph, boolean averaging,
172 boolean ignore_missing, boolean ignore_self_distances)
174 this(graph, new UnweightedShortestPath<V,E>(graph), averaging,
175 ignore_missing, ignore_self_distances);
179 * Equivalent to <code>this(graph, averaging, true, true)</code>.
180 * @param graph The graph on which the vertex scores are to be
182 * @param averaging Specifies whether the values returned is the sum of
183 * all v-distances or the mean v-distance.
185 public DistanceCentralityScorer(Hypergraph<V,E> graph, boolean averaging)
187 this(graph, new UnweightedShortestPath<V,E>(graph), averaging, true, true);
191 * Calculates the score for the specified vertex. Returns {@code null} if
192 * there are missing distances and such are not ignored by this instance.
194 public Double getVertexScore(V v)
196 Double value = output.get(v);
204 Map<V, Number> v_distances = new HashMap<V, Number>(distance.getDistanceMap(v));
205 if (ignore_self_distances)
206 v_distances.remove(v);
208 // if we don't ignore missing distances and there aren't enough
209 // distances, output null (shortcut)
212 int num_dests = graph.getVertexCount() -
213 (ignore_self_distances ? 1 : 0);
214 if (v_distances.size() != num_dests)
222 for (V w : graph.getVertices())
224 if (w.equals(v) && ignore_self_distances)
226 Number w_distance = v_distances.get(w);
227 if (w_distance == null)
236 sum += w_distance.doubleValue();
240 value /= v_distances.size();
242 double score = value == 0 ?
243 Double.POSITIVE_INFINITY :
245 output.put(v, score);