Package it.unimi.dsi.law.big.graph

Class LayeredLabelPropagation

java.lang.Object

it.unimi.dsi.law.big.graph.LayeredLabelPropagation

public class LayeredLabelPropagation
extends Object

A big implementation of the layered label propagation algorithm described by by Paolo Boldi, Sebastiano Vigna, Marco Rosa, Massimo Santini, and Sebastiano Vigna in “Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks”, Proceedings of the 20th international conference on World Wide Web, pages 587−596, ACM, 2011.

This implementation uses big arrays to provide support for big graphs (i.e., with more than 2³¹ nodes). For the rest, it is functionally identical to LayeredLabelPropagation. However, it supports outdegrees smaller than 2³¹, only.

Memory requirements

This class requires 25 bytes per node (three longs and a boolean), plus the memory that is necessary to load the graph, which however can be just memory-mapped.

Author:

Paolo Boldi, Marco Rosa, Massimo Santini, Sebastiano Vigna

See Also:

LayeredLabelPropagation

Field Summary

Fields

Modifier and Type	Field	Description
protected EliasFanoCumulativeOutdegreeList	cumulativeOutdegrees	The outdegrees cumulative function.
static double[]	DEFAULT_GAMMAS	The list of default γ values.
static int	MAX_UPDATES	The default maximum number of updates.
protected long	nextArcs	The number of arcs before nextNode.
protected long	nextNode	The starting node of the next chunk of nodes to be processed.

Constructor Summary

Constructors

Constructor	Description
LayeredLabelPropagation(ImmutableGraph symGraph, long seed)	Creates a new instance.
LayeredLabelPropagation(ImmutableGraph symGraph, long[][] startPerm, int numberOfThreads, long seed, boolean exact)	Creates a new instance using a specific initial permutation and specified number of threads.
LayeredLabelPropagation(ImmutableGraph symGraph, long[][] startPerm, long seed)	Creates a new instance using a specific initial permutation.
LayeredLabelPropagation(ImmutableGraph symGraph, long[][] startPerm, long seed, boolean exact)	Creates a new instance using a specific initial permutation.

Method Summary

Modifier and Type	Method	Description
AtomicLongArray[]	computeLabels(double gamma)	Computes the labels of a graph for a given value of γ using the default maximum number of updates.
AtomicLongArray[]	computeLabels(double gamma, int maxUpdates)	Computes the labels of a graph for a given value of γ.
long[][]	computePermutation(double[] gammas, String cluster)	Computes the final permutation of the graph using the default maximum number of updates.
long[][]	computePermutation(double[] gammas, String cluster, int maxUpdates)	Computes the final permutation of the graph.
long[][]	computePermutation(String cluster)	Computes the final permutation of the graph using the default maximum number of updates and the default gammas.
void	labelBasename(String labelBasename)	Sets the basename for label files.
static void	main(String[] args)

Methods inherited from class java.lang.Object

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

Field Details

DEFAULT_GAMMAS

public static final double[] DEFAULT_GAMMAS

The list of default γ values. It must be kept in sync with the main(String[]) default parameters.

MAX_UPDATES

public static final int MAX_UPDATES

The default maximum number of updates.

See Also:

Constant Field Values

nextNode

protected long nextNode

The starting node of the next chunk of nodes to be processed.

nextArcs

protected long nextArcs

The number of arcs before nextNode.

cumulativeOutdegrees

protected final EliasFanoCumulativeOutdegreeList cumulativeOutdegrees

The outdegrees cumulative function.

Constructor Details

LayeredLabelPropagation

public LayeredLabelPropagation(ImmutableGraph symGraph,
long seed)
                        throws IOException

Creates a new instance.

Parameters:

symGraph - a symmetric, loopless graph.

seed - a random seed.

Throws:

IOException

LayeredLabelPropagation

public LayeredLabelPropagation(ImmutableGraph symGraph,
long[][] startPerm,
long seed)
                        throws IOException

Creates a new instance using a specific initial permutation.

Parameters:

symGraph - a symmetric, loopless graph.

startPerm - an initial permutation of the graph, or null for no permutation.

seed - a random seed.

Throws:

IOException

LayeredLabelPropagation

public LayeredLabelPropagation(ImmutableGraph symGraph,
long[][] startPerm,
long seed,
boolean exact)
                        throws IOException

Creates a new instance using a specific initial permutation.

If exact is true, the final permutation is exactly the same as if you first permute the graph with startPerm and then apply LLP with an null starting permutation.

Parameters:

symGraph - a symmetric, loopless graph.

startPerm - an initial permutation of the graph, or null for no permutation.

seed - a random seed.

exact - a boolean flag that forces the algorithm to run exactly.

Throws:

IOException

LayeredLabelPropagation

public LayeredLabelPropagation(ImmutableGraph symGraph,
long[][] startPerm,
int numberOfThreads,
long seed,
boolean exact)
                        throws IOException

Creates a new instance using a specific initial permutation and specified number of threads.

If exact is true, the final permutation is exactly the same as if you first permute the graph with startPerm and then apply LLP with an null starting permutation.

Parameters:

symGraph - a symmetric, loopless graph.

startPerm - an initial permutation of the graph, or null for no permutation.

numberOfThreads - the number of threads to be used (0 for automatic sizing).

seed - a random seed.

exact - a boolean flag that forces the algorithm to run exactly.

Throws:

IOException

Method Details

labelBasename

public void labelBasename(String labelBasename)

Sets the basename for label files.

Parameters:

labelBasename - basename for label files.

computeLabels

public AtomicLongArray[] computeLabels(double gamma)

Computes the labels of a graph for a given value of γ using the default maximum number of updates.

Parameters:

gamma - the gamma parameter.

Returns:

the labels.

computeLabels

public AtomicLongArray[] computeLabels(double gamma,
int maxUpdates)

Computes the labels of a graph for a given value of γ.

Parameters:

gamma - the gamma parameter.

maxUpdates - the maximum number of updates performed.

Returns:

the labels.

computePermutation

public long[][] computePermutation(String cluster)
                            throws IOException

Computes the final permutation of the graph using the default maximum number of updates and the default gammas.

Parameters:

cluster - if not null, clusters will be saved to a file with this name.

Returns:

the final permutation of the graph.

Throws:

IOException

computePermutation

public long[][] computePermutation(double[] gammas,
String cluster)
                            throws IOException

Computes the final permutation of the graph using the default maximum number of updates.

Parameters:

gammas - a set of parameters that will be used to generate labellings.

cluster - if not null, clusters will be saved to a file with this name.

Returns:

the final permutation of the graph.

Throws:

IOException

computePermutation

public long[][] computePermutation(double[] gammas,
String cluster,
int maxUpdates)
                            throws IOException

Computes the final permutation of the graph.

Parameters:

gammas - a set of parameters that will be used to generate labellings.

cluster - if not null, clusters will be saved to a file with this name.

maxUpdates - the maximum number of updates performed.

Returns:

the final permutation of the graph.

Throws:

IOException

main

public static void main(String[] args)
                 throws IOException,
JSAPException

Throws:

IOException

JSAPException