Graphalyze-0.4: Graph-Theoretic Analysis library.Source codeContentsIndex
Clustering Algorithms
Non-deterministic algorithms
Spatial Algorithms
Graph Collapsing
data Whispering a
chineseWhispers :: (RandomGen g, Eq a, Eq b, DynGraph gr) => g -> gr a b -> gr (Whispering a) b
relativeNeighbourhood :: (DynGraph gr, Eq a, Ord b) => gr a b -> gr (GenCluster a) b
data CNodes a = CN [LNode a]
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:

  • Increase the weighting of those nodes present in interesting structures, such as loops and root nodes. This is to try and ensure that these nodes end up in the same cluster.

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).



data Whispering a Source
An instance of ClusterLabel used for the Chinese Whispers algorithm.
show/hide Instances
The actual Chinese Whispers algorithm.
Spatial Algorithms

This implements the algorithm called CLUSTER, from the paper:



The adaptations to this algorithm are as follows:



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.


data CNodes a Source
A collapsed node contains a list of nodes that it represents.
CN [LNode a]
show/hide Instances
Show a => Show (CNodes a)
This definition of show is written so as to make the shapes of the nodes in Graphviz roughly circular, rather than one long ellipse.
Produced by Haddock version 2.1.0