2
\$\begingroup\$

Problem

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[1])
        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[0],e[1])
    print g.second_order_rank(1)
\$\endgroup\$
  • 1
    \$\begingroup\$ A person can be both a friend and a feiend's friend, I see no way these conditions are mutually exclusive \$\endgroup\$ – Caridorc Jan 24 '17 at 14:28
  • 2
    \$\begingroup\$ I would only write code to go "one level deeper" and use in a loop to go arbitrarly deep into the network. \$\endgroup\$ – Caridorc Jan 24 '17 at 14:29
  • \$\begingroup\$ @Caridorc, "see no way these conditions are mutually exclusive" -- for a person to be both friend and friend's friend, do you mean they should be 2nd degree connection, or not? \$\endgroup\$ – Lin Ma Jan 25 '17 at 2:24
  • 1
    \$\begingroup\$ Yes they should be \$\endgroup\$ – Caridorc Jan 25 '17 at 11:03
  • 1
    \$\begingroup\$ I do not know how to write it, , it was just an idea \$\endgroup\$ – Caridorc Jan 25 '17 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.