Artificial Intelligence Stack Exchange is a question and answer site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment. It only takes a minute to sign up.
Sign up to join this community
There are several (family of) algorithms that can be used to cluster a set of $d$-dimensional points: for example, k-means, k-medoids, hierarchical clustering (agglomerative or divisive).
What is graph-based clustering? Are we clustering the nodes or edges of a graph instead of a set of $d$-dimensional (as e.g. in k-means)? Couldn't we just use k-means to also cluster a set of nodes?
In graph clustering, we want to cluster the nodes of a given graph, such that nodes in the same cluster are highly connected (by edges) and nodes in different clusters are poorly or not connected at all.
A simple (hierarchical and divisive) algorithm to perform clustering on a graph is based on first finding the minimum spanning tree of the graph (using e.g. Kruskal's algorithm), $T$. It then proceeds in iterations. At each iteration, we remove from $T$ the edge with the highest weight. Given that $T$ is a tree, the removal of an edge from $T$ will create a forest (with connected components). So, after the removal of the edge of highest weight from $T$, we will have two connected components. These two connected components will represent two clusters. So, after one iteration, we will have two clusters. At the next iteration, we remove the edge with the second highest weight, and this will create other connected components, and so on, until, possibly, all nodes are in their own cluster (that is, all edges have been removed from $T$).
There are several limitations of this algorithm. For example, it only considers the edges of the initial graph that are shared with $T$ (that is, it only considers the edges of the minimum spanning tree). It also requires the edges of the graph to be weighted. It does not require the number of clusters to be known in advance (like any other hierarchical clustering algorithm), but we still need to choose the optimal number of clusters (after the algorithm has terminated). We can do that in several ways. A way to do it would be to have a threshold value $t$ that is used to decide when we should stop removing edges from $T$: more specifically, we will keep removing edges from $T$ until the next highest weight is higher than this threshold $t$.
There are numerous applications of this type of clustering. For example, we might want to discover certain groups of people in social networks.
The paper Graph clustering (by Satu Elisa Schaeffer, 2007) provides a readable and quite detailed overview of this field.
There are algorithms based on k-means that can also work on graphs. See e.g. Graph-based k-means Clustering: A Comparison of the Set Median versus the Generalized Median Graph (by Ferrer et al.).
