| |
| |
| Praktikum-Modul 2: "Community Structures in biologischen Netzwerken" |
|
|
 |
|
|
ClusterAlgorithmus.
Als ClusterAlgorithmus wurde der von Chris Biemann entwickelte “Chinese Whispers Algorithmus”
verwendet.
“ ... Chinese Whispers, henceforth abbreviated CW, is an efficient graph clustering algorithm. It has
been described first in [Biemann and Teresniak 2005] and more elaborately in [Biemann 2006].
CW is a clustering algorithm that clusters undirected, weighted graphs. Its runtime
complexity is
linear in the number of edges, which makes CW in comparison a very efficient algorithm. The output
is a fuzzy partitioning (nonhierarchical)
of the graph ...
... Intuitively, the algorithm works as follows in a bottom-up fashion: First, all nodes get different
classes. Then the nodes are processed for a small number of iterations and inherit the strongest class
in the local neighborhood. This is the class whose sum of edge weights to the current node is
maximal. In case of multiple strongest classes, one is chosen randomly. Regions of the same class
stabilize during the iteration and grow until they reach the border of a stable region of another class.
Note that classes are updated immediately: a node can obtain classes from the neighborhood that were
introduced there in the same iteration ... "[Biemann 2006]
http://wortschatz.informatik.uni-leipzig.de/~cbiemann/software/CW.html
|
|
|
Maria Herberg
Stephanie Kehr
|
| |
|