Graph clustering using mutual K-nearest neighbors

Most real world networks like social networks, protein-protein interaction networks, etc. can be represented as graphs which tend to include densely connected subgroups or modules. In this work, we develop a novel graph clustering algorithm called G-MKNN for clustering weighted graphs based upon a node affinity measure called 'Mutual K-Nearest neighbors' (MKNN). MKNN is calculated based upon edge weights in the graph and it helps to capture dense low variance clusters. This ensures that we not only capture clique like structures in the graph, but also other hybrid structures. Using synthetic and real world datasets, we demonstrate the effectiveness of our algorithm over other state of the art graph clustering algorithms. © 2014 Springer International Publishing.