it.unimi.dsi.law.graph
Class LayeredLabelPropagation

java.lang.Object
   it.unimi.dsi.law.graph.LayeredLabelPropagation

public class LayeredLabelPropagation
extends Object

An 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.

The method computePermutation(double[], String, int) returns a permutation of the original symmetric graph provided with the constructor which will (hopefully) increase locality (see the paper). Usually, the permutation is fed to Transform.mapOffline(ImmutableGraph, int[], int, File, ProgressLogger) to permute the original graph.

Note that the graph provided must be symmetric and loopless. If this is not the case, please use Transform.symmetrizeOffline(ImmutableGraph, int, File, ProgressLogger) and possibly Transform.filterArcs(ImmutableGraph, it.unimi.dsi.webgraph.Transform.ArcFilter, ProgressLogger) with filter Transform.NO_LOOPS to generate a suitable graph.

This class can also be used to run just label propagation over a given graph to get the labels assigned to the nodes for a fixed γ.

Memory requirements

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

Note that the main method will warm up the algorithm by performing a depth-first visit if the graph is not mapped. The visit will require storing an additional array of integers.

Author:

Paolo Boldi, Marco Rosa, Massimo Santini, Sebastiano Vigna

MAX_UPDATES

public static final int MAX_UPDATES

The default maximum number of updates.

See Also:

Constant Field Values

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,
                               int[] 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,
                               int[] 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

labelBasename

public void labelBasename(String labelBasename)

Sets the basename for label files.

Parameters:

labelBasename - basename for label files.

computeLabels

public AtomicIntegerArray 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 AtomicIntegerArray 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 int[] 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 int[] 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

SEARCH:

Related searches:
public string double number method

gipoco.com is neither affiliated with the authors of this page or responsible
for its contents. This is a safe-cache copy of the original web site.

gipoco.com is neither affiliated with the authors of this page nor responsible for its contents. This is a safe-cache copy of the original web site.