This is my Pyhton's solution for the problem Actor Centrality from CS215 Algorithms class on Udacity

cs215_ps4-6_actor_centrality.py

import csv

def make_link(G, node1, node2):
    if node1 not in G:
        G[node1] = set()
    G[node1].add(node2)
    if node2 not in G:
        G[node2] = set()
    G[node2].add(node1)
    return G

def read_graph(filename):
    tsv = csv.reader(open(filename), delimiter='\t')
    G = {}
    actors = set()
    for (actor, movie, year) in tsv:
        make_link(G, actor, movie + '(' + year + ')')
        actors.add(actor)
    return G, actors

def encode(actors_graph, actors):
    dkey = []
    new_actors_graph = [None] * len(actors_graph)
    string_to_index = {}
    for node in actors_graph:
        if node not in string_to_index:
            string_to_index[node] = len(dkey)
            dkey.append(node)
    for name in string_to_index:
        if name in actors:
            actors.remove(name)
            actors.add(string_to_index[name])
        edges = []
        for edge in actors_graph[name]:
            edges.append(string_to_index[edge])
        new_actors_graph[string_to_index[name]] = tuple(edges)
    return dkey, new_actors_graph

def centrality(G, v):
    total_distance = 0
    open_list = [(v, 0)]
    visited = [False] * len(G)
    visited[v] = True
    idx = 0
    while idx < len(open_list):
        current, distance = open_list[idx]
        total_distance += distance
        idx += 1
        for neighbor in G[current]:
            if not visited[neighbor]:
                open_list.append((neighbor, distance+1))
                visited[neighbor] = True
    return total_distance/float(idx)

def compute_centralities(G, actors):
    C = {}
    for actor in actors:
        C[actor] = centrality(G, actor)
    return C

actors_graph, actors = read_graph("imdb-1.tsv")
decryption_key, actors_graph = encode(actors_graph, actors)
centrs = compute_centralities(actors_graph, actors)

twentieth_actor = sorted(centrs.items(), key = lambda item: item[1])[19]
print "rank 20: %s centrality=%.3f" % (decryption_key[twentieth_actor[0]], twentieth_actor[1])