How is the clustering coefficient defined for random graphs? For example, a first definition could be calling clustering coefficient of a random graph the expected value of the clustering coefficient observed for every realization. According to this definition, how to compute the clustering coefficient for the Erdos-Renyi model? Is this a good definition?

  • $\begingroup$ What is the clustering coefficient? But that aside, the [whatever parameter] of a random graph is a random variable with a distribution. Its value depends on what the random graph ends up being. There's a chance that the parameter is very big, and there's a chance that it's very small (based on what the random graph ends up being). So when people say "what's the [blah] for a random graph," they mean what is the distribution of that random variable. Mean and variance are the first two things people usually care about. Then other concentration results if you can find them. $\endgroup$ – Pat Devlin Jan 17 '17 at 12:20
  • $\begingroup$ In your case, this coefficient is based on subgraph counts, so it should be easy to do. $\endgroup$ – Pat Devlin Jan 17 '17 at 12:27
  • $\begingroup$ To get a better feel for this sort of thing (and to see the answer to at least half the question) look up "number of triangles in random graph" [which, by the way, has a central limit theorem result]. $\endgroup$ – Pat Devlin Jan 17 '17 at 12:39
  • $\begingroup$ The calculation of the expected number of triangles is straightforward, I understand what you mean. The point, however, is to find the expected value of the ratio between triangles and connected triples and I guess that having the expected number of triangles is not of much help. $\endgroup$ – John K Jan 17 '17 at 13:12
  • $\begingroup$ Well, the number of triangles and the number of v's both concentrate about their means. So this gives $p$ as a guess for what the ratio should be? $\endgroup$ – Pat Devlin Jan 17 '17 at 13:13

This is a good definition. The answer can be found in the following thread: Expected global clustering coefficient for Erdős–Rényi graph


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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