Recovering nested structures in networks: an evaluation of hierarchical clustering techniques.

In this article, we present various algorithms to partition the nodes of a network into groups that show the property of nestedness. Since perfect nestedness is a rare phenomenon, we consider the task from a data mining perspective, and we search for groups having high-level of nestedness. We utilize both agglomerative and divisive hierarchical clustering procedures and compare them on several benchmark and real-life networks. Furthermore, we propose different metrics derived from the results of our algorithms. We show that average-linkage and complete-linkage clustering can recover the largest fully nested clusters, and that the cluster size-weighted mean nestedness was a more stable metric for measuring clustering performance. Our proposed algorithms allow us to create multiple resolution views of nestedness-based clustering of networks, extending the field of graph-based data mining. [ABSTRACT FROM AUTHOR]