| |||||||||
| |||||||||
| |||||||||
Description | |||||||||
Clustering and grouping algorithms that are graph-invariant and require no user intervention. | |||||||||
Synopsis | |||||||||
| |||||||||
Clustering Algorithms | |||||||||
Non-deterministic algorithms | |||||||||
The Chinese Whispering Algorithm. This is an adaptation of the algorithm described in: Biemann, C. (2006): Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems. Proceedings of the HLT-NAACL-06 Workshops on Textgraphs-06, New York, USA http://wortschatz.uni-leipzig.de/~cbiemann/pub/2006/BiemannTextGraph06.pdf The adaptations to this algorithm are as follows:
Simplistically, the way it works is this: 1. Every node is assigned into its own unique cluster. 2. For each iteration, sort the nodes into each order. For each node, it joins the most popular cluster in its neighbourhood (where popularity is defined by the sum of the weightings). 3. Repeat step 2. until a fixed point is reached. Note that this algorithm is non-deterministic, and that for some graphs no fixed point may be reached (and the algorithm may oscillate between a few different graph clusterings). | |||||||||
| |||||||||
| |||||||||
| |||||||||
The actual Chinese Whispers algorithm. | |||||||||
Spatial Algorithms | |||||||||
This implements the algorithm called CLUSTER, from the paper: Bandyopadhyay, S. (2003): An automatic shape independent clustering technique. Pattern Recognition, vol. 37, pp. 33-45. Simplistically, it defines clusters as groups of nodes that are spatially located closer to each other than to nodes in other clusters. It utilises the concept of a /Relative Neighbour Graph/ [RNG] to determine the spatial structure of a set of two-dimensional data points. The adaptations to this algorithm are as follows:
The algorithm is renamed relativeNeighbourhood. Experimentally, it seems to work better with larger graphs (i.e. more nodes), since then Graphviz makes the apparent clusters more obvious. | |||||||||
| |||||||||
The renamed CLUSTER algorithm. Attempts to cluster a graph by using the spatial locations used by Graphviz. | |||||||||
Graph Collapsing | |||||||||
Collapse the interesting parts of a graph down to try and show a compressed overview of the whole graph. Note that this doesn't work too well on undirected graphs, since every pair of nodes forms a K_2 subgraph. It may be possible to extend this to a clustering algorithm by collapsing low density regions into high density regions. | |||||||||
| |||||||||
| |||||||||
| |||||||||
Produced by Haddock version 2.3.0 |