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


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.

  • $\begingroup$ Can you please elaborate on objective functions? $\endgroup$ – suhas bhairav Mar 20 '16 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$ – Yuval Filmus Mar 20 '16 at 22:04
  • $\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$ – David Richerby Oct 27 '18 at 9:33

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.)

  • $\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$ – David Richerby Mar 20 '16 at 19:40

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

  • $\begingroup$ Do you have an idea about using implicit enumeration on the problem of graph partitioning ? $\endgroup$ – Hilbert Hotel Feb 3 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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