Adapting k-means for graph clustering

Abstract We propose two new algorithms for clustering graphs and networks. The first, called K‑algorithm , is derived directly from the k -means algorithm. It applies similar iterative local optimization but without the need to calculate the means. It inherits the properties of k -means clustering in terms of both good local optimization capability and the tendency to get stuck at a local optimum. The second algorithm, called the M-algorithm , gradually improves on the results of the K -algorithm to find new and potentially better local optima. It repeatedly merges and splits random clusters and tunes the results with the K -algorithm. Both algorithms are general in the sense that they can be used with different cost functions. We consider the conductance cost function and also introduce two new cost functions, called inverse internal weight and mean internal weight . According to our experiments, the M -algorithm outperforms eight other state-of-the-art methods. We also perform a case study by analyzing clustering results of a disease co-occurrence network, which demonstrate the usefulness of the algorithms in an important real-life application.