0
$\begingroup$

I am reading Markov Random Field Analysis. I am somewhat confused by the definition of a clique in that book.

edited: definition from the book "A clique c for $(\mathcal{S},\mathcal{N})$ is defined as a subset of sites in $\mathcal{S}$. It consists of either a single-site $c=\{i\}$, a pair of neighboring sites c=\{i,i'\}, a triple of neighboring sites c=\{i,i',i''\}, and so on.". This is the definition I am familiar with, but then the author goes on: "Note that the sites in a clique are ordered and {i,i'} is not the same clique as {i',i}, and so on."

Is this a well-known alternative definition to the typical non-ordered definition ?

What would a maximal clique be if cliques are ordered? E.g. a graph with three nodes all connected and the cliques: {1,2,3},{1,3,2},{3,2,1}... would they all be maximal cliques?

I do understand how the definition in the book may be useful for image analysis (e.g. encourage flow towards one direction so the potential has different energies depending on the order of the clique). Then again I can't see why that could not be taken into account by an alternative potential which takes all orientations into account when given a non-ordered clique.

  • 0
    @Jacopo, I added the definition. Yet it is the note from the author about cliques being ordered which is confusing. Especially considering his definition to me at least makes the cliques non-ordered.2012-01-08

1 Answers 1

1

In my (very limited) experience an ordered clique is simply a clique with a linear order imposed on its vertices. I’ve seen the concept used in purely graph-theoretic contexts and in an example related to complexity theory, but my impression is that in those cases the ordering was primarily just a technical convenience. A maximal ordered clique would be simply a maximal clique with a linear order imposed on its vertices. (This works even if ordered cliques are themselves ordered by end extension rather than by simple order-compatibility, so that $\langle K_1,\le_1\rangle$ precedes $\langle K_2,\le_2\rangle$ iff $\langle K_1,\le_1\rangle$ is an initial segment of $\langle K_2,\le_2\rangle$: an ordered clique whose underlying unordered clique is not maximal can always be end-extended to a larger ordered clique with the new vertex at the end of the linear order.)

Using ordinary curly braces for an ordered set and distinguishing \{i,i'\} from \{i',i\} is abysmally sloppy, but it may not be uncommon in that particular field: Google found another example in Chan & Peng, Wavelets for sensing technologies, p. 62, with the same sloppy notation and a similar mention, almost as an afterthought, that the cliques (of pixels) under discussion are ordered.

  • 0
    Thanks for also pointing out that the curly braces are indeed a bad notation. I am using ordinary parentheses (tuples) for such cases but the book confused me into thinking there may be some alternative notation I am not aware of.2012-01-09