info.aduna.linkmap.transform
Class ClusteringTransform

java.lang.Object
  info.aduna.linkmap.transform.ClusteringTransform

All Implemented Interfaces:

Transform

public class ClusteringTransform
extends Object
implements Transform

ClusteringTransform implements a transformationalgorithm that calculates the weight of every Vertex in a Graph based on graph-topological features.

The weight of a Vertex is defined as the fraction of the total number of connections between the neighbours of the vertex in the graph relative to the maximum total number of connections possible. In other words: to what degree are the neighbours of a vertex also eachothers direct neighbours, expressed on a scale from 0 to 1. In a graph where the vertices seem to cluster more or less (i.e. where subsets of vertices can be identified that have a relatively high connectivity inside the set and a relatively low connectivity with the rest of the vertices), vertices in the center of a cluster tend to have a high weight, and may be considered good representatives of what such a cluster is about.

There are two special cases to be taken in consideration. First, a vertex with no neighbours has a maximum weight, since it by definition represents its cluster very well. Second, vertices with only one neighbour have a weight of 0, since it could not be further away from the core of the graph.

There still seem to be some problems with this definition. For example, if a Graph contains a single vertex not connected to anything else, it has weight 1, but if there are two vertices connected to eachother but to nothing else, they both have a weight of 0. Clearly, this is not very intuitive (the rule concerning the "single neighbour" case works only satisfactorily when the vertex is connected to a relatively large subgraph). Furthermore, it may be rather unintuitive that a vertex with 12 neighbours may have a lower weight that a vertex with 6 neighbours, since the cluster containing the vertex with 12 neighbours is visually much more dense. When visualising such a structure, you would often expect that the vertex in that cluster to have relatively high weights, whereas the reality may quite be the opposite. Summarizing, the current definition seems to be too much oriented on local structures. Maybe a variation of the algorithm that considers all neighbours reachable in two steps might help.

Constructor Summary

ClusteringTransform()

Method Summary

Graph

transform(Graph graph) Transform the specified Graph and return the transformed Graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ClusteringTransform

public ClusteringTransform()

Method Detail

transform

public Graph transform(Graph graph)

Description copied from interface: Transform

Transform the specified Graph and return the transformed Graph.

Specified by:

transform in interface Transform