Hierarchical clustering of networks
Hierarchical clustering is one method for finding community structures in a network. The technique arranges the network into a hierarchy of groups according to a specified weight function. The data can then be represented in a tree structure known as a dendrogram. Hierarchical clustering can either be agglomerative or divisive depending on whether one proceeds through the algorithm by adding links to or removing links from the network, respectively. One divisive technique is the Girvan–Newman algorithm.
Algorithm
In the hierarchical clustering algorithm, a weight [math]\displaystyle{ W_{ij} }[/math] is first assigned to each pair of vertices [math]\displaystyle{ (i,j) }[/math] in the network. The weight, which can vary depending on implementation (see section below), is intended to indicate how closely related the vertices are. Then, starting with all the nodes in the network disconnected, begin pairing nodes from highest to lowest weight between the pairs (in the divisive case, start from the original network and remove links from lowest to highest weight). As links are added, connected subsets begin to form. These represent the network's community structures.
The components at each iterative step are always a subset of other structures. Hence, the subsets can be represented using a tree diagram, or dendrogram. Horizontal slices of the tree at a given level indicate the communities that exist above and below a value of the weight.
Weights
There are many possible weights for use in hierarchical clustering algorithms. The specific weight used is dictated by the data as well as considerations for computational speed. Additionally, the communities found in the network are highly dependent on the choice of weighting function. Hence, when compared to real-world data with a known community structure, the various weighting techniques have been met with varying degrees of success.
Two weights that have been used previously with varying success are the number of node-independent paths between each pair of vertices and the total number of paths between vertices weighted by the length of the path. One disadvantage of these weights, however, is that both weighting schemes tend to separate single peripheral vertices from their rightful communities because of the small number of paths going to these vertices. For this reason, their use in hierarchical clustering techniques is far from optimal.[1]
Edge betweenness centrality has been used successfully as a weight in the Girvan–Newman algorithm.[1] This technique is similar to a divisive hierarchical clustering algorithm, except the weights are recalculated with each step.
The change in modularity of the network with the addition of a node has also been used successfully as a weight.[2] This method provides a computationally less-costly alternative to the Girvan-Newman algorithm while yielding similar results.
See also
References
- ↑ 1.0 1.1 Girvan, M.; Newman, M. E. J. (2002-06-11). "Community structure in social and biological networks". Proceedings of the National Academy of Sciences 99 (12): 7821–7826. doi:10.1073/pnas.122653799. ISSN 0027-8424. PMID 12060727. Bibcode: 2002PNAS...99.7821G.
- ↑ Newman, M. E. J. (2004-06-18). "Fast algorithm for detecting community structure in networks". Physical Review E 69 (6): 066133. doi:10.1103/physreve.69.066133. ISSN 1539-3755. PMID 15244693. Bibcode: 2004PhRvE..69f6133N.
 |  |
