Sign up ×

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?

alt text

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?

share|cite|improve this question
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

2 Answers 2

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:

share|cite|improve this answer

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 ( but it's eight years old and probably not the best reference out there.

share|cite|improve this answer
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

Your Answer


