Link Clustering

In this blog post, I will be talking about a very recent paper by Yong-Yeol Ahn et al, titled 'Link communities reveal multiscale complexity in networks' which appeared in Nature (a physics journal) in 2010. Today's lecture, introducing clustering coefficient, would serve as a great introduction for this post.

Networks have become a key approach to understanding systems of interacting objects, unifying the study of diverse phenomena including human society. One crucial step when studying the structure and dynamics of networks is to identify communities: groups of related nodes that correspond to functional subunits such as social spheres. Communities in networks often overlap such that nodes simultaneously belong to several groups. Meanwhile, many networks are known to possess hierarchical organization, where communities are recursively grouped into a hierarchical structure . However, the fact that many real networks have communities with pervasive overlap, where each and every node belongs to more than one group, has the consequence that a global hierarchy of nodes cannot capture the relationships between overlapping groups.

While most of the previous works focused on clustering nodes, this work tries to cluster links instead of nodes and successfully reconcile the antagonistic organizing principles of overlapping communities and hierarchy. When I think about it, it feels obvious, now! :)

The method in its essence, is as follows:

For an undirected, unweighted network, we denote the node as i and its neighbours as n₊(i). Limiting ourselves to link pairs that share a node, expected to be more similar than disconnected pairs, we find the similarity, S, between links e_ik and e_jk to be

Shared node k does not appear in S because it provides no additional information and introduces bias. Single-linkage hierarchical clustering builds a link dendrogram, cutting this dendrogram at some clustering threshold yields link communities.

Reference:
Ahn Y-Y, Bagrow JP, Lehmann S. Link communities reveal multiscale complexity in networks. Nature. 2010;466:761–764.