Find 2nd degree connections ( friends’ friends), output these 2nd degree connections ranked by number of common friends (i.e 1st degree connections) with you, (example: if 2nd degree connection A has 10 common friends (1st degree connections) with you but 2nd degree connection B has 8 common friends (1st degree connections)with you, then A should be ranked first) Input is your connection graph represented by undirected graph nodes, output is list of 2nd degree connections represented by graph nodes.
My current solution is to find all first degree connection, and then for each first degree connection, I try to find true (i.e. not overlapped with first degree connection) second degree connection, and build a common connection (between self, and 2nd degree connection) frequency dictionary. Finally, I sort the dictionary by frequency.
I'm wondering if any advice of more efficient implementation (in terms of algorithm time complexity), bugs in my code and code style advice. I am thinking of using BFS could improve performance (in terms of algorithm time complexity) for this problem.
from collections import defaultdict class Graph: def __init__(self): self.out_neighbour = defaultdict(list) def add_edge(self, from_node, to_node): self.out_neighbour[from_node].append(to_node) self.out_neighbour[to_node].append(from_node) def second_order_rank(self, from_node): first_order_set = set() for n in self.out_neighbour[from_node]: first_order_set.add(n) second_order_rank = defaultdict(int) # key: node id, value: count of common first order connection for first_order_node in self.out_neighbour[from_node]: for second_order_node in self.out_neighbour[first_order_node]: if second_order_node == from_node or second_order_node in first_order_set: continue for second_order_neighbour in self.out_neighbour[second_order_node]: if second_order_neighbour in first_order_set: second_order_rank[second_order_node] += 1 rank_order =  for n,c in second_order_rank.items(): rank_order.append((c,n)) rank_order = sorted(rank_order, reverse=True) result =  for r in rank_order: result.append(r) return result if __name__ == "__main__": g = Graph() edges = [(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,6),(4,7),(4,10),(5,9),(6,8)] for e in edges: g.add_edge(e,e) print g.second_order_rank(1)