I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are the cliques and clusters the same?

  • 2
    $\begingroup$ What are cluster graphs? $\endgroup$ – Yuval Filmus Feb 7 '14 at 2:12
  • 1
    $\begingroup$ And which are "the videos on Coursera"? Are you folloing Koller's course? Have you checked her book, or Googled? $\endgroup$ – Raphael Feb 7 '14 at 7:41
  • $\begingroup$ Yes the Koller's course. But I am finding it a bit hard to do the assignments. Yet to get the book though. Thanks for your answer. $\endgroup$ – Yathi Feb 9 '14 at 9:56

A clique is a rigorously defined, exact part of a graph $G=(V,E)$;

$\qquad\displaystyle C \subseteq V \text{ is clique} \iff \{ \{u,v\} \mid u,v \in C, u \neq v \} \subseteq E$.

A cluster is more general, but also more nebulous. Here's what Wikipedia has to say:

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).

So, a cluster also is a set of nodes that is "dense" in some sense, depending on the metric used. However, while is it always clear whether adding a note increases the size of a clique, it's not always clear from looking only at one cluster whether adding a node to it is better; the quality of a clustering is defined on the whole graph.

As the Wikipedia article shows, there are many notions of clustering. Cliques can be seen as one of them.

| cite | improve this answer | |

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.