Bookmark and Share

Computing degrees of separation in social networking.

Posted: Friday, January 9th, 2009 at 6:31 amUpdated: Friday, January 30th, 2009 at 10:08 pm

As the final question in one of my interviews a while ago, I was asked to compute the average degrees of separation in social networking site. If you don’t know what degree of separation, here’s an example.

Amy is a friend of Robert. Therefore, Amy and Robert are 1st degree friend. Robert is a friend of James. Therefore, Amy and James are 2nd degree friend through their common friend Robert. Below is a small example of 5 people identified by number 0 – 4.

A ←→ D
A ←→ C
B ←→ D
B ←→ E
B ←→ C
C ←→ E
C ←→ D

In the above case, A and D are separated by one degree. A and E are separated by 2 degree since they are both friends of C. A and E can also be connected through A ←→ D ←→ B ←→ E for 3 degreees separation. However, we want to know the closest separation. Now calculating all the relationship degree on the above example, the average degree of separation is 1.3. Consult the table below and add the numbers, you’ll end up with 13. There are 10 connections. So average is 1.3. Actually, if you add the numbers, it adds up to 26 for 20 connections for the same average of 1.3. However, if you calculate all the numbers, you’ll be double counting as you’re counting the degree of A ←→ B and B ←→ A.

  A B C D E
A 0 2 1 1 2
B 2 0 1 1 1
C 1 1 0 1 1
D 1 1 1 0 2
E 2 1 1 2 0

Ok now that the stage is set, find the average degree of separation on the following user data. The user is identified by user 0 to 99.

0 ←→ 70   15 ←→ 93   25 ←→ 62   36 ←→ 85   48 ←→ 79   64 ←→ 90
1 ←→ 2   15 ←→ 79   25 ←→ 72   36 ←→ 83   48 ←→ 63   64 ←→ 95
1 ←→ 46   15 ←→ 63   25 ←→ 97   36 ←→ 52   48 ←→ 56   64 ←→ 75
1 ←→ 99   15 ←→ 94   25 ←→ 40   36 ←→ 96   48 ←→ 99   65 ←→ 73
1 ←→ 59   15 ←→ 59   25 ←→ 99   36 ←→ 74   48 ←→ 96   65 ←→ 75
1 ←→ 78   15 ←→ 51   26 ←→ 86   36 ←→ 76   49 ←→ 93   65 ←→ 80
2 ←→ 55   15 ←→ 74   26 ←→ 94   37 ←→ 79   49 ←→ 89   66 ←→ 83
2 ←→ 34   16 ←→ 63   26 ←→ 96   37 ←→ 54   49 ←→ 50   66 ←→ 68
3 ←→ 89   16 ←→ 50   27 ←→ 77   37 ←→ 78   49 ←→ 66   66 ←→ 91
3 ←→ 95   16 ←→ 90   27 ←→ 90   38 ←→ 42   49 ←→ 78   66 ←→ 85
3 ←→ 26   16 ←→ 23   27 ←→ 64   38 ←→ 39   49 ←→ 74   66 ←→ 79
3 ←→ 21   17 ←→ 30   27 ←→ 71   38 ←→ 67   50 ←→ 61   66 ←→ 71
3 ←→ 75   17 ←→ 86   28 ←→ 67   38 ←→ 73   50 ←→ 81   67 ←→ 83
4 ←→ 21   17 ←→ 39   28 ←→ 94   38 ←→ 68   50 ←→ 97   67 ←→ 68
4 ←→ 41   17 ←→ 50   28 ←→ 92   38 ←→ 91   50 ←→ 58   67 ←→ 92
4 ←→ 96   17 ←→ 72   28 ←→ 74   38 ←→ 58   51 ←→ 62   68 ←→ 85
5 ←→ 85   17 ←→ 88   28 ←→ 76   39 ←→ 85   51 ←→ 77   68 ←→ 83
5 ←→ 60   17 ←→ 96   28 ←→ 80   39 ←→ 99   51 ←→ 87   68 ←→ 86
5 ←→ 26   17 ←→ 70   29 ←→ 93   39 ←→ 49   51 ←→ 80   68 ←→ 96
5 ←→ 99   18 ←→ 85   29 ←→ 86   40 ←→ 86   52 ←→ 79   68 ←→ 91
6 ←→ 65   18 ←→ 40   29 ←→ 69   40 ←→ 45   52 ←→ 84   68 ←→ 80
6 ←→ 64   18 ←→ 41   29 ←→ 90   41 ←→ 73   52 ←→ 91   69 ←→ 94
6 ←→ 91   19 ←→ 83   29 ←→ 31   41 ←→ 66   53 ←→ 85   69 ←→ 87
6 ←→ 76   19 ←→ 73   29 ←→ 98   41 ←→ 84   53 ←→ 69   69 ←→ 96
7 ←→ 63   19 ←→ 94   29 ←→ 76   41 ←→ 46   53 ←→ 56   70 ←→ 75
7 ←→ 48   19 ←→ 64   30 ←→ 62   41 ←→ 54   53 ←→ 88   70 ←→ 87
8 ←→ 77   19 ←→ 27   30 ←→ 83   42 ←→ 86   54 ←→ 73   70 ←→ 91
8 ←→ 69   19 ←→ 98   30 ←→ 90   42 ←→ 44   54 ←→ 88   71 ←→ 89
8 ←→ 98   19 ←→ 92   30 ←→ 56   42 ←→ 69   54 ←→ 99   71 ←→ 96
8 ←→ 75   20 ←→ 50   30 ←→ 74   42 ←→ 90   54 ←→ 70   72 ←→ 81
9 ←→ 29   20 ←→ 90   30 ←→ 91   42 ←→ 61   55 ←→ 85   72 ←→ 94
9 ←→ 73   20 ←→ 64   30 ←→ 58   42 ←→ 95   55 ←→ 73   72 ←→ 82
9 ←→ 75   20 ←→ 66   30 ←→ 80   42 ←→ 91   55 ←→ 57   72 ←→ 88
10 ←→ 83   20 ←→ 97   31 ←→ 63   42 ←→ 78   56 ←→ 85   72 ←→ 96
10 ←→ 39   21 ←→ 62   31 ←→ 66   43 ←→ 86   56 ←→ 64   72 ←→ 74
10 ←→ 90   21 ←→ 63   31 ←→ 82   43 ←→ 62   56 ←→ 95   73 ←→ 84
10 ←→ 81   21 ←→ 86   31 ←→ 96   43 ←→ 57   56 ←→ 82   73 ←→ 91
10 ←→ 27   21 ←→ 67   31 ←→ 92   43 ←→ 98   56 ←→ 59   74 ←→ 93
10 ←→ 20   21 ←→ 99   31 ←→ 80   43 ←→ 84   57 ←→ 60   74 ←→ 77
10 ←→ 51   21 ←→ 96   32 ←→ 73   43 ←→ 52   57 ←→ 97   74 ←→ 99
10 ←→ 74   21 ←→ 70   32 ←→ 61   43 ←→ 47   57 ←→ 68   76 ←→ 94
11 ←→ 50   22 ←→ 85   32 ←→ 95   43 ←→ 68   57 ←→ 96   76 ←→ 98
11 ←→ 73   22 ←→ 93   32 ←→ 97   44 ←→ 94   58 ←→ 96   77 ←→ 86
11 ←→ 90   22 ←→ 77   32 ←→ 92   44 ←→ 52   59 ←→ 83   77 ←→ 88
11 ←→ 94   22 ←→ 44   32 ←→ 48   44 ←→ 71   59 ←→ 65   77 ←→ 96
11 ←→ 52   22 ←→ 61   33 ←→ 57   44 ←→ 48   59 ←→ 78   78 ←→ 91
11 ←→ 51   22 ←→ 80   33 ←→ 94   44 ←→ 70   59 ←→ 70   79 ←→ 98
11 ←→ 87   23 ←→ 28   33 ←→ 51   45 ←→ 62   60 ←→ 93   79 ←→ 82
11 ←→ 32   23 ←→ 84   34 ←→ 85   45 ←→ 57   60 ←→ 65   79 ←→ 96
12 ←→ 73   23 ←→ 36   34 ←→ 95   45 ←→ 84   60 ←→ 69   80 ←→ 86
12 ←→ 39   23 ←→ 59   34 ←→ 98   45 ←→ 77   60 ←→ 64   80 ←→ 97
12 ←→ 64   23 ←→ 74   34 ←→ 36   45 ←→ 67   60 ←→ 66   81 ←→ 93
12 ←→ 97   24 ←→ 29   34 ←→ 59   45 ←→ 95   60 ←→ 99   81 ←→ 83
12 ←→ 35   24 ←→ 66   34 ←→ 51   45 ←→ 64   60 ←→ 70   81 ←→ 96
13 ←→ 16   24 ←→ 43   34 ←→ 78   45 ←→ 49   61 ←→ 83   82 ←→ 99
13 ←→ 99   24 ←→ 84   35 ←→ 66   45 ←→ 96   61 ←→ 63   83 ←→ 84
14 ←→ 63   24 ←→ 41   35 ←→ 40   45 ←→ 53   61 ←→ 73   83 ←→ 85
14 ←→ 90   24 ←→ 99   35 ←→ 52   45 ←→ 51   61 ←→ 72   83 ←→ 92
14 ←→ 72   24 ←→ 46   35 ←→ 36   45 ←→ 76   61 ←→ 68   84 ←→ 87
14 ←→ 46   24 ←→ 32   35 ←→ 47   46 ←→ 73   62 ←→ 64   85 ←→ 96
14 ←→ 49       35 ←→ 53   46 ←→ 84   62 ←→ 91   86 ←→ 94
        35 ←→ 76   46 ←→ 70   62 ←→ 70   89 ←→ 95
        35 ←→ 78   47 ←→ 83   63 ←→ 93   89 ←→ 98
            47 ←→ 56   63 ←→ 84   89 ←→ 97
            47 ←→ 66       90 ←→ 91
                    91 ←→ 97
                    91 ←→ 98
                    92 ←→ 94
                    98 ←→ 99

Once again, the question is, what is the average degree of separation on the social network relationship on the above table? Well, try to work on it first … then go to page 2 for one possible solution.

Pages: 1 2

3 Responses to “Computing degrees of separation in social networking.”

  1. james Says:

    hi
    i want to know which platform will handle larger and quicker searches (PHP or SQL)?

    also do u have implementations of BFS and DFS in POSTGRESQL.

    Great Work
    thanks

  2. deepak Says:

    Degree pf seperation required in c programing code

  3. deepak Says:

    really good

Leave a Reply