# In Probabilistic Graphical Models, are Cliques and Clusters the same?

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?

• What are cluster graphs? – Yuval Filmus Feb 7 '14 at 2:12
• And which are "the videos on Coursera"? Are you folloing Koller's course? Have you checked her book, or Googled? – Raphael Feb 7 '14 at 7:41
• 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. – 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.