Package 'clusterLibreville'

Statistics of a given partition on a graph

Description

How well do these labels describe this graph, with the labels taken as fixed (an annotation, a clustering from another modality)? Every quantity is a closed form of the block edge-count matrix, one pass over the edges.

Usage

assess(graph, membership, check_symmetry = TRUE)

Arguments

graph	An undirected graph: a symmetric sparse matrix (e.g. an SNN graph's adjacency) or an igraph graph.
membership	Labels, one per vertex (any atomic type).
check_symmetry	Validate symmetry (FALSE for graphs symmetric by construction).

Details

• loglik: the degree-corrected SBM profile log-likelihood with the labels as blocks (Karrer & Newman 2011), the statistic of BESTest (Peel, Larremore & Clauset 2017), whose p-value is a permutation of the labels the caller runs.

• description_length: Peixoto's (2017) microcanonical DC-SBM description length with uniform priors, in nats, as graph-tool's BlockState.entropy(degree_dl_kind = "uniform"). It charges for the block matrix and the partition, so it ranks nested annotations: the shorter, the better the graph supports that level.

• significance: Traag, Krings & Van Dooren (2013), nats; leidenalg's SignificanceVertexPartition.quality().

• surprise: per label, -ln P(X >= inner edges) with X Poisson at the configuration-model expectation: the label's cohesion beyond chance (Lancichinetti, Radicchi & Ramasco 2010, edge-count form).

Exact on unweighted graphs; weights count as multiplicities.

Value

A list: loglik, description_length, significance (numbers); labels (the distinct labels, in order of first appearance) and, per label, surprise, size, degree_sum, inner_edges.

References

Peel, Larremore & Clauset (2017) Sci. Adv. 3:e1602548; Peixoto (2017) Phys. Rev. E 95:012317; Traag, Krings & Van Dooren (2013) Sci. Rep. 3:2930; Karrer & Newman (2011) Phys. Rev. E 83:016107; Lancichinetti, Radicchi & Ramasco (2010) Phys. Rev. E 81:046110.

Examples

f <- system.file("extdata", "hao3k.mtx", package = "clusterLibreville")
g <- Matrix::readMM(f)
a <- assess(g, leiden(g))
a$description_length

---

Pick the resolution by CHAMP (experimental)

Description

Experimental: the interface and the scores may change.

Usage

champ(
  graph,
  resolutions = 10^seq(-1, 1, length.out = 20),
  seeds = 0:4,
  gamma_range = NULL,
  n_iterations = -1L,
  theta = 0.01,
  min_gain = 0,
  threads = NULL,
  check_symmetry = TRUE,
  metric = c("nvi", "ami")
)

Arguments

graph	Undirected weighted graph: a symmetric sparse matrix or an igraph graph, as for leiden().
resolutions	Grid of resolutions (gamma), all > 0.
seeds	Seeds, non-negative whole numbers below 2^53.
gamma_range	The range the intervals cover; NULL: the span of resolutions.
n_iterations, theta, min_gain, threads, check_symmetry	Options of leiden(), for every run.
metric	"nvi" (default), normalised variation of information: a distance (0 = identical) and a metric, so steps along the domains add up, as in Markov stability. "ami", adjusted mutual information: a similarity (1 = identical), corrected for the chance agreement between partitions into many small communities.

Details

Runs leiden() at every pair of resolutions x seeds, then keeps the partitions that have the highest modularity among that pool somewhere in gamma_range, each with its interval of resolutions (CHAMP: Weir et al. 2017, https://doi.org/10.3390/a10030093). Modularity is linear in the resolution, so the intervals are exact; they are optimal relative to the pool, not globally. Each partition is also scored by its agreement with its neighbouring domains and with the other seeds, under metric. Deterministic, at any number of threads.

Value

A list: domains, a data frame with one row per partition on the envelope in increasing resolution (gamma_lo, gamma_hi, log_width, n_communities, and the grid point that produced it: resolution, seed; and the agreement under metric: to_prev with the previous row's partition, to_neighbours the mean with both neighbours' (close: a plateau; far: a boundary), to_seeds the mean with the other seeds' partitions at the same grid resolution (algorithmic noise); NA where there is nothing to compare with); labels, an integer matrix (vertices x domains, labels ⁠1..k⁠, community 1 the largest); and best, the row of domains with the widest interval in log resolution, e.g. labels[, best].

Examples

f <- system.file("extdata", "hao3k.mtx", package = "clusterLibreville")
g <- Matrix::readMM(f)
ch <- champ(g, 10^seq(-1, 1, length.out = 10), seeds = 0:2)
ch$domains
table(ch$labels[, ch$best])

---

Deterministic Leiden as an igraph community function

Description

leiden() with igraph's ⁠cluster_*()⁠ interface: it returns an igraph communities object, so it plugs into igraph and into bluster's graph clustering, e.g. bluster::clusterRows(pcs, SNNGraphParam(cluster.fun = cluster_libreville)).

Usage

cluster_libreville(graph, ...)

Arguments

graph	An undirected igraph graph (edge attribute weight if present).
...	Options of leiden(): resolution, seed, n_iterations, theta, min_gain, threads.

Value

An igraph communities object (igraph::membership(), igraph::modularity() and igraph::sizes() work on it).

Examples

g <- igraph::make_graph("Zachary")
comm <- cluster_libreville(g, seed = 1)
igraph::sizes(comm)

---

leiden() with the interface of Seurat's FindClusters

Description

A drop-in for Seurat::FindClusters on a graph, for tools built on it that accept another clustering function (e.g. a patched CHOIR: options(CHOIR.cluster_fun = clusterLibreville::find_clusters)); for those that do not, see with_libreville(). Takes the graph (a Seurat Graph, as obj@graphs$RNA_snn, or any symmetric sparse matrix), resolution (a vector gives one column each) and random.seed (the leiden() seed), and returns what FindClusters returns for a graph: a data frame with one factor column per resolution (⁠res.<r>⁠, labels ⁠1..k⁠, 1 the largest community), rows named by cell. As in Seurat, group.singletons (default TRUE) merges each one-cell community into the community it is best connected to (highest mean edge weight); Seurat breaks ties at random, here the larger community wins. Seurat's other options (algorithm, method, n.start, n.iter, ...) are accepted and ignored: the clustering is always this Leiden.

Usage

find_clusters(
  object,
  resolution = 0.8,
  random.seed = 0,
  group.singletons = TRUE,
  ...,
  threads = NULL
)

Arguments

object	A graph, as for leiden(); not a Seurat object.
resolution	Resolution(s) of the modularity (gamma).
random.seed	Seed, a non-negative whole number below 2^53.
group.singletons	Merge one-cell communities into their best-connected community.
...	Ignored (Seurat's options).
threads	Worker threads, as for leiden().

Value

A data frame, one factor column per resolution.

Examples

g <- Matrix::readMM(system.file("extdata", "hao3k.mtx", package = "clusterLibreville"))
cl <- find_clusters(g, resolution = c(0.5, 1), random.seed = 1)
sapply(cl, nlevels)

---

Deterministic Leiden community detection

Description

Leiden (Traag, Waltman & van Eck 2019) maximising modularity at resolution resolution, seeded and deterministic: the same seed gives the same labels at any number of threads.

Usage

leiden(x, ...)

## S4 method for signature 'ANY'
leiden(
  x,
  resolution = 1,
  seed = 0,
  n_iterations = -1L,
  theta = 0.01,
  min_gain = 0,
  threads = NULL,
  check_symmetry = TRUE,
  details = FALSE
)

## S4 method for signature 'SingleCellExperiment'
leiden(x, use.dimred = "PCA", k = 10L, type = "rank", details = FALSE, ...)

Arguments

x	A graph or a SingleCellExperiment. Graph: undirected and weighted, a symmetric sparse matrix (anything methods::as(x, "CsparseMatrix") accepts: a dgCMatrix, a Seurat Graph such as obj@graphs$RNA_snn, a symmetric dsCMatrix, a pattern matrix) or an igraph graph (edge attribute weight if present, e.g. from scran::buildSNNGraph() or bluster::makeSNNGraph()). SingleCellExperiment: the cells are clustered on a shared nearest neighbour graph of reducedDim(x, use.dimred), built by bluster::makeSNNGraph().
...	Arguments for the graph method (resolution, seed, ...).
resolution	Resolution of the modularity (gamma).
seed	Seed, a non-negative whole number below 2^53.
n_iterations	Leiden iterations; -1: until an iteration changes nothing.
theta	Randomness of the refinement.
min_gain	With n_iterations = -1, also stop once an iteration gains less modularity than this (0: strict).
threads	Worker threads; NULL: all cores. Does not change the result.
check_symmetry	Verify that the matrix is symmetric. FALSE skips only that check, for graphs symmetric by construction (Seurat, scanpy, bluster); bounds and weights are always validated.
details	Also return how the run ended (see Value).
use.dimred	Name of the reduced dimension to build the graph from.
k	Number of nearest neighbours for the SNN graph.
type	Edge weighting of the SNN graph, as in bluster::makeSNNGraph(): "rank", "number" or "jaccard".

Value

For a graph: integer community labels ⁠1..k⁠, community 1 the largest (ties: by smallest vertex), named by the graph's row names if it has them. For a SingleCellExperiment: the same labels as a factor named by cell, e.g. for colLabels(sce) <- leiden(sce). With details = TRUE, a list: labels (as above), iterations (Leiden iterations run), converged (whether the last iteration changed nothing: a fixed point), stop (why it stopped: "converged", "min_gain" or "n_iterations") and modularity.

See Also

cluster_libreville() for igraph and bluster.

Examples

f <- system.file("extdata", "hao3k.mtx", package = "clusterLibreville")
g <- Matrix::readMM(f)
labels <- leiden(g, resolution = 1, seed = 0)
table(labels)

sce <- SingleCellExperiment::SingleCellExperiment(
    assays = list(counts = matrix(0, 2, 200)),
    reducedDims = list(PCA = rbind(matrix(rnorm(400), ncol = 4),
                                   matrix(rnorm(400, 5), ncol = 4))))
SingleCellExperiment::colLabels(sce) <- leiden(sce, seed = 1)
table(SingleCellExperiment::colLabels(sce))

---

Modularity of a partition

Description

Newman's modularity at resolution resolution, summed in a fixed order (the quantity leiden() maximises).

Usage

modularity(graph, membership, resolution = 1)

Arguments

graph	Undirected weighted graph: a symmetric sparse matrix or an igraph graph, as for leiden().
membership	Labels, one per vertex (any atomic type).
resolution	Resolution of the modularity (gamma).

Value

A number.

Examples

f <- system.file("extdata", "hao3k.mtx", package = "clusterLibreville")
g <- Matrix::readMM(f)
modularity(g, leiden(g))

---

neoSBM: how many vertices leave an annotation when leaving gets cheaper

Description

Peel, Larremore & Clauset's (2017) neoSBM: every vertex keeps its label's block or is free to sit in any block, at a prior cost of log((1 - theta) / theta) nats of degree-corrected SBM likelihood. Sweeping theta towards 1/2 traces the fraction of vertices that defect from the annotation; at theta = 1/2 the prior is neutral and that fraction is "vertices whose label is not locally optimal for this graph". Greedy single-vertex moves with exact likelihood deltas, warm-started along thetas; a maximiser of the published objective, not Peel's reference code.

Usage

neosbm(
  graph,
  membership,
  thetas = c(1e-06, 1e-05, 1e-04, 0.001, 0.003, 0.01, 0.03, 0.1, 0.2, 0.3, 0.4, 0.5),
  max_sweeps = 20L,
  seed = 0L,
  check_symmetry = TRUE
)

Arguments

graph	An undirected graph: a symmetric sparse matrix (e.g. an SNN graph's adjacency) or an igraph graph.
membership	Labels, one per vertex (any atomic type).
thetas	The grid, in (0, 1), ascending.
max_sweeps	Sweeps per theta before giving up on convergence.
seed	Fixes the vertex order of the sweeps; NULL sweeps in vertex order (the deterministic choice for cross-checks).
check_symmetry	Validate symmetry (FALSE for graphs symmetric by construction).

Value

A list: thetas; per theta defect (fraction off their label), loglik_gain (nats recovered) and sweeps; blocks (the block of every vertex at the last theta, as indices into labels); labels.

Examples

f <- system.file("extdata", "hao3k.mtx", package = "clusterLibreville")
g <- Matrix::readMM(f)
r <- neosbm(g, leiden(g))
r$defect

---

Run code with Seurat's FindClusters replaced by find_clusters()

Description

Evaluates expr with Seurat::FindClusters swapped for find_clusters() and restores it afterwards (also on error). For tools that cluster through Seurat::FindClusters and have no option to choose the clustering function, such as CHOIR: with_libreville(CHOIR::CHOIR(obj)) makes every clustering in its tree deterministic Leiden, seeded with CHOIR's random_seed.

Usage

with_libreville(expr, threads = NULL)

Arguments

expr	Code to run.
threads	Worker threads for every clustering, as for leiden().

Details

The function is replaced in Seurat's namespace, for the whole R session, while expr runs.

Value

The value of expr.

Examples

g <- Matrix::readMM(system.file("extdata", "hao3k.mtx", package = "clusterLibreville"))
cl <- with_libreville(Seurat::FindClusters(g, resolution = 1, random.seed = 1))
table(cl$res.1)

---