/*
* Created on Jul 10, 2007
*
* Copyright (c) 2007, the JUNG Project and the Regents of the University
* of California
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* http://jung.sourceforge.net/license.txt for a description.
*/
package edu.uci.ics.jung.algorithms.scoring;
import java.util.HashMap;
import java.util.Map;
import org.apache.commons.collections15.Transformer;
import edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance;
import edu.uci.ics.jung.algorithms.shortestpath.Distance;
import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
import edu.uci.ics.jung.graph.Hypergraph;
/**
* Assigns scores to vertices based on their distances to each other vertex
* in the graph.
*
* This class optionally normalizes its results based on the value of its
* 'averaging' constructor parameter. If it is true,
* then the value returned for vertex v is 1 / (_average_ distance from v to all other vertices);
* this is sometimes called closeness centrality.
* If it is false, then the value returned is 1 / (_total_ distance from
* v to all other vertices); this is sometimes referred to as barycenter centrality.
* (If the average/total distance is 0, the value returned is {@code Double.POSITIVE_INFINITY}.)
*
* @see BarycenterScorer
* @see ClosenessCentrality
*/
public class DistanceCentralityScorer implements VertexScorer
{
/**
* The graph on which the vertex scores are to be calculated.
*/
protected Hypergraph graph;
/**
* The metric to use for specifying the distance between pairs of vertices.
*/
protected Distance distance;
/**
* The cache for the output results. Null encodes "not yet calculated",
* < 0 encodes "no such distance exists".
*/
protected Map output;
/**
* Specifies whether the values returned are the sum of the v-distances
* or the mean v-distance.
*/
protected boolean averaging;
/**
* Specifies whether, for a vertex v with missing (null) distances,
* v's score should ignore the missing values or be set to 'null'.
* Defaults to 'true'.
*/
protected boolean ignore_missing;
/**
* Specifies whether the values returned should ignore self-distances
* (distances from v to itself).
* Defaults to 'true'.
*/
protected boolean ignore_self_distances;
/**
* Creates an instance with the specified graph, distance metric, and
* averaging behavior.
*
* @param graph The graph on which the vertex scores are to be calculated.
* @param distance The metric to use for specifying the distance between
* pairs of vertices.
* @param averaging Specifies whether the values returned is the sum of all
* v-distances or the mean v-distance.
* @param ignore_missing Specifies whether scores for missing distances
* are to ignore missing distances or be set to null.
* @param ignore_self_distances Specifies whether distances from a vertex
* to itself should be included in its score.
*/
public DistanceCentralityScorer(Hypergraph graph, Distance distance,
boolean averaging, boolean ignore_missing,
boolean ignore_self_distances)
{
this.graph = graph;
this.distance = distance;
this.averaging = averaging;
this.ignore_missing = ignore_missing;
this.ignore_self_distances = ignore_self_distances;
this.output = new HashMap();
}
/**
* Equivalent to this(graph, distance, averaging, true, true).
*
* @param graph The graph on which the vertex scores are to be calculated.
* @param distance The metric to use for specifying the distance between
* pairs of vertices.
* @param averaging Specifies whether the values returned is the sum of all
* v-distances or the mean v-distance.
*/
public DistanceCentralityScorer(Hypergraph graph, Distance distance,
boolean averaging)
{
this(graph, distance, averaging, true, true);
}
/**
* Creates an instance with the specified graph and averaging behavior
* whose vertex distances are calculated based on the specified edge
* weights.
*
* @param graph The graph on which the vertex scores are to be
* calculated.
* @param edge_weights The edge weights to use for specifying the distance
* between pairs of vertices.
* @param averaging Specifies whether the values returned is the sum of
* all v-distances or the mean v-distance.
* @param ignore_missing Specifies whether scores for missing distances
* are to ignore missing distances or be set to null.
* @param ignore_self_distances Specifies whether distances from a vertex
* to itself should be included in its score.
*/
public DistanceCentralityScorer(Hypergraph graph,
Transformer edge_weights, boolean averaging,
boolean ignore_missing, boolean ignore_self_distances)
{
this(graph, new DijkstraDistance(graph, edge_weights), averaging,
ignore_missing, ignore_self_distances);
}
/**
* Equivalent to this(graph, edge_weights, averaging, true, true).
* @param graph The graph on which the vertex scores are to be
* calculated.
* @param edge_weights The edge weights to use for specifying the distance
* between pairs of vertices.
* @param averaging Specifies whether the values returned is the sum of
* all v-distances or the mean v-distance.
*/
public DistanceCentralityScorer(Hypergraph graph,
Transformer edge_weights, boolean averaging)
{
this(graph, new DijkstraDistance(graph, edge_weights), averaging,
true, true);
}
/**
* Creates an instance with the specified graph and averaging behavior
* whose vertex distances are calculated on the unweighted graph.
*
* @param graph The graph on which the vertex scores are to be
* calculated.
* @param averaging Specifies whether the values returned is the sum of
* all v-distances or the mean v-distance.
* @param ignore_missing Specifies whether scores for missing distances
* are to ignore missing distances or be set to null.
* @param ignore_self_distances Specifies whether distances from a vertex
* to itself should be included in its score.
*/
public DistanceCentralityScorer(Hypergraph graph, boolean averaging,
boolean ignore_missing, boolean ignore_self_distances)
{
this(graph, new UnweightedShortestPath(graph), averaging,
ignore_missing, ignore_self_distances);
}
/**
* Equivalent to this(graph, averaging, true, true).
* @param graph The graph on which the vertex scores are to be
* calculated.
* @param averaging Specifies whether the values returned is the sum of
* all v-distances or the mean v-distance.
*/
public DistanceCentralityScorer(Hypergraph graph, boolean averaging)
{
this(graph, new UnweightedShortestPath(graph), averaging, true, true);
}
/**
* Calculates the score for the specified vertex. Returns {@code null} if
* there are missing distances and such are not ignored by this instance.
*/
public Double getVertexScore(V v)
{
Double value = output.get(v);
if (value != null)
{
if (value < 0)
return null;
return value;
}
Map v_distances = new HashMap(distance.getDistanceMap(v));
if (ignore_self_distances)
v_distances.remove(v);
// if we don't ignore missing distances and there aren't enough
// distances, output null (shortcut)
if (!ignore_missing)
{
int num_dests = graph.getVertexCount() -
(ignore_self_distances ? 1 : 0);
if (v_distances.size() != num_dests)
{
output.put(v, -1.0);
return null;
}
}
Double sum = 0.0;
for (V w : graph.getVertices())
{
if (w.equals(v) && ignore_self_distances)
continue;
Number w_distance = v_distances.get(w);
if (w_distance == null)
if (ignore_missing)
continue;
else
{
output.put(v, -1.0);
return null;
}
else
sum += w_distance.doubleValue();
}
value = sum;
if (averaging)
value /= v_distances.size();
double score = value == 0 ?
Double.POSITIVE_INFINITY :
1.0 / value;
output.put(v, score);
return score;
}
}