edu.uci.ics.jung.statistics
Class GraphStatistics

java.lang.Object
  edu.uci.ics.jung.statistics.GraphStatistics

public class GraphStatistics
extends Object

A set of statistical measures for structural properties of a graph.

Author:

Scott White, Joshua O'Madadhain

Constructor Summary

GraphStatistics()

Method Summary

static Map	averageDistances(ArchetypeGraph g) For each vertex v in g, calculates the average shortest path length from v to all other vertices in g, ignoring edge weights.
static Map	averageDistances(ArchetypeGraph graph, Distance d) For each vertex v in graph, calculates the average shortest path length from v to all other vertices in graph using the metric specified by d, and returns the results in a Map from vertices to Double values.
static Map	clusteringCoefficients(ArchetypeGraph graph) Returns a Map of vertices to their clustering coefficients.
static Histogram	createHistogram(DoubleArrayList values, double min, int numBins, double binWidth) Creates a histogram from a sequence of doubles
static double	diameter(ArchetypeGraph g) Returns the diameter of g, ignoring edge weights.
static double	diameter(ArchetypeGraph g, Distance d) Returns the diameter of g using the metric specified by d.
static double	diameter(ArchetypeGraph g, Distance d, boolean use_max) Returns the diameter of g using the metric specified by d.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphStatistics

public GraphStatistics()

Method Detail

clusteringCoefficients

public static Map clusteringCoefficients(ArchetypeGraph graph)

Returns a Map of vertices to their clustering coefficients. The clustering coefficient cc(v) of a vertex v is defined as follows:

• degree(v) == 0: 0
• degree(v) == 1: 1
• degree(v) == n, n > 1: given S, the set of neighbors of v: cc(v) = (the sum over all w in S of the number of other elements of w that are neighbors of w) / ((|S| * (|S| - 1) / 2). Less formally, the fraction of v's neighbors that are also neighbors of each other.

  Note: This algorithm treats its argument as an undirected graph; edge direction is ignored.

  Parameters:

  graph -

averageDistances

public static Map averageDistances(ArchetypeGraph graph,
                                   Distance d)

For each vertex v in graph, calculates the average shortest path length from v to all other vertices in graph using the metric specified by d, and returns the results in a Map from vertices to Double values. If there exists an ordered pair <u,v> for which d.getDistance(u,v) returns null, then the average distance value for u will be stored as Double.POSITIVE_INFINITY).

To calculate the average distances, ignoring edge weights if any:

 Map distances = GraphStatistics.averageDistances(g, new UnweightedShortestPath(g));
 

To calculate the average distances respecting edge weights:

 DijkstraShortestPath dsp = new DijkstraShortestPath(g, nev);
 Map distances = GraphStatistics.averageDistances(g, dsp);
 

where nev is an instance of NumberEdgeValue that is used to fetch the weight for each edge.

See Also:

UnweightedShortestPath, DijkstraDistance

averageDistances

public static Map averageDistances(ArchetypeGraph g)

For each vertex v in g, calculates the average shortest path length from v to all other vertices in g, ignoring edge weights.

See Also:

diameter(ArchetypeGraph, Distance)

diameter

public static double diameter(ArchetypeGraph g,
                              Distance d,
                              boolean use_max)

Returns the diameter of g using the metric specified by d. The diameter is defined to be the maximum, over all pairs of vertices u,v, of the length of the shortest path from u to v. If the graph is disconnected (that is, not all pairs of vertices are reachable from one another), the value returned will depend on use_max: if use_max == true, the value returned will be the the maximum shortest path length over all pairs of connected vertices; otherwise it will be Double.POSITIVE_INFINITY.

diameter

public static double diameter(ArchetypeGraph g,
                              Distance d)

Returns the diameter of g using the metric specified by d. The diameter is defined to be the maximum, over all pairs of vertices u,v, of the length of the shortest path from u to v, or Double.POSITIVE_INFINITY if any of these distances do not exist.

See Also:

diameter(ArchetypeGraph, Distance, boolean)

diameter

public static double diameter(ArchetypeGraph g)

Returns the diameter of g, ignoring edge weights.

See Also:

diameter(ArchetypeGraph, Distance, boolean)

createHistogram

public static Histogram createHistogram(DoubleArrayList values,
                                        double min,
                                        int numBins,
                                        double binWidth)

Creates a histogram from a sequence of doubles

Parameters:

values - the sequence of doubles

min - the minimum value to bin off of

numBins - the number of bins

binWidth - the width of the bin

Returns:

a histogram