stag.cluster Namespace Reference

Functions
List[int]	spectral_cluster (graph.Graph g, int k)
	Spectral clustering algorithm.
List[int]	local_cluster (graph.LocalGraph g, int seed_vertex, float target_volume)
	Local clustering algorithm based on personalised Pagerank.
List[int]	local_cluster_acl (graph.LocalGraph g, int seed_vertex, float locality, float error=0.001)
	The ACL local clustering algorithm.
Tuple[scipy.sparse.csc_matrix, scipy.sparse.csc_matrix]	approximate_pagerank (graph.LocalGraph g, scipy.sparse.csc_matrix seed_vector, float alpha, float epsilon)
	Compute the approximate pagerank vector.
List[int]	sweep_set_conductance (graph.LocalGraph g, scipy.sparse.csc_matrix v)
	Find the sweep set of the given vector with the minimum conductance.
float	adjusted_rand_index (List[int] gt_labels, List[int] labels)
	Compute the Adjusted Rand Index between two label vectors.
float	conductance (graph.LocalGraph g, List[int] cluster)
	Compute the conductance of the given cluster in a graph.

Function Documentation

spectral_cluster()

List[int] stag.cluster.spectral_cluster	(	graph.Graph	g,
		int	k
	)

Spectral clustering algorithm.

This is a simple graph clustering method, which provides a clustering of the entire graph. To use spectral clustering, simply pass a stag.graph.Graph object and the number of clusters you would like to find.

import stag.graph
import stag.cluster
 
myGraph = stag.graph.Graph.barbell_graph(10)
labels = stag.cluster.spectral_cluster(myGraph, 2)
print(labels)

The spectral clustering algorithm has the following steps.

• Compute the \(k\) smallest eigenvectors of the normalised Laplacian matrix.
• Embed the vertices into \(\mathbb{R}^k\) according to the eigenvectors.
• Cluster the vertices into \(k\) clusters using a \(k\)-means clustering algorithm.

Parameters

g	the graph object to be clustered
k	the number of clusters to find. Should be less than \(n/2\).

Returns

a list of ints giving the cluster membership for each vertex in the graph

References

A. Ng, M. Jordan, Y. Weiss. On spectral clustering: Analysis and an algorithm. NeurIPS'01

local_cluster()

List[int] stag.cluster.local_cluster	(	graph.LocalGraph	g,
		int	seed_vertex,
		float	target_volume
	)

Local clustering algorithm based on personalised Pagerank.

Given a graph and starting vertex, return a cluster which is close to the starting vertex.

This method uses the ACL local clustering algorithm.

Parameters

g	a graph object implementing the LocalGraph interface
seed_vertex	the starting vertex in the graph
target_volume	the approximate volume of the cluster you would like to find

Returns

a vector containing the indices of vectors considered to be in the same cluster as the seed_vertex.

References

R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. FOCS'06

local_cluster_acl()

List[int] stag.cluster.local_cluster_acl	(	graph.LocalGraph	g,
		int	seed_vertex,
		float	locality,
		float	error = 0.001
	)

The ACL local clustering algorithm.

Given a graph and starting vertex, returns a cluster close to the starting vertex, constructed in a local way.

The locality parameter is passed as the alpha parameter in the personalised pagerank calculation.

Parameters

g	a graph object implementing the LocalGraph interface
seed_vertex	the starting vertex in the graph
locality	a value in \([0, 1]\) indicating how 'local' the cluster should be. A value of \(1\) will return the return only the seed vertex and a value of \(0\) will explore the whole graph.
error	(optional) - the acceptable error in the calculation of the approximate pagerank. Default \(0.001\).

Returns

a vector containing the indices of vectors considered to be in the same cluster as the seed_vertex.

References

R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. FOCS'06

approximate_pagerank()

Tuple[scipy.sparse.csc_matrix, scipy.sparse.csc_matrix] stag.cluster.approximate_pagerank	(	graph.LocalGraph	g,
		scipy.sparse.csc_matrix	seed_vector,
		float	alpha,
		float	epsilon
	)

Compute the approximate pagerank vector.

The parameters s, alpha, and epsilon are used as described in the ACL paper.

Note that the dimension of the returned vectors may not match the true number of vertices in the graph provided since the approximate pagerank is computed locally.

Parameters

g	a stag.graph.LocalGraph object
seed_vector	the seed vector of the personalised pagerank
alpha	the locality parameter of the personalised pagerank
epsilon	the error parameter of the personalised pagerank

Returns

A tuple of sparse column vectors corresponding to

• p: the approximate pagerank vector
• r: the residual vector

By the definition of approximate pagerank, it is the case that p + ppr(r, alpha) = ppr(s, alpha).

Exceptions

argument_error

if the provided seed_vector is not a column vector.

References

R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. FOCS'06

sweep_set_conductance()

List[int] stag.cluster.sweep_set_conductance	(	graph.LocalGraph	g,
		scipy.sparse.csc_matrix	v
	)

Find the sweep set of the given vector with the minimum conductance.

First, sort the vector such that \(v_1, \ldots, v_n\). Then let

\[ S_i = \{v_j : j <= i\} \]

and return the set of original indices corresponding to

\[ \mathrm{argmin}_i \phi(S_i) \]

where \(\phi(S)\) is the conductance of \(S\).

This method is expected to be run on vectors whose support is much less than the total size of the graph. If the total volume of the support of vec is larger than half of the volume of the total graph, then this method may return unexpected results.

Note that the caller is responsible for any required normalisation of the input vector. In particular, this method does not normalise the vector by the node degrees.

Parameters

g	a stag.graph.LocalGraph object
v	the vector to sweep over

Returns

a vector containing the indices of vec which give the minimum conductance in the given graph

adjusted_rand_index()

float stag.cluster.adjusted_rand_index	(	List[int]	gt_labels,
		List[int]	labels
	)

Compute the Adjusted Rand Index between two label vectors.

Parameters

gt_labels	the ground truth labels for the dataset
labels	the candidate labels whose ARI should be calculated

Returns

the ARI between the two labels vectors

References

W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association. 66 (336): 846–850. 1971.

conductance()

float stag.cluster.conductance	(	graph.LocalGraph	g,
		List[int]	cluster
	)

Compute the conductance of the given cluster in a graph.

Given a graph \(G = (V, E)\), the conductance of \(S \subseteq V\) is defined to be

\[ \phi(S) = \frac{w(S, V \setminus S)}{\mathrm{vol}(S)}, \]

where \(\mathrm{vol}(S) = \sum_{v \in S} \mathrm{deg}(v)\) is the volume of \(S\) and \(w(S, V \setminus S)\) is the total weight of edges crossing the cut between \(S\) and \(V \setminus S\).

Parameters

g	a stag.graph.LocalGraph object representing \(G\).
cluster	a list of node IDs in \(S\).

Returns

the conductance \(\phi_G(S)\).