Hierarchical link clustering algorithm in networks

Hierarchical network clustering is an approach to find tightly and internally connected clusters (groups or communities) of nodes in a network based on its structure. Instead of nodes, it is possible to cluster links of the network. The sets of nodes belonging to clusters of links can overlap. While overlapping clusters of nodes are not always expected, they are natural in many applications. Using appropriate dissimilarity measures, we can complement the clustering strategy to consider, for example, the semantic meaning of links or nodes based on their properties. We propose a new hierarchical link clustering algorithm which in comparison to existing algorithms considers node and/or link properties (descriptions, attributes) of the input network alongside its structure using monotonic dissimilarity measures. The algorithm determines communities that form connected subnetworks (relational constraint) containing locally similar nodes with respect to their description. It is only implicitly based on the corresponding line graph of the input network, thus reducing its space and time complexities. We investigate both complexities analytically and statistically. Using provided dissimilarity measures, our algorithm can, in addition to the general overlapping community structure of input networks, uncover also related subregions inside these communities in a form of hierarchy. We demonstrate this ability on real-world and artificial network examples.

Figure 1

Two dendrograms of hierarchies obtained by a monotonic dissimilarity (left) and a nonmonotonic dissimilarity (right). While the clustering partition on the left, obtained by cutting the hierarchy into clusters 1, 2, and 3, is uniquely defined, the clustering partition in the right case is not. We have to decide which of the three clustering partitions, A, B, or C, to choose.

Figure 2

A diagram of running times of the basic algorithm in relation to the product of the number of nodes and the maximal degree in random generated scale-free networks. Each node had its own single unique keyword.

Figure 3

A diagram of running times of the adapted algorithm in relation to the product of the number of nodes and the maximal degree ($\mathrm{\Delta }$) in random generated scale-free networks. Each node had its own single unique keyword.

Figure 4

A diagram of running times of the adapted algorithm in relation to the product of the number of nodes and the maximal degree ($\mathrm{\Delta }$) in random generated scale-free networks. Each node had 10 random keywords of a set from 200 keywords.

Figure 5

Three clusterings on the demonstration network. Nodes are labeled with their numbers followed by a string of their keywords. Clusters obtained by cutting the hierarchy (Fig. 6) produced by the algorithm on the intervals below each network sketch are color coded and surrounded by broken lines. In the top region of the leftmost clustering, each link is in its own cluster.

Figure 6

Flattened hierarchy of links obtained by the adapted algorithm using dissimilarity $D_{\mathrm{SC}}$ on the demonstration network. Dissimilarity values are displayed at the top of branchings. Links are displayed on the bottom by pairs of linked network nodes.

Figure 7

Flattened hierarchy of links obtained by the adapted algorithm using dissimilarity $D_{\mathrm{SF}}$ on the demonstration network. Dissimilarity values are displayed at the top of branchings. Links are displayed on the bottom by pairs of linked network nodes.

Figure 8

A diagram of differences ($\delta$) between each clustering obtained by a given cut value in the hierarchy generated on the demonstration network by the adapted algorithm and the ground-truth clustering. The optimal cut takes place at value 6 and $\delta =0.221$. It is marked with a bigger bullet in the diagram.

Figure 9

A diagram of differences ($\delta$) between each clustering obtained by a given cut value in the hierarchy generated on the network of oscilloscope probes by the adapted algorithm, and the ground-truth clustering. The optimal cut takes place at value 28 and $\delta =0.253$. See the emphasized dot in the diagram.

Figure 10

Scheme of locations of clusters of authors in the hierarchy from the author collaboration network.

Figure 11

Sets of keywords corresponding to selected clusters in the hierarchy from the author collaboration network. Keywords in green (darker) color on the leftmost and on the middle set correspond to keywords from the intersection of clusters $\mathcal{A}\cap \mathcal{B}$. Darker keywords on the rightmost set correspond to the cluster $\mathcal{A}\cap \mathcal{Z}$.