Class NeighbourhoodFunction
public class NeighbourhoodFunction extends Object
Note that performing all breadthfirst visits requires time O(nm), so this class is usable only on very small graphs.
Additionally, this class provides several useful static methods such as distanceCumulativeDistributionFunction(double[])
,
distanceProbabilityMassFunction(double[])
, averageDistance(double[])
, medianDistance(int, double[])
and spid(double[])
that act on neighbourhood functions.
Performance issues
This class uses an instance of ParallelBreadthFirstVisit
to ensure a high degree of parallelism (see its
documentation for memory requirements). Note that if the graph is small a large number of thread will slow down the computation because of synchronization costs.
 Author:
 Paolo Boldi, Sebastiano Vigna

Constructor Summary
Constructors Constructor Description NeighbourhoodFunction()

Method Summary
Modifier and Type Method Description static double
averageDistance(double[] neighbourhoodFunction)
Returns the average of the distances between reachable pairs of nodes.static double[]
compute(ImmutableGraph g)
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.static double[]
compute(ImmutableGraph g, int threads, ProgressLogger pl)
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.static double[]
compute(ImmutableGraph g, ProgressLogger pl)
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.static long[]
computeExact(ImmutableGraph g, int threads, ProgressLogger pl)
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.static double[]
distanceCumulativeDistributionFunction(double[] neighbourhoodFunction)
Returns the distance cumulative distribution function.static double[]
distanceProbabilityMassFunction(double[] neighbourhoodFunction)
Returns the probability mass function of the distance distribution.static double
effectiveDiameter(double[] neighbourhoodFunction)
Returns the effective diameter at 0.9.static double
effectiveDiameter(double alpha, double[] neighbourhoodFunction)
Returns the effective diameter at a specified fraction.static double
harmonicDiameter(double[] neighbourhoodFunction)
Returns the harmonic diameter, that is, the harmonic mean of all distances.static double
harmonicDiameter(int n, double[] neighbourhoodFunction)
Returns the harmonic diameter, that is, the harmonic mean of all distances.static void
main(String[] arg)
static double
medianDistance(double[] neighbourhoodFunction)
Returns the median of distances between all pairs of nodes.static double
medianDistance(int n, double[] neighbourhoodFunction)
Returns the median of distances between all pairs of nodes.static double
spid(double[] neighbourhoodFunction)
Returns the spid (shortestpaths index of dispersion).

Constructor Details

NeighbourhoodFunction
public NeighbourhoodFunction()


Method Details

compute
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.This method returns an array of doubles. When some values of the function are near 2^{63}, it might lose some leastsignificant digits. If you need exact values, use
computeExact(ImmutableGraph, int, ProgressLogger)
instead. Parameters:
g
 a graph. Returns:
 the neighbourhood function of the specified graph.

compute
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.This method returns an array of doubles. When some values of the function are near 2^{63}, it might lose some leastsignificant digits. If you need exact values, use
computeExact(ImmutableGraph, int, ProgressLogger)
instead. Parameters:
g
 a graph.pl
 a progress logger, ornull
. Returns:
 the neighbourhood function of the specified graph.

compute
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.This method returns an array of doubles. When some values of the function are near 2^{63}, it might lose some leastsignificant digits. If you need exact values, use
computeExact(ImmutableGraph, int, ProgressLogger)
instead. Parameters:
g
 a graph.threads
 the requested number of threads (0 forRuntime.availableProcessors()
). Note that if the graph is small a large number of thread will slow down the computation because of synchronization costs.pl
 a progress logger, ornull
. Returns:
 the neighbourhood function of the specified graph.

computeExact
Computes and returns the neighbourhood function of the specified graph by multiple breadthfirst visits.This method returns an array of longs. When some values of the function are near 2^{63}, it provides an exact value, as opposed to
compute(ImmutableGraph, int, ProgressLogger)
. Parameters:
g
 a graph.threads
 the requested number of threads (0 forRuntime.availableProcessors()
). Note that if the graph is small a large number of thread will slow down the computation because of synchronization costs.pl
 a progress logger, ornull
. Returns:
 the neighbourhood function of the specified graph as an array of longs.

distanceCumulativeDistributionFunction
public static double[] distanceCumulativeDistributionFunction(double[] neighbourhoodFunction)Returns the distance cumulative distribution function. Parameters:
neighbourhoodFunction
 a neighbourhood function or distance cumulative distribution function. Returns:
 the distance cumulative distribution function.

distanceProbabilityMassFunction
public static double[] distanceProbabilityMassFunction(double[] neighbourhoodFunction)Returns the probability mass function of the distance distribution. Parameters:
neighbourhoodFunction
 a neighbourhood function or distance cumulative distribution function. Returns:
 the probability mass function of the distance distribution.

effectiveDiameter
public static double effectiveDiameter(double alpha, double[] neighbourhoodFunction)Returns the effective diameter at a specified fraction. Parameters:
alpha
 the desired fraction of reachable pairs of nodes (usually, 0.9).neighbourhoodFunction
 a neighbourhood function or distance cumulative distribution function. Returns:
 the effective diameter at
fraction
.

effectiveDiameter
public static double effectiveDiameter(double[] neighbourhoodFunction)Returns the effective diameter at 0.9. Parameters:
neighbourhoodFunction
 a neighbourhood function (or distance cumulative distribution function). Returns:
 the effective diameter at 0.9.

medianDistance
public static double medianDistance(double[] neighbourhoodFunction)Returns the median of distances between all pairs of nodes. Parameters:
neighbourhoodFunction
 a neighbourhood function. Returns:
 the median distance, which might be
Double.POSITIVE_INFINITY
if less than half of the pairs of nodes are reachable.

medianDistance
public static double medianDistance(int n, double[] neighbourhoodFunction)Returns the median of distances between all pairs of nodes.Note that if you have an actual neighbourhood function, you can safely pass its first value as first argument; however, having the number of nodes as a separate input makes it possible passing this method a distance cumulative distribution function, too.
 Parameters:
n
 the number of nodes in the graph.neighbourhoodFunction
 a neighbourhood function (or distance cumulative distribution function). Returns:
 the median distance, which might be
Double.POSITIVE_INFINITY
if less than half of the pairs of nodes are reachable.

spid
public static double spid(double[] neighbourhoodFunction)Returns the spid (shortestpaths index of dispersion). Parameters:
neighbourhoodFunction
 a neighbourhood function (or distance cumulative distribution function). Returns:
 the spid.

averageDistance
public static double averageDistance(double[] neighbourhoodFunction)Returns the average of the distances between reachable pairs of nodes. Parameters:
neighbourhoodFunction
 a neighbourhood function (or distance cumulative distribution function). Returns:
 the average of the distances between reachable pairs of nodes.

harmonicDiameter
public static double harmonicDiameter(double[] neighbourhoodFunction)Returns the harmonic diameter, that is, the harmonic mean of all distances. Parameters:
neighbourhoodFunction
 a neighbourhood function. Returns:
 the harmonic diameter.

harmonicDiameter
public static double harmonicDiameter(int n, double[] neighbourhoodFunction)Returns the harmonic diameter, that is, the harmonic mean of all distances.Note that if you have an actual neighbourhood function, you can safely pass its first value as first argument; however, having the number of nodes as a separate input makes it possible passing this method a distance cumulative distribution function, too.
 Parameters:
n
 the number of nodes in the graph.neighbourhoodFunction
 a neighbourhood function (or distance cumulative distribution function). Returns:
 the harmonic diameter.

main
 Throws:
IOException
JSAPException
