7
$\begingroup$

What is the difference between graph-partitioning and graph-clustering in graph theory?

$\endgroup$

3 Answers 3

11
$\begingroup$

Graph partitioning and graph clustering are informal concepts, which (usually) mean partitioning the vertex set under some constraints (for example, the number of parts) such that some objective function is maximized (or minimized). We usually have some specific constraints and objective function in mind. However graph partitioning and graph clustering, as vague informal concepts, are pretty much the same.

$\endgroup$
3
  • $\begingroup$ Can you please elaborate on objective functions? $\endgroup$ Mar 20, 2016 at 21:44
  • 1
    $\begingroup$ There are very many of them. The objective function defines what it means to be a good partition. For a random example, see here: en.wikipedia.org/wiki/K-means_clustering#Description. $\endgroup$ Mar 20, 2016 at 22:04
  • 1
    $\begingroup$ Is this really true? My impression of the terms is that "graph partitioning" refers to any method of dividing a graph up into multiple parts, whereas "graph clustering" strongly implies that the parts induce reasonably dense subgraphs. For example, producing a $3$-colouring is definitely partitioning but I don't think anyone would call it clustering. $\endgroup$ Oct 27, 2018 at 9:33
3
$\begingroup$

There tends to be an emphasis on edges in partitioning. ("A good partition is defined as one in which the number of edges running between separated components is small." from the English Wikipedia.) On the other hand, clustering tends to be about vertices (or the connectedness of the subgraph of neighbors of a vertex). This is entirely a linguistic artifact and I would not expect it to be as prevalent in non-English writing.

(Of course, it's challenging to separate the roles of vertices and edges in defining nearness or connectedness, so such a distinction is necessarily somewhat artificial.)

$\endgroup$
1
  • $\begingroup$ This is very dependent on context. For example, the definition of bipartite graphs is that there's a partition of the vertex set such that all the edges go between the parts. $\endgroup$ Mar 20, 2016 at 19:40
2
$\begingroup$

Both creates partitions/blocks. In partitioning number of partitions/blocks 'K' is given in advance. While in clustering we do not know what number of partitions/clusters/groups will be formed by clustering. Following screenshot is taken from this text.

enter image description here

$\endgroup$
2
  • 1
    $\begingroup$ Do you have an idea about using implicit enumeration on the problem of graph partitioning ? $\endgroup$
    – user99918
    Feb 3, 2019 at 11:24
  • $\begingroup$ @user99918 I do not have any idea about it. $\endgroup$ Nov 1, 2019 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.