Create a directed graph and compute in degrees in Python
In make_complete_graph, the inner loop could be written with a list comprehension:

result[i] = set([num for num in range(num_nodes) if num != i])


In compute_in_degrees, instead of iterating over all nodes for all nodes x to find links going to x, you could build a dictionary of counts easier:

counts = dict([(x, 0) for x in digraph])
for targets in digraph.values():
    for target in targets:
        counts[target] += 1