 |
STAG C++
2.0.0
Spectral Toolkit of Algorithms for Graphs
|
|
STAG C++
2.0.0
Spectral Toolkit of Algorithms for Graphs
|
Algorithms for finding clusters in graphs.
The methods in this module can be divided into three sub-categories.
| std::vector< StagInt > stag::spectral_cluster | ( | stag::Graph * | graph, |
| StagInt | 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 object and the number of clusters you would like to find.
The spectral clustering algorithm has the following steps.
| graph | the graph object to be clustered |
| k | the number of clusters to find. Should be less than \(n/2\). |
| std::vector< StagInt > stag::cheeger_cut | ( | stag::Graph * | graph | ) |
Find the Cheeger cut in a graph.
Let \(G = (V, E)\) be a graph and \(\mathcal{L}\) be its normalised Laplacian matrix with eigenvalues \(0 = \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n\). Then, Cheeger's inequality states that
\[ \frac{\lambda_2}{2} \leq \Phi_G \leq \sqrt{2 \lambda_2}, \]
where
\[ \Phi_G = \min_{S \subset V} \phi(S) \]
is the conductance of \(G\). The proof of Cheeger's inequality is constructive: by computing the eigenvector corresponding to \(\lambda_2\), and performing the sweep set operation, we are able to find a set \(S\) with conductance close to the optimal. The partition returned by this algorithm is called the 'Cheeger cut' of the graph.
| graph | the graph object to be partitioned |
| std::vector< StagInt > stag::local_cluster | ( | stag::LocalGraph * | graph, |
| StagInt | seed_vertex, | ||
| double | 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.
| graph | 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 |
| std::vector< StagInt > stag::local_cluster_acl | ( | stag::LocalGraph * | graph, |
| StagInt | seed_vertex, | ||
| double | locality, | ||
| double | error | ||
| ) |
The ACL local clustering algorithm. Given a graph and starting vertex, return 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.
| graph | 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 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\). |
| std::vector< StagInt > stag::local_cluster_acl | ( | stag::LocalGraph * | graph, |
| StagInt | seed_vertex, | ||
| double | locality | ||
| ) |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| std::tuple< SprsMat, SprsMat > stag::approximate_pagerank | ( | stag::LocalGraph * | graph, |
| SprsMat & | seed_vector, | ||
| double | alpha, | ||
| double | epsilon | ||
| ) |
Compute the approximate Pagerank vector.
The parameters seed_vector, alpha, and epsilon are used as described in the ACL paper.
Note that the dimension of the returned vectors may not match the correct number of vertices in the graph provided since the approximate Pagerank is computed locally.
| graph | a stag::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 |
By the definition of approximate Pagerank, it holds that p + ppr(r, alpha) = ppr(s, alpha).
| std::invalid_argument | if the provided seed_vector is not a column vector. |
| std::vector< StagInt > stag::sweep_set_conductance | ( | stag::LocalGraph * | graph, |
| SprsMat & | vec | ||
| ) |
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\).
When the provided graph is a stag::LocalGraph, the volume of the support of the provided vector should be less than half the total volume of the graph. The method does not (and cannot) check this condition.
When the provided graph is a stag::Graph, there is no restriction on the volume of the support of the provided vector.
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.
| graph | a stag::LocalGraph or stag::Graph object |
| vec | the vector to sweep over |
| std::vector< StagInt > stag::sweep_set_conductance | ( | stag::Graph * | graph, |
| SprsMat & | vec | ||
| ) |
This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
| std::vector< StagInt > stag::connected_component | ( | stag::LocalGraph * | g, |
| StagInt | v | ||
| ) |
Return the vertex indices of every vertex in the same connected component as the specified vertex.
The running time of this method is proportional to the size of the returned connected component.
The returned vector is not sorted.
| g | a stag::LocalGraph instance |
| v | a vertex of the graph |
| std::vector< std::vector< StagInt > > stag::connected_components | ( | stag::Graph * | g | ) |
Return a vector of the connected components in the specified graph.
| g | a stag::Graph instance |
| double stag::adjusted_rand_index | ( | std::vector< StagInt > & | gt_labels, |
| std::vector< StagInt > & | labels | ||
| ) |
Compute the Adjusted Rand Index between two label vectors.
| gt_labels | the ground truth labels for the dataset |
| labels | the candidate labels whose ARI should be calculated |
| double stag::mutual_information | ( | std::vector< StagInt > & | gt_labels, |
| std::vector< StagInt > & | labels | ||
| ) |
Compute the Mutual Information between two label vectors.
| gt_labels | the ground truth labels for the dataset |
| labels | the candidate labels whose MI should be calculated |
| double stag::normalised_mutual_information | ( | std::vector< StagInt > & | gt_labels, |
| std::vector< StagInt > & | labels | ||
| ) |
Compute the Normalised Mutual Information between two label vectors.
| gt_labels | the ground truth labels for the dataset |
| labels | the candidate labels whose NMI should be calculated |
| double stag::conductance | ( | stag::LocalGraph * | graph, |
| std::vector< StagInt > & | 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\).
| graph | a stag::LocalGraph object representing \(G\). |
| cluster | a vector of node IDs in \(S\). |
| std::vector< StagInt > stag::symmetric_difference | ( | std::vector< StagInt > & | S, |
| std::vector< StagInt > & | T | ||
| ) |
Compute the symmetric difference of two sets of integers.
Given sets \(S\) and \(T\), the symmetric difference \(S \triangle T\) is defined to be
\[ S \triangle T = \{S \setminus T\} \cup \{T \setminus S\}. \]
Although \(S\) and \(T\) are provided as vectors, they are treated as sets and any duplicates will be ignored.
| S | a vector containing the first set of integers |
| T | a vector containing the second set of integers |
Construct an approximate similarity graph for the given dataset.
Given datapoints \(\{x_1, \ldots, x_n\} \in \mathbb{R}^n\) and a parameter \(a\), the similarity between two data points is given by
\[ k(x_i, x_j) = \mathrm{exp}\left(- a \|x_i - x_j\|^2 \right). \]
Then, the similarity graph of the data is a complete graph on \(n\) vertices such that the weight between vertex \(i\) and \(j\) is given by \(k(x_i, x_j)\). However, the complete similarity graph requires \(O(n^2)\) time and space to construct.
This method implements an algorithm which approximates the similarity graph with a sparse graph, while preserving any cluster structure of the graph. This algorithm has running time \(\widetilde{O}(n^{1.25})\).
| data | an \(n \times d\) Eigen matrix representing the dataset. |
| a | the parameter of the similarity kernel. |
Construct a complete similarity graph for the given dataset.
Given datapoints \(\{x_1, \ldots, x_n\} \in \mathbb{R}^n\) and a parameter \(a\), the similarity between two data points is given by
\[ k(x_i, x_j) = \mathrm{exp}\left(- a \|x_i - x_j\|^2 \right). \]
Then, the similarity graph of the data is a complete graph on \(n\) vertices such that the weight between vertex \(i\) and \(j\) is given by \(k(x_i, x_j)\).
Note that the time and space complexity of this method is \(O(n^2)\). For a faster, approximate method, you could consider using stag::approximate_similarity_graph.
| data | an \(n \times d\) Eigen matrix representing the dataset. |
| a | the parameter of the similarity kernel. |
1.9.6