Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

From the wikipedia article on percolation it appears that the theory is applicable to graphs in general, and this presentation describes the theory nicely. This review article on complex networks discusses how measures of percolation apply to complex networks in general but the background could be discussed in more depth for newcomers with little knowledge in physics.

I do not think that the social networks can be compared to the lattice percolation models because of their community structure.

I would like to know:

  1. How is percolation defined for social networks? and what is the intuitive explanation/description for it in layman's terms?
  2. With which methods can the percolation of a social network (graphs) be measured and what features of the network do these measurements represent?
  3. What are other measures for social networks conductivity that are similar to percolation?
  4. Are social networks 3D lattices due to the community sparsity and how is that modeled (eg. edges between lattices)?
share|cite|improve this question
You keep mentioning "social networks" but then parenthesis them as graphs. So, are you interested in how percolation works on graphs? – Alex R. Aug 12 '13 at 16:05
@Alex, I am interested in graphs of social networks. – Vass Aug 12 '13 at 23:00
Could you outline what you define as a social network? The point is, percolation is perfectly well defined on graphs, for example Erdos Renyi random graphs. So, when you say "social network" are you referring to some class of random graphs? For example, there are random models where the degrees of vertices are distributed according to a power law. There's also vast generalizations of percolation on graphs, for example with random weights, directed percolation etc. If you search on google for "social network percolation" there's a vast number of results. Could you specialize to a few of them? – Alex R. Aug 12 '13 at 23:39
@AlexR. random graphs with high degree of community structure. Sparsely connected random graphs – Vass Aug 13 '13 at 21:13
up vote 2 down vote accepted

To rigorously answer the question we need some concept of a social network in the limit as the number of nodes $N$ approaches $\infty$. Then percolation is the same as any other system - is there a $p$ such that if we keep bonds (or sites) with probability $p$ we end up with an infinite connected component.

In practice of course, our social networks are finite. Often, but not always, there is significant clustering (the existence of short cycles). So really, what we look for is a transition in which at some $p$ the size of the largest component switches from being $O(\log N)$ to $O(N)$.

Sometimes we use a degree distribution and then either the configuration model network class (aka Molloy-Reed) or the Chung-Lu network class. In these cases, we can rigorously calculate a condition under which the network percolates.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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