Module llp

Layered label propagation.

An implementation of the layered label propagation algorithm described 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 function layered_label_propagation returns a permutation of the provided symmetric graph which will (hopefully) increase locality (see the paper). Usually, the permutation is fed to permute to permute the original graph.

Note that the graph provided should be symmetric and loopless. If this is not the case, please use simplify to generate a suitable graph.

Memory requirements

LLP requires three usize and a boolean per node, plus the memory that is necessary to load the graph.

Modules

preds

Predicates implementing stopping conditions.

Structs

LabelsStore

This struct is how the labels and their metadata are stored on disk.

Functions

combine_labels

Combines the labels computed by LLP into a final labels array.

invert_permutation

Inverts a permutation.

labels_to_ranks

Computes the ranks of a slice of labels by their natural order.

layered_label_propagation

Runs layered label propagation on the provided symmetric graph and returns the resulting labels.

layered_label_propagation_labels_only

Computes and store on disk the labels for the given gammas, but does not combine them. For the arguments look at layered_label_propagation.