Social group sizes

This is a small exercise on statistical acquaintance between persons within small worlds.

Suppose we have a group with N members and friendship relations, one connecting two members, such that at average each member has n friendship links. We suppose that the friendship relations are random in such a way that the two endpoints of the links are chosen randomly with equal probability from the set of members. We thus choose the pairs of endpoints for N*n/2 links randomly; if a pair has occurred already, we try again.

Our question now is: For given N and n, how many members are within a 2-link neighborhood (friend of a friend) for an average member.

Below you find a php script which calculates these results:

n = 5, N = 50, neighbors within 2 links: 23.4
n = 5, N = 100, neighbors within 2 links: 26.8
n = 5, N = 150, neighbors within 2 links: 28.1
n = 5, N = 200, neighbors within 2 links: 28.7
n = 5, N = 250, neighbors within 2 links: 29.2
n = 5, N = 300, neighbors within 2 links: 29.5
n = 5, N = 350, neighbors within 2 links: 29.6
n = 5, N = 400, neighbors within 2 links: 29.9
n = 5, N = 450, neighbors within 2 links: 30.0
n = 5, N = 500, neighbors within 2 links: 30.0
n = 10, N = 50, neighbors within 2 links: 45.1
n = 10, N = 100, neighbors within 2 links: 67.4
n = 10, N = 150, neighbors within 2 links: 78.8
n = 10, N = 200, neighbors within 2 links: 85.4
n = 10, N = 250, neighbors within 2 links: 89.9
n = 10, N = 300, neighbors within 2 links: 93.0
n = 10, N = 350, neighbors within 2 links: 95.3
n = 10, N = 400, neighbors within 2 links: 97.1
n = 10, N = 450, neighbors within 2 links: 98.5
n = 10, N = 500, neighbors within 2 links: 99.7
n = 15, N = 50, neighbors within 2 links: 49.7
n = 15, N = 100, neighbors within 2 links: 91.5
n = 15, N = 150, neighbors within 2 links: 120.5
n = 15, N = 200, neighbors within 2 links: 140.6
n = 15, N = 250, neighbors within 2 links: 155.1
n = 15, N = 300, neighbors within 2 links: 166.0
n = 15, N = 350, neighbors within 2 links: 174.5
n = 15, N = 400, neighbors within 2 links: 181.3
n = 15, N = 450, neighbors within 2 links: 186.9
n = 15, N = 500, neighbors within 2 links: 191.5
n = 20, N = 50, neighbors within 2 links: 50.0
n = 20, N = 100, neighbors within 2 links: 98.7
n = 20, N = 150, neighbors within 2 links: 141.3
n = 20, N = 200, neighbors within 2 links: 176.0
n = 20, N = 250, neighbors within 2 links: 204.1
n = 20, N = 300, neighbors within 2 links: 226.7
n = 20, N = 350, neighbors within 2 links: 245.3
n = 20, N = 400, neighbors within 2 links: 260.8
n = 20, N = 450, neighbors within 2 links: 273.8
n = 20, N = 500, neighbors within 2 links: 285.0
n = 25, N = 50, neighbors within 2 links: 50.0
n = 25, N = 100, neighbors within 2 links: 99.9
n = 25, N = 150, neighbors within 2 links: 148.3
n = 25, N = 200, neighbors within 2 links: 192.6
n = 25, N = 250, neighbors within 2 links: 231.8
n = 25, N = 300, neighbors within 2 links: 266.2
n = 25, N = 350, neighbors within 2 links: 296.0
n = 25, N = 400, neighbors within 2 links: 322.0
n = 25, N = 450, neighbors within 2 links: 344.5
n = 25, N = 500, neighbors within 2 links: 364.5
n = 30, N = 50, neighbors within 2 links: 50.0
n = 30, N = 100, neighbors within 2 links: 100.0
n = 30, N = 150, neighbors within 2 links: 149.7
n = 30, N = 200, neighbors within 2 links: 198.2
n = 30, N = 250, neighbors within 2 links: 244.2
n = 30, N = 300, neighbors within 2 links: 286.8
n = 30, N = 350, neighbors within 2 links: 325.9
n = 30, N = 400, neighbors within 2 links: 361.4
n = 30, N = 450, neighbors within 2 links: 393.6
n = 30, N = 500, neighbors within 2 links: 422.9
n = 35, N = 50, neighbors within 2 links: 50.0
n = 35, N = 100, neighbors within 2 links: 100.0
n = 35, N = 150, neighbors within 2 links: 150.0
n = 35, N = 200, neighbors within 2 links: 199.7
n = 35, N = 250, neighbors within 2 links: 248.5
n = 35, N = 300, neighbors within 2 links: 295.7
n = 35, N = 350, neighbors within 2 links: 340.7
n = 35, N = 400, neighbors within 2 links: 383.2
n = 35, N = 450, neighbors within 2 links: 423.1
n = 35, N = 500, neighbors within 2 links: 460.3

This means, e.g. that in a group of 400 people, if an average person has 30 friends, then 361.4 people are either his/her direct friends, or friends of a friend.

And here is the script:

<?php class TrustNet { /** * number of group members * * groups members will be numbered from 1..$N */ var $N; /** * average number of trust links connected to a person */ var $n; // altogether we have this number of trust links within the group var $L; /** * the trust net consists of different pairs of (different) group members * * the first entry of a pair is the smaller number */ var $trustNet = array(); // for calculation purposes we also build a symmetrized array with opposite links var $trustNetS = array(); public function __construct($N, $n) { $this->N = $N; $this->n = $n; $this->L = $this->N * $this->n / 2; $this->trustNet = $this->generateTrustNet($this->N, $this->L); $this->trustNetS = $this->trustNet; foreach ($this->trustNet as $pair) { $this->trustNetS[] = array($pair[1], $pair[0]); } //print_r($this->trustNet); //print_r($this->trustNetS); } /** * generate the trust net * by choosing two different nodes randomly and connecting them * (if the link does already exist, then try again) * * (in this way we automatically get members with many and members with few links; * here we implicitly choose a probability distribution) * @param $N number of group members * @param $L number of links */ public function generateTrustNet($N, $L) { $t = array(); for ($i = 0; $i < $L; $i++) { do { $m1 = mt_rand(1, $N); do { $m2 = mt_rand(1, $N); } while ($m1 == $m2); $min = min($m1, $m2); $max = max($m1, $m2); } while (in_array(array($min, $max), $t)); $t[] = array($min, $max); } return $t; } public function statistics() { // now do some statistics // echo "How many people do have how many trust links?\n"; // echo "Number of trust links => number of people; people with no links omitted\n"; $histogram1 = array(); $h1 = array(); foreach ($this->trustNetS as $pair) { $h1[] = $pair[0]; } //print_r($h1); $h2 = array_count_values($h1); ksort($h2); // this is how many trust links a member has //print_r($h2); $histogram1 = array_count_values($h2); ksort($histogram1); // print_r($histogram1); // echo "For each member: How many members are within a 2-link neighborhood\n"; // echo "id of the member => number of neighbors within 2 links\n"; // make a list of members within a 1-link neighborhood for ($i = 1; $i <= $this->N; $i++) { $zone1[$i] = array(); foreach ($this->trustNetS as $pair) { if ($pair[0] == $i) { $zone1[$i][] = $pair[1]; } } } // iterate the results to get the 2-link neighborhood $s = 0; for ($i = 1; $i <= $this->N; $i++) { $zone2[$i] = $zone1[$i]; foreach ($zone1[$i] as $neighbor1) { $zone2[$i] = array_merge($zone2[$i], $zone1[$neighbor1]); } $zone2[$i] = array_unique($zone2[$i]); $neighborCount = sizeof($zone2[$i]); //echo "member $i has $neighborCount neighbors within 1 or 2 links\n"; $s += $neighborCount; } return $s / $this->N; } } for ($n = 5; $n <= 35; $n += 5) { for ($N = 50; $N <= 500; $N += 50) { $sampleCount = 100; $s = 0; for ($i = 0; $i < $sampleCount; $i++) { $t = new TrustNet($N, $n); $s += $t->statistics(); } $avg = $s / $sampleCount; echo "n = $n, N = $N, neighbors within 2 links: " . sprintf( "%01.1f", $avg) . "\n"; } } ?>

See also wikipedia on Dunbar's number