<p>There are lots of overlaps between small world and scale-free, but I think much less so between those two and expanders.</p>

<p>The terms "small world" and "scale-free" are often used informally, but formal definitions are  often along the lines of:</p>

<ul>
<li><p>Small-world means short average (or maximum) path length (typically $O(\log n)$, with $n$ vertices) and highly clustered (meaning that for any vertex $v$, the fraction of pairs of neighbors of $v$ which are adjacent is high)</p></li>
<li><p>Scale-free is often taken to mean that the degree distribution follows some variant of a power-law (e.g. power-law with cutoff, etc.), but more generally/informally is used to mean that the degree distribution is long-tailed, in contrast to, say, Erdos-Renyi random graphs which have a degree distribution that is exponentially concentrated around its mean.</p></li>
</ul>

<p>Expander, of course, has a formal definition that is almost 100% standardized. </p>

<p>Expanders by their nature have logarithmic diameter, similar to small-world networks. Beyond that, however, as far as I know there is little overlap between the concepts. </p>

<p>In practice, expanders are often bounded-degree or even <em>regular</em> of bounded degree, whereas "real-world" graphs typically have a long-tailed degree distribution, with a small (but surprisingly large - e.g. not exponentially small) number of high-degree "hubs" (as they are usually called). Furthermore, scale-free graphs (almost by definition, depending on your definition) have a large number of vertices of very low degree - in most "real-world" graphs there are a large number of vertices of degree 1 or 2. This makes real-world graphs very unlike expanders, in that it is very easy to disconnect real-world graphs by removal of targeted edges, whereas expanders are by their nature highly connected. (Real-world graphs often also have the property that removal of <em>random</em> edges is very bad at disconnecting them.)</p>

<p>I'm sure there is something to be said about the use of spectral techniques for things like community detection, etc. in real-world networks, and from that viewpoint there may or may not be a little more overlap with expanders, but I'm not an expert in that area (maybe we can get Mark Newman to join cstheory.SE to comment...)</p>

CC BY-SA 3.0
2014-07-11T19:11:08.697Z
thx! the degree distribution is one simple/superficial way to study/classify them which maybe leads one to conclude a fundamental dissimilarity but maybe they have more abstract theoretical properties in common eg relating to paths/connectivity etc... long wondering if there is some deeper common principle that explains/unifies the ubiquity of all 3 classes...
vzn
CC BY-SA 3.0
2014-07-11T20:01:33.463Z
@vzn: I've been coming to view expanders and "real-world" graphs as opposites in a certain sense. Real-world graphs are what come from mostly disorganized/decentralized processes (even an engineering process like that which leads to the Intel chips was disorganized from the viewpoint of the underlying graph of the chip), whereas expanders are what we  come up with when try to optimize for certain parameters of the network.
Joshua Grochow
CC BY-SA 3.0
2014-07-11T17:53:07.840Z
2014-07-11T17:53:07.840Z
Joshua Grochow
<p><a href="http://en.wikipedia.org/wiki/Small-world_network" rel="nofollow noreferrer">small world graphs</a> (eg <a href="http://en.wikipedia.org/wiki/Watts_and_Strogatz_model" rel="nofollow noreferrer">Watts-Strogatz model</a> &amp; others) and <a href="http://en.wikipedia.org/wiki/Scale-free_network" rel="nofollow noreferrer">scale free graphs</a> are a relatively recently <em>discovered</em> graph type via mainly empirical analysis of large real-world graphs (eg via <a href="http://en.wikipedia.org/wiki/Big_data" rel="nofollow noreferrer">Big Data</a> techniques/ <a href="http://en.wikipedia.org/wiki/Datamining" rel="nofollow noreferrer">datamining</a> etc). they have since been found to be quite ubiquitous/ longstanding in many diverse graphs related to nature and human constructions (eg biology/genes, social networks, man-made networks eg WWW/ internet/ telecommunication/ electrical grids, airport connectivity, etc). </p>

<p>in contrast <a href="http://en.wikipedia.org/wiki/Expander_graph" rel="nofollow noreferrer">expander graphs</a> are <a href="https://mathoverflow.net/questions/168586/who-first-dubbed-them-expander-graphs">far older</a> and were invented mainly as a theoretical device in math/(T)CS however have since found very broad/ widespread/ key application. am looking for eg refs/ surveys/ overviews on their interrelation.</p>

<blockquote>
  <p>what are the relations between the following (eg is there any overlap for some parameters)</p>
  
  <ul>
  <li>small world networks</li>
  <li>scale free graphs</li>
  <li>expander graphs</li>
  </ul>
</blockquote>

<reference-request><graph-theory><big-picture><application-of-theory>
any relation/ overlap between small world graphs, scale free graphs, and expander graphs?
vzn
# any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

(Asked by: username_0 on 2014-07-11)

[small world graphs](http://en.wikipedia.org/wiki/Small-world_network) (eg [Watts-Strogatz model](http://en.wikipedia.org/wiki/Watts_and_Strogatz_model) & others) and [scale free graphs](http://en.wikipedia.org/wiki/Scale-free_network) are a relatively recently *discovered* graph type via mainly empirical analysis of large real-world graphs (eg via [Big Data](http://en.wikipedia.org/wiki/Big_data) techniques/ [datamining](http://en.wikipedia.org/wiki/Datamining) etc). they have since been found to be quite ubiquitous/ longstanding in many diverse graphs related to nature and human constructions (eg biology/genes, social networks, man-made networks eg WWW/ internet/ telecommunication/ electrical grids, airport connectivity, etc).

in contrast [expander graphs](http://en.wikipedia.org/wiki/Expander_graph) are [far older](https://mathoverflow.net/questions/168586/who-first-dubbed-them-expander-graphs) and were invented mainly as a theoretical device in math/(T)CS however have since found very broad/ widespread/ key application. am looking for eg refs/ surveys/ overviews on their interrelation.

> what are the relations between the following (eg is there any overlap for some parameters)
>
> * small world networks
> * scale free graphs
> * expander graphs

**Tags:** reference-request, graph-theory, big-picture, application-of-theory

---

## 1 answers

### Answer by username_1 on 2014-07-11. Score: 8 | Accepted answer

There are lots of overlaps between small world and scale-free, but I think much less so between those two and expanders.

The terms "small world" and "scale-free" are often used informally, but formal definitions are often along the lines of:

* Small-world means short average (or maximum) path length (typically $O(\log n)$, with $n$ vertices) and highly clustered (meaning that for any vertex $v$, the fraction of pairs of neighbors of $v$ which are adjacent is high)
* Scale-free is often taken to mean that the degree distribution follows some variant of a power-law (e.g. power-law with cutoff, etc.), but more generally/informally is used to mean that the degree distribution is long-tailed, in contrast to, say, Erdos-Renyi random graphs which have a degree distribution that is exponentially concentrated around its mean.

Expander, of course, has a formal definition that is almost 100% standardized.

Expanders by their nature have logarithmic diameter, similar to small-world networks. Beyond that, however, as far as I know there is little overlap between the concepts.

In practice, expanders are often bounded-degree or even *regular* of bounded degree, whereas "real-world" graphs typically have a long-tailed degree distribution, with a small (but surprisingly large - e.g. not exponentially small) number of high-degree "hubs" (as they are usually called). Furthermore, scale-free graphs (almost by definition, depending on your definition) have a large number of vertices of very low degree - in most "real-world" graphs there are a large number of vertices of degree 1 or 2. This makes real-world graphs very unlike expanders, in that it is very easy to disconnect real-world graphs by removal of targeted edges, whereas expanders are by their nature highly connected. (Real-world graphs often also have the property that removal of *random* edges is very bad at disconnecting them.)

I'm sure there is something to be said about the use of spectral techniques for things like community detection, etc. in real-world networks, and from that viewpoint there may or may not be a little more overlap with expanders, but I'm not an expert in that area (maybe we can get Mark Newman to join cstheory.SE to comment...)

> **Comments:**
> **username_0**: thx! the degree distribution is one simple/superficial way to study/classify them which maybe leads one to conclude a fundamental dissimilarity but maybe they have more abstract theoretical properties in common eg relating to paths/connectivity etc... long wondering if there is some deeper common principle that explains/unifies the ubiquity of all 3 classes...  
> **username_1**: @vzn: I've been coming to view expanders and "real-world" graphs as opposites in a certain sense. Real-world graphs are what come from mostly disorganized/decentralized processes (even an engineering process like that which leads to the Intel chips was disorganized from the viewpoint of the underlying graph of the chip), whereas expanders are what we  come up with when try to optimize for certain parameters of the network.  

---

