<p>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.</p>

CC BY-SA 3.0
2012-12-06T16:56:38.220Z
2012-12-06T16:56:38.220Z
Andras Farago
<p>Although I am not sure what you mean by "random", obvious natural non-scale-free graphs are the road networks.</p>

CC BY-SA 3.0
2012-12-06T13:59:24.467Z
Well, random in the sense that the vertices would come at random and attach to others following some (possibly hidden) probability distribution.
Arnab
CC BY-SA 3.0
2012-12-06T18:28:33.347Z
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: http://www.cs.unm.edu/~treport/tr/05-10/RoadNetworks.pdf.
Joshua Grochow
CC BY-SA 3.0
2012-12-06T06:07:56.270Z
2012-12-06T06:07:56.270Z
Snowie
<p>The connections between neurons do not form scale-free networks, I think. See e.g. Figure 1 on p.181 of <a href="http://www.indiana.edu/~cortex/Koetter_chapter_modified.pdf">http://www.indiana.edu/~cortex/Koetter_chapter_modified.pdf</a> and observe that the vertex degrees only span a single order of magnitude.</p>

CC BY-SA 3.0
2012-12-06T06:33:52.230Z
2012-12-06T06:33:52.230Z
David Eppstein
<p>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. </p>

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

<graph-theory><ni.networking-internet>
Natural graphs that are not scale free
Arnab
# Natural graphs that are not scale free

(Asked by: username_0 on 2012-12-05)

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?

**Tags:** graph-theory, ni.networking-internet

---

## 3 answers

### Answer by username_4 on 2012-12-06. Score: 7 | Accepted answer

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.


---

### Answer by username_1 on 2012-12-06. Score: 7

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.


---

### Answer by username_2 on 2012-12-06. Score: 3

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

> **Comments:**
> **username_0**: Well, random in the sense that the vertices would come at random and attach to others following some (possibly hidden) probability distribution.  
> **username_3**: 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: http://www.cs.unm.edu/~treport/tr/05-10/RoadNetworks.pdf.  

---

