Consider graph clusterings as an example of constructions.

Let a [clustering][1] of a graph $(V,E)$ be any covering of $V$, i.e. a set $C$ with $\bigcup C = V$. 

I am looking for a way to define the notion of a "*natural* graph clustering". By a natural graph clustering I mean - informally - a clustering that can be uniformly defined for all graphs by a formula or an algorithm that doesn't depend on arbitrary parameters.

Intended examples of natural graph clusterings include

1. the connected components of a graph
2. the cliques of a graph
3. the maximal cliques of a graph
4. the orbits of the automorphism group of a graph

Intended counter-examples (while depending on parameters) include

1. cliques up to size $k$ 
2. quasi-cliques, i.e. a fraction $\theta$ of the edges can be missing

But what does it mean *formally* to "depend on a parameter"? E.g. counter-example (1) can easily be defined by a formula not containing any numeric parameter $k$ but instead an appropriate number of quantifiers.

> (How) can the notion of "dependence on a parameter" be formalized?

The problem is: every number (or other distinguished set) occuring in a formula as a parameter can either be eliminated by an appropriate number of quantifiers or by a [definite description][2].

An intuitive feeling remains that the counter-examples are less "natural" than the intended examples.

> So what does distinguish the intended examples from the counter-examples?

Or is it a chimera, and such a distinction cannot be made?

**[Appendix]**

There are unclear cases for which I have no intuition whether they should count as examples or counter-examples:

1. connected induced subgraphs with more edges than vertices (a kind of quasi-clique)


----------

<sup>I also tried to ask [this question at MSE][3].</sup>


  [1]: https://s3-us-west-2.amazonaws.com/mlsurveys/13.pdf
  [2]: http://en.wikipedia.org/wiki/Theory_of_descriptions
  [3]: http://math.stackexchange.com/questions/679440/natural-definitions-of-families-of-subgraphs