Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
1  
Cliqueness might be algebraic connectivity, divided by vertices minus one? –  Will Sawin Apr 16 '12 at 3:20
add comment

2 Answers 2

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.

share|improve this answer
1  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.