Answers.Body: <p>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. </p>
  
  <p>A simple (hierarchical and divisive) algorithm to perform clustering on a graph is based on first finding the <a href="https://en.wikipedia.org/wiki/Minimum_spanning_tree" rel="nofollow noreferrer">minimum spanning tree</a> of the graph (using e.g. <a href="https://en.wikipedia.org/wiki/Kruskal%27s_algorithm" rel="nofollow noreferrer">Kruskal's algorithm</a>), <span class="math-container">$T$</span>. It then proceeds in iterations. At each iteration, we remove from <span class="math-container">$T$</span> the edge with the highest weight. Given that <span class="math-container">$T$</span> is a <a href="https://en.wikipedia.org/wiki/Tree_(data_structure)" rel="nofollow noreferrer">tree</a>, the removal of an edge from <span class="math-container">$T$</span> will create a <a href="http://mathworld.wolfram.com/Forest.html" rel="nofollow noreferrer">forest</a> (with connected components). So, after the removal of the edge of highest weight from <span class="math-container">$T$</span>, 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 <span class="math-container">$T$</span>). </p>
  
  <p>There are several limitations of this algorithm. For example, it only considers the edges of the initial graph that are shared with <span class="math-container">$T$</span> (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 <span class="math-container">$t$</span> that is used to decide when we should stop removing edges from <span class="math-container">$T$</span>: more specifically, we will keep removing edges from <span class="math-container">$T$</span> until the next highest weight is higher than this threshold <span class="math-container">$t$</span>.</p>
  
  <p>There are numerous applications of this type of clustering. For example, we might want to discover certain groups of people in social networks.</p>
  
  <p>The paper <a href="http://www.leonidzhukov.net/hse/2016/networks/papers/GraphClustering_Schaeffer07.pdf" rel="nofollow noreferrer">Graph clustering</a> (by Satu Elisa Schaeffer, 2007) provides a readable and quite detailed overview of this field. </p>
  
  <p>There are algorithms based on k-means that can also work on graphs. See e.g. <a href="http://digital.csic.es/bitstream/10261/30134/1/Graph-based%20k-means.pdf" rel="nofollow noreferrer">Graph-based k-means Clustering: A Comparison of the Set Median versus the Generalized Median Graph</a> (by Ferrer et al.).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-20T16:55:39.990Z
Answers.LastActivityDate: 2019-03-21T10:25:47.193Z
Answers.LastEditDate: 2019-03-21T10:25:47.193Z
Answers.UserDisplayName: nbro
Body: <p>There are several (family of) algorithms that can be used to cluster a set of <span class="math-container">$d$</span>-dimensional points: for example, <a href="https://en.wikipedia.org/wiki/K-means_clustering" rel="nofollow noreferrer">k-means</a>, <a href="https://en.wikipedia.org/wiki/K-medoids" rel="nofollow noreferrer">k-medoids</a>, <a href="https://en.wikipedia.org/wiki/Hierarchical_clustering" rel="nofollow noreferrer">hierarchical clustering</a> (agglomerative or divisive). </p>
  
  <p>What is graph-based clustering? Are we clustering the nodes or edges of a graph instead of a set of <span class="math-container">$d$</span>-dimensional (as e.g. in k-means)? Couldn't we just use k-means to also cluster a set of nodes?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-21T11:57:29.080Z
Comments.Text: Not to be confused with clustering multiple different graphs based on e.g. their [edit distance](https://en.wikipedia.org/wiki/Graph_edit_distance) or geometric properties, as in http://www.eurocg2019.uu.nl/papers/45.pdf
Comments.UserDisplayName: Discrete lizard
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-03-21T14:11:22.150Z
Comments.Text: @Discretelizard Yes, this is also noted in the paper I mentioned in my answer (maybe I should have pointed this out in my answer).
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-23T19:38:22.333Z
Comments.Text: In addition to the methods mentioned by nbro for clustering the nodes of a graph,"spectral clustering" for non-graph data conceptually proceeds by assembling a graph the nodes of which are the data points. It then uses the highest-eigenvalue eigenvectors of a diffusion operator on thisgraph to assign nodes to clusters. For data that is already in graph form, a procedure that skips the first part might be of interest.
Comments.UserDisplayName: tsbertalan
Tags: <unsupervised-learning><clustering><k-means>
Title: What is graph clustering?
UserDisplayName: nbro
ThreadText: # What is graph clustering?
  
  (Asked by: username_0 on 2019-03-20)
  
  There are several (family of) algorithms that can be used to cluster a set of $d$-dimensional points: for example, [k-means](https://en.wikipedia.org/wiki/K-means_clustering), [k-medoids](https://en.wikipedia.org/wiki/K-medoids), [hierarchical clustering](https://en.wikipedia.org/wiki/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?
  
  **Tags:** unsupervised-learning, clustering, k-means
  > **Comments:**
  > **username_1**: Not to be confused with clustering multiple different graphs based on e.g. their [edit distance](https://en.wikipedia.org/wiki/Graph_edit_distance) or geometric properties, as in http://www.eurocg2019.uu.nl/papers/45.pdf  
  > **username_0**: @Discretelizard Yes, this is also noted in the paper I mentioned in my answer (maybe I should have pointed this out in my answer).  
  > **username_2**: In addition to the methods mentioned by nbro for clustering the nodes of a graph,"spectral clustering" for non-graph data conceptually proceeds by assembling a graph the nodes of which are the data points. It then uses the highest-eigenvalue eigenvectors of a diffusion operator on thisgraph to assign nodes to clusters. For data that is already in graph form, a procedure that skips the first part might be of interest.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2019-03-20. Score: 5
  
  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](https://en.wikipedia.org/wiki/Minimum_spanning_tree) of the graph (using e.g. [Kruskal's algorithm](https://en.wikipedia.org/wiki/Kruskal%27s_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](https://en.wikipedia.org/wiki/Tree_(data_structure)), the removal of an edge from $T$ will create a [forest](http://mathworld.wolfram.com/Forest.html) (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](http://www.leonidzhukov.net/hse/2016/networks/papers/GraphClustering_Schaeffer07.pdf) (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](http://digital.csic.es/bitstream/10261/30134/1/Graph-based%20k-means.pdf) (by Ferrer et al.).
  
  
  ---
  
  