# Defining fuzzy properties of crisp graphs

Is there a standard procedure to define fuzzy generalizations of typical graph properties?

Consider the concept of a fuzzy clique. Define the cliqueness $c(G)$ of a graph $G$ as the ratio $\text{deg}(G)\ /\ (|V(G)|-1)$ between the mean degree of $G$ and the number of its vertices (minus one).

Alternatively: $c(G) = 2\ |E|\ /\ (|V|^2 - |V|)$.

That is, a graph deviates from being a "true" clique with the number of its missing possible edges. But shouldn't the missing edges been distributed as uniformly as possible among the vertices? Isn't 3 more of a (fuzzy) clique than 2 (which is more of a "true" clique plus an extra vertex), even though they have the same cliqueness?

Should one try to capture this (felt) difference between 2 and 3? E.g. by considering higher moments of the distribution of missing edges?

Is this program (including higher moments) executed somewhere? And how is it to be generalized?

-
Which graph properties are of this kind: to be understood as an X-ness? Connected-ness? Tree-ness? Circle-ness? –  Hans Stricker Apr 15 '12 at 20:29
I agree with Felix. Spectral graph theory is almost certainly the sort of thing you want, since eigenvalues and other linear algebra things tend to be the most well-behaved fuzzy measurements. For instance, I think that connectedness is algebraic connectivity. –  Will Sawin Apr 16 '12 at 3:13
Cliqueness might be algebraic connectivity, divided by vertices minus one? –  Will Sawin Apr 16 '12 at 3:20

I think fractional graph theory fits the bill...

Also, spectral extremal graph theory might be interesting. There is a new and excellent survey by Nikiforov:

http://arxiv.org/pdf/1107.1121.pdf

-

One way to argue that 2 has more cliqueness than 3 is to take whatever graph clustering algorithm you like, and ask whether or not the graph ends up as one cluster. Likely 2 will be split into two clusters, whereas 3 will be one cluster, but this depends on the algorithm.

The issue is discussed in Chapter 2 of my master's thesis (http://www.sfu.ca/~adk7/papers/mscthesis.ps) but it's eight years old and probably not the best reference out there.

-
As an empirical investigation, this might be great, but I'm not sure an informative theoretical measure can be had this way. –  Felix Goldberg Apr 16 '12 at 6:47
Agreed. The problem of how to find a good graph clustering is subject to a lot of debate, and is very closely related to this problem. Given a clustering scoring function $f$, and letting $f_o$ be the optimal score of any clustering (vertex partition) of $G$, probably $f_o/f(G)$ would be a good measurement of cliqueness. But in the end, finding the function $f$ is really a matter of taste and context. –  Andrew D. King Apr 16 '12 at 17:52