12
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – András Salamon
    Commented Nov 20, 2016 at 11:39
  • $\begingroup$ 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. $\endgroup$
    – Zur Luria
    Commented Nov 21, 2016 at 7:06

2 Answers 2

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

Power-law graphs are arguably good models for social network graphs. This paper by Gkantsidis, Mihail, and Saberi shows that power-law graphs are expanders.

Improve this answer
$\endgroup$
1

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.