/*
 * Created on Jul 10, 2007
 *
 * Copyright (c) 2007, The JUNG Authors 
 *
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * https://github.com/jrtom/jung/blob/master/LICENSE for a description.
 */
package edu.uci.ics.jung.algorithms.scoring;

import java.util.HashMap;
import java.util.Map;

import com.google.common.base.Function;

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, 
            Function 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, 
            Function 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;
	}
}

 

Ads help maintain this website.