<p>Power-law graphs are arguably good models for social network graphs.
<a href="https://dl.acm.org/citation.cfm?id=781027.781046" rel="nofollow noreferrer">This paper</a> by Gkantsidis, Mihail, and Saberi shows that power-law graphs are expanders.</p>

CC BY-SA 4.0
2020-03-04T22:34:43.210Z
The idea that social networks are distributed like power laws has been recently contested by some highly rigorous analysis of data: https://www.nature.com/articles/s41467-019-08746-5
Stella Biderman
CC BY-SA 3.0
2018-02-25T13:09:59.027Z
2018-02-25T13:09:59.027Z
Thatchaphol
<p>Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap. </p>

<p>What you <em>could</em> hope for is good vertex/edge expansion for sufficiently large sets. However, if you have tightly-knit communities within the network, then again you would expect low expansion. </p>

<p>I'm not sure if it quite answers your question, but the following empirical paper looks at exactly expansion-like properties in social networks. The answer seems to vary from network to network.
<a href="http://fragkiskos.me/papers/expansion_SNSMW11.pdf" rel="noreferrer">http://fragkiskos.me/papers/expansion_SNSMW11.pdf</a></p>

<p>I'm sure there is other work out there along these lines, possibly disguised using alternate terminology ("community structure", cut sizes, etc).</p>

CC BY-SA 3.0
2016-11-29T16:04:46.920Z
2016-11-29T16:04:46.920Z
Adam Smith
<p>I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility of these graphs. One basic question is: Are these graphs typically good expander graphs?</p>

<p>Has anyone checked, say, the facebook graph's spectral gap? Or the spectral gap of other large real-world networks? I am hoping that someone can point me in the right direction to learn about this topic.</p>

CC BY-SA 3.0
2016-11-20T11:39:53.997Z
Since each step in an iterative eigenvalue algorithm for $n$ by $n$ matrices typically requires $cn^2$ steps, the graphs for which we can decide easily whether they are expanders are much smaller than the web scale graphs you ask about.  Even $n=10^5$ is a challenge.  However, social networks are quite special.  Essentially you are asking whether it is possible to approximate an eigenvalue in something like quasilinear time and quasilinear space in $n$, if the input graph is sparse and its vertex degrees follow a power law.
András Salamon
CC BY-SA 3.0
2016-11-21T07:06:26.133Z
Huh, I've been focused on theory for too long. It never even crossed my mind that the facebook graph might be so large that it might be infeasible to compute its spectral gap.
Zur Luria
<graph-theory><application-of-theory><expanders>
Are social networks typically good expanders?
Zur Luria
# Are social networks typically good expanders?

(Asked by: username_0 on 2016-11-18)

I am interested in the combinatorial properties of social networks as graphs. People have looked at things such as the distribution of the degrees, the clustering coefficient and the compressibility of these graphs. One basic question is: Are these graphs typically good expander graphs?

Has anyone checked, say, the facebook graph's spectral gap? Or the spectral gap of other large real-world networks? I am hoping that someone can point me in the right direction to learn about this topic.

**Tags:** graph-theory, application-of-theory, expanders
> **Comments:**
> **username_1**: Since each step in an iterative eigenvalue algorithm for $n$ by $n$ matrices typically requires $cn^2$ steps, the graphs for which we can decide easily whether they are expanders are much smaller than the web scale graphs you ask about.  Even $n=10^5$ is a challenge.  However, social networks are quite special.  Essentially you are asking whether it is possible to approximate an eigenvalue in something like quasilinear time and quasilinear space in $n$, if the input graph is sparse and its vertex degrees follow a power law.  
> **username_0**: Huh, I've been focused on theory for too long. It never even crossed my mind that the facebook graph might be so large that it might be infeasible to compute its spectral gap.  

---

## 2 answers

### Answer by username_4 on 2016-11-29. Score: 9 | Accepted answer

Social networks typically have many vertices with just one or two connections to the rest of the graph. Such vertices will typically lead to a bad spectral gap.

What you *could* hope for is good vertex/edge expansion for sufficiently large sets. However, if you have tightly-knit communities within the network, then again you would expect low expansion.

I'm not sure if it quite answers your question, but the following empirical paper looks at exactly expansion-like properties in social networks. The answer seems to vary from network to network.
<http://fragkiskos.me/papers/expansion_SNSMW11.pdf>

I'm sure there is other work out there along these lines, possibly disguised using alternate terminology ("community structure", cut sizes, etc).


---

### Answer by username_2 on 2018-02-25. Score: 1

Power-law graphs are arguably good models for social network graphs.
[This paper](https://dl.acm.org/citation.cfm?id=781027.781046) by Gkantsidis, Mihail, and Saberi shows that power-law graphs are expanders.

> **Comments:**
> **username_3**: The idea that social networks are distributed like power laws has been recently contested by some highly rigorous analysis of data: https://www.nature.com/articles/s41467-019-08746-5  

---

