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