#### 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 provide direct support for graphs as a data type. Python for instance does not have a graph data structure. However, graphs can be built out of

**lists and dictionaries**. For instance, here is the Python code to represent the connections from the above graph:

1 2 3 4 5 6 7 8 9 |
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 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.

The full dictionary with all the members of our social network can be found in the Python trinket below.

#### Shortest Path Algorithm

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def find_shortest_path(graph, start, end, shortestLength=-1, path=[]): path = path + [start] if start == end: return path if not graph.has_key(start): 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 lenght of the chain).