Cluster analysis is a vibrant area of applied mathematics, "used in many fields, including machine learning, pattern recognition, image analysis, information retrieval, and bioinformatics". A subfield of cluster analysis of special mathematical interest - because of its clear-cut underlying definitions - is graph clustering.
a clique, i.e., a subset of nodes in a graph such that every two nodes in the subset are connected by an edge can be considered as a prototypical form of cluster. Relaxations of the complete connectivity requirement (a fraction of the edges can be missing) are known as quasi-cliques.
A completely different kind of graph clusters are the orbits of the automorphism group of a graph $G$, which are not necessarily connected but contain similar (in fact: structurally identical) objects.
Both cliques and orbits seem to me prototypical "natural definitions" of families of subgraphs.
The above mentioned relaxations - there is an infinitude of them - usually depend on arbitrary numerical parameters and don't feel so natural, at least when the parameters are not natural in a sense.
Comparably, a definition of "n-cliques" using not immediate but intermediate connectivity - eg. by replacing "connected by an edge (= 1-path)" by "connected by an n-path" in the definition above - would not feel as natural as the "immediate" definition.
But it is hard to formalize this intuitive feeling of "naturality" which comprises among others:
- no arbitrary numerical parameters
- no arbitrary reference to singled-out (named) objects
- no unnecessary complifications of otherwise simple definitions
My question is:
What attempts to define "natural definitions" are there, especially with respect to families of subgraphs of arbitrary graphs? Is it possible at all?