Welcome to MathOverflow

Question

2

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?

flag	asked Apr 15 2012 at 19:56 Hans Stricker 5,233●12●38

Which graph properties are of this kind: to be understood as an X-ness? Connected-ness? Tree-ness? Circle-ness? – Hans Stricker Apr 15 2012 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 2012 at 3:13

1

Cliqueness might be algebraic connectivity, divided by vertices minus one? – Will Sawin Apr 16 2012 at 3:20

Felix Goldberg · Answer 1 · 2012-04-15 21:37:29Z UTC

1

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

edited Apr 15 2012 at 21:37

answered Apr 15 2012 at 20:17

Felix Goldberg
2,363●4●12

Andrew D. King · Answer 2 · 2012-04-16 05:25:01Z UTC

1

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.

answered Apr 16 2012 at 5:25

Andrew D. King
1,087●6●11

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 2012 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 2012 at 17:52

Defining fuzzy properties of crisp graphs

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.