14
$\begingroup$

I am analyzing social networks (not virtual) and I am observing the connections between people. If a person would choose another person to connect with randomly, the number of connections within a group of people would be distributed normally - at least according to the book I am currently reading.

How can we know the distribution is Gaussian (normal)? There are other distributions such as Poisson, Rice, Rayliegh, etc. The problem with the Gaussian distribution in theory is that the values go from $-\infty$ to $+\infty$ (although the probabilities go toward zero) and the number of connections cannot be negative.

Does anyone know which distribution can be expected in case each person independently (randomly) picks-up another person to connect with?

$\endgroup$
  • 1
    $\begingroup$ Clarification: Is the question about the "total number of connections for the whole group" or "the total number of connections for one person"? My answer implicitly assumes the latter. $\endgroup$ – user28 Oct 28 '10 at 20:35
  • 1
    $\begingroup$ Riley distribution? That's a new one on me. Do you have a reference or link? $\endgroup$ – onestop Oct 28 '10 at 22:48
  • 3
    $\begingroup$ "Rayleigh" maybe? $\endgroup$ – whuber Oct 29 '10 at 1:11
6
$\begingroup$

When there are $n$ people and the number of connections made by person $i, 1 \le i \le n,$ is $X_i$, then the total number of connections is $S_n = \sum_{i=1}^n{X_i} / 2$. Now if we take the $X_i$ to be random variables, assume they are independent and their variances are not "too unequal" as more and more people are added to the mix, then the Lindeberg-Levy Central Limit Theorem applies. It asserts that the cumulative distribution function of the standardized sum converges to the cdf of the normal distribution. That means roughly that a histogram of the sum will look more and more like a Gaussian (a "bell curve") as $n$ grows large.

Let's review what this does not say:

  • It does not assert that the distribution of $S_n$ is ever exactly normal. It can't be, for the reasons you point out.

  • It does not imply the expected number of connections converges. In fact, it must diverge (go to infinity). The standardization is a recentering and rescaling of the distribution; the amount of rescaling is growing without limit.

  • It says nothing when the $X_i$ are not independent or when their variances change too much as $n$ grows. (However, there are generalizations of the CLT for "slightly" dependent series of variables.)

$\endgroup$
  • $\begingroup$ Note that I do not interpret the question to state that everyone chooses exactly one other person to connect to--that would lead to a sterile theory because the number of connections would be determined, not random. Instead I have interpreted it to state that everyone when they enter the network chooses connections randomly among the n others, winding up with anywhere from 0 through n connections total. The assumption on the variances is assured when there is a limit on the number of connections any newcomer will make and that number has some "minimal" randomness. $\endgroup$ – whuber Oct 28 '10 at 20:30
  • $\begingroup$ I'm a bit confused about $X_{i}$ and the variance. Does this suggest people have an intrinsic variance? $\endgroup$ – Andy W Oct 28 '10 at 23:56
  • 1
    $\begingroup$ @Andy Not people: the number of connections made. The important thing is that there should be a good chance that the number of connections made by individuals actually varies and doesn't settle down to a constant. When that happens, the limiting distribution (of the number of connections) is determined by the finite number of initial connections that do vary, so it's not possible to approach a Normal distribution asymptotically. $\endgroup$ – whuber Oct 29 '10 at 1:14
1
$\begingroup$

The answer is dependent on the assumptions that you are willing to make. A social network constantly evolves over time and hence is not a static entity. Therefore, you need to make some assumptions about how the network evolves over time.

The trivial answer under the stated conditions is: If the network size is $n$ then as asymptotically (in the sense of 'as time goes to infinity')

$Prob(\mbox{No of connections for any individual} = n-1) =1$.

If a person selects another person at random to connect to then eventually everyone will be connected.

However, real life networks do not behave this way. People differ in several aspects.

  1. At any time a person has a fixed network size and the probability of another connection being made is a function of his/her network size (as people introduce other people etc).

  2. A person has his/her own intrinsic tendency to form a connection (as some are introvert/exterovert etc).

These probabilities change over time, context etc. I am not sure there is a straightforward answer unless we make some assumptions about the structure of the network (e.g., density of the network, how people behave etc).

$\endgroup$
  • $\begingroup$ @Srikant Could you explain how you derive the "trivial answer"? (There must be some unstated assumptions behind it.) And to what theorem do you refer when you conclude that "eventually everyone will be connected"? That's not at all obvious! $\endgroup$ – whuber Oct 28 '10 at 20:26
  • $\begingroup$ @whuber I am assuming that the network size is fixed. The question states: A person picks another person at random to make a connection and presumably this is an ongoing process. Thus, as time goes to infinity everyone should be connected. No theorem, just intuition. Perhaps, I am using imprecise language. $\endgroup$ – user28 Oct 28 '10 at 20:29
  • $\begingroup$ @Srikant I am still confused, because after a long time, "Prob(No of connections=n)" equals 1 when n = 3 and otherwise is always zero. After all, when "everyone should be connected" the number of connections equals n(n-1)/2. I suspect you may have several different random processes in mind at the same time. It could help to disclose the assumptions you are making and be a little more precise. $\endgroup$ – whuber Oct 28 '10 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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