The Social Network

Six Degrees of Separation

The Six degrees of separation is an idea that was originally set out by Frigyes Karinthy in 1929 and that can be applied to Social Networks such as Facebook.

It is based on the idea that all human beings in the world are six or fewer steps away from each other so that a chain of “a friend of a friend” statements can be made to connect any two people in a maximum of six steps.

Using a Graph:

In order to verify this concept, we are going to use a graph data structure where all the nodes of the graph will represent the members of a small social network that contains 100 members.

The connections between the nodes will represent the friendship relationships between two members.

We will then ask the end-user to enter 2 names and use an algorithm to find out the shortest friendship chain between these two members (if it exists).

Using Graphs in Python

Most programming languages do not necessary provide direct support for graphs as a data type. Python for instance does not have a graph data structure. However it is possible to create a graph data structure in python using any of the following two methods:

• Method 1: Adjacency Matrix: Using a 2D array (or list of lists in Pyhon)
• Method 2: Us: Using a hash table (dictionary) of lists

Let’s investigate both approaches.

Method #1: Implementing a graph using an adjacency matrix

An adjacency matrix is a 2D array that has the same number of rows and columns: 1 row and 1 column per node of the graph.

	Eshan	Sonia	Jackson	Naomi	Zheng	Kamal	Oliver	May
Eshan		✔						✔
Sonia	✔		✔
Jackson		✔		✔
Naomi			✔			✔		✔
Zheng						✔	✔
Kamal				✔	✔		✔
Oliver					✔	✔
May	✔			✔

Here is how we could implement this adjacency matrix in Python:

members =    ["Eshan","Sonia","Jackson","Naomi","Zheng","Kamal","Oliver","May"]

#Adjacency Matrix: (2D array to store friendship data)
friendship = [[False , True  , False   , False , False , False , False  , True ], #Eshan
              [True  , False , True    , False , False , False , False  , False], #Sonia
              [False , True  , False   , True  , False , False , False  , False], #Jackson
              [False , False , True    , False , False , True  , False  , True ], #Naomi
              [False , False , False   , False , False , False , False  , False], #Zheng
              [False , False , False   , True  , True  , False , True   , False], #Kamal
              [False , False , False   , False , True  , True  , False  , False], #Oliver
              [True  , False , False   , True  , False , False , False  , False]  #May
             ]

Now that we have saved this data into our code, we can create a small program to query this data. For instance, let’s write a program that asks the user to enter the names of two members of our social network and output whether these two members are friends or not.

Note that using an adjacency matrix is not recommended for very large graphs where you have two many nodes. This is because, for a graph of n nodes the resulting 2D array would contain n² values. This is can quickly be too demanding in terms of memory requirements (O(n²) Big O Notation)

Method #2: Implementing a graph using a hash table

An alternative approach to implement a graph is to use a hash table where each node of the graph is a key, and the value for each key is the list of adjacent nodes of this node. For instance, here is the Python code to represent the connections from our friendship graph:

members = {'Naomi': ['Jackson', 'May', 'Kamal'],
'May': ['Eshan', 'Naomi'],
'Jackson': ['Naomi', 'Sonia'],
'Kamal': ['Oliver', 'Naomi', 'Zheng'],
'Eshan': ['Sonia','May'],
'Sonia': ['Eshan','Jackson'],
'Zheng': ['Kamal','Oliver'],
'Oliver': ['Zheng','Kamal']
}

This graph is a hash table (a.k.a dictionary) where the keys are the nodes of the graph. For each key, the corresponding value is a list containing the nodes that are connected by a direct arc from this node.

Let’s see how we can use this graph to complete our friendship checker program:

Shortest Path Algorithm

Two find out the degrees of separations between two members of our social network, we will need to identify the shortest path between these two members (nodes). We will use a shortest path algorithm to do so, using a graph based on a hash table (method #2).

Our shortest path algorithm will be based on a recursive function used to find all the friendship chains/paths that can been found between two members and identify which one is the shortest path (The path that has the smallest number of nodes).

To make this algorithm more effective we also have a stopping condition to stop exploring a path that would be longer than the shortest path found so far.

def find_shortest_path(graph, start, end, shortestLength=-1, path=[]):
  path = path + [start]
  if start == end:
    return path
  if not start in graph:
    return None
  shortest = None
  for node in graph[start]:
    if node not in path:
      if shortestLength==-1 or len(path)<(shortestLength-1):
        newpath = find_shortest_path(graph, node, end, shortestLength, path)
        if newpath:
          if not shortest or len(newpath) < len(shortest):
            shortest = newpath
            shortestLength = len(newpath)  
  return shortest

Python Code

Check the code below used the find_shortest_path() algorithm to find the shortest path between two members. It is then used to calculate the degree of separation (based on the length of the chain).