5
$\begingroup$

small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big Data techniques/ 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 are far older 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
$\endgroup$

1 Answer 1

8
$\begingroup$

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...)

$\endgroup$
2
  • $\begingroup$ 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... $\endgroup$
    – vzn
    Jul 11, 2014 at 19:11
  • 6
    $\begingroup$ @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. $\endgroup$ Jul 11, 2014 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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