1
$\begingroup$

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(source)

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?

$\endgroup$
3
  • $\begingroup$ Which graph properties are of this kind: to be understood as an X-ness? Connected-ness? Tree-ness? Circle-ness? $\endgroup$ Apr 15, 2012 at 20:29
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Apr 16, 2012 at 3:13
  • 1
    $\begingroup$ Cliqueness might be algebraic connectivity, divided by vertices minus one? $\endgroup$
    – Will Sawin
    Apr 16, 2012 at 3:20

2 Answers 2

1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ As an empirical investigation, this might be great, but I'm not sure an informative theoretical measure can be had this way. $\endgroup$ Apr 16, 2012 at 6:47
  • $\begingroup$ 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. $\endgroup$ Apr 16, 2012 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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