Class NeighbourhoodFunction
Note that performing all breadth-first 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 -
Method Summary
Modifier and TypeMethodDescriptionstatic doubleaverageDistance(double[] neighbourhoodFunction) Returns the average of the distances between reachable pairs of nodes.static double[]Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.static double[]compute(ImmutableGraph g, int threads, it.unimi.dsi.logging.ProgressLogger pl) Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.static double[]compute(ImmutableGraph g, it.unimi.dsi.logging.ProgressLogger pl) Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.static long[]computeExact(ImmutableGraph g, int threads, it.unimi.dsi.logging.ProgressLogger pl) Computes and returns the neighbourhood function of the specified graph by multiple breadth-first 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 doubleeffectiveDiameter(double[] neighbourhoodFunction) Returns the effective diameter at 0.9.static doubleeffectiveDiameter(double alpha, double[] neighbourhoodFunction) Returns the effective diameter at a specified fraction.static doubleharmonicDiameter(double[] neighbourhoodFunction) Returns the harmonic diameter, that is, the harmonic mean of all distances.static doubleharmonicDiameter(int n, double[] neighbourhoodFunction) Returns the harmonic diameter, that is, the harmonic mean of all distances.static voidstatic doublemedianDistance(double[] neighbourhoodFunction) Returns the median of distances between all pairs of nodes.static doublemedianDistance(int n, double[] neighbourhoodFunction) Returns the median of distances between all pairs of nodes.static doublespid(double[] neighbourhoodFunction) Returns the spid (shortest-paths index of dispersion).
-
Constructor Details
-
NeighbourhoodFunction
public NeighbourhoodFunction()
-
-
Method Details
-
compute
Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.This method returns an array of doubles. When some values of the function are near 263, it might lose some least-significant 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 breadth-first visits.This method returns an array of doubles. When some values of the function are near 263, it might lose some least-significant 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
public static double[] compute(ImmutableGraph g, int threads, it.unimi.dsi.logging.ProgressLogger pl) Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.This method returns an array of doubles. When some values of the function are near 263, it might lose some least-significant 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
public static long[] computeExact(ImmutableGraph g, int threads, it.unimi.dsi.logging.ProgressLogger pl) Computes and returns the neighbourhood function of the specified graph by multiple breadth-first visits.This method returns an array of longs. When some values of the function are near 263, 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_INFINITYif 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_INFINITYif less than half of the pairs of nodes are reachable.
-
spid
public static double spid(double[] neighbourhoodFunction) Returns the spid (shortest-paths 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:
IOExceptioncom.martiansoftware.jsap.JSAPException
-