Package 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

  • 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 int 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, 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

    • LayeredLabelPropagation

      public LayeredLabelPropagation​(ImmutableGraph symGraph, int[] 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 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​(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 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