Clustering coefficient

From WandoraWiki
Jump to: navigation, search

Clustering coefficient is a property of a node in a network. Roughly speaking it tells how well connected the neighborhood of the node is. If the neighborhood is fully connected, the clustering coefficient is 1 and a value close to 0 means that there are hardly any connections in the neighborhood. Wandora topic map editor application calculates clustering coefficient for any topic and topic group. Cluster coefficient is measured selecting tool option Copy also > Copy also topic clustering coefficient in context of topic selection. Calculated value is clustering coefficient of selected topics.

Clustering coefficient of the graph is the average clustering coefficient of all nodes in the graph. Topic map is effectively a graph where each topic is a node and each association is an edge in the graph. Thus it makes sense to calculate the clustering coefficient of a topic map. Wandora application is capable to measure topic map's clustering coefficient. Topic map's clustering coefficient is measured selecting tool option Layers > Statistics > Average clustering coefficient. Calculated value is clustering coefficient of entire topic map i.e. selected layer.

Formal definition

Consider following graph:

Wandora examplegraph2.png

Clustering coefficient of a node is the ratio of number of connections in the neighborhood of a node and the number of connections if the neighborhood was fully connected. Here neighborhood of node A means the nodes that are connected to A but does not include A itself. Note that a fully connected group of n nodes has n*(n-1)/2 connections.

For example, the neighborhood of topic 6 consists of topics 9, 12, 2 and 1. Between these topics there is only one connection, from topic 2 to topic 12. If the four topics were fully connected, that is there would be a connection from each topic to every other topic, there would be 4*3/2=6 connections. Clustering coefficient of topic 6 is therefor 1/6=0.17. Clustering coefficient of topic 1 is 0 because there is no connections at all between topics 0, 6, 11 and 19. Clustering coefficient of topic 3 is 1 because the neighborhood consisting of topics 12, 4 and 13 is fully connected.

Clustering coefficient in topic maps

The clustering coefficient tool in Wandora treats the topic map as a graph in the canonical way of treating each topic as a node and each association as an edge (or multiple edges in case of more than two players). You should note that because of this the clustering coefficient is highly dependent on the general structure of the topic map.

For example consider a topic map that contains information about movies and actors. Each actor topic is connected to a movie topic if the actor stars in that movie. This kind of topic map would always have a clustering coefficient of 0 no matter how many topics it contained and how the movies and actors were connected. Reason for this is that the neighborhood of an actor topic will always consists of only movie topics and movie topics are never directly linked. Similarly neighborhood of a movie topic consists only of actor topics. Generally speaking topics in topic maps are different in quality (or type) and direct connections between topics of same quality (or type) are rare.

On the other hand, you could have a topic map with only movie topics which are connected if they have at least one same actor. Results in this kind of topic map would be much more interesting.

Personal tools