8
$\begingroup$

It is now a well known observation that many graphical structures that arise in natural settings tend to obey scale-free properties, such as the power law of degree distribution.

Are there any good example of natural graphs that are fairly random and not do not necessarily obey scale-free properties?

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
7
$\begingroup$

The connections between neurons do not form scale-free networks, I think. See e.g. Figure 1 on p.181 of http://www.indiana.edu/~cortex/Koetter_chapter_modified.pdf and observe that the vertex degrees only span a single order of magnitude.

Improve this answer
$\endgroup$
7
$\begingroup$

The network topology of wireless ad hoc networks and wireless sensor networks are often captured by a random geometric graph. This means, picking random points in a planar domain, and connecting any two that are within a certain distance threshold. These graphs have Poisson degree distributions, even though they are quite different from the Erdos-Renyi random graphs, and they arise naturally as a network model.

Improve this answer
$\endgroup$
3
$\begingroup$

Although I am not sure what you mean by "random", obvious natural non-scale-free graphs are the road networks.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well, random in the sense that the vertices would come at random and attach to others following some (possibly hidden) probability distribution. $\endgroup$
    – Arnab
    Commented Dec 6, 2012 at 13:59
  • 6
    $\begingroup$ Actually, road networks are scale-free, when viewed appropriately. Obviously the natural representation isn't, since most intersection have degree at most 4 or sometimes 5 or rarely 6. But if you take the dual representation - a node for each road, and edge between them if the roads ever meet - you do get a scale-free network: cs.unm.edu/~treport/tr/05-10/RoadNetworks.pdf. $\endgroup$
    – Joshua Grochow
    Commented Dec 6, 2012 at 18:28

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.