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?

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

2 Answers 2

Reset to default
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

Improve this answer
$\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.

Improve this answer
$\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$
    – Felix Goldberg
    Commented 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$
    – Andrew D. King
    Commented Apr 16, 2012 at 17:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .