# Algorithm for finding strongest connection for a user on social network

I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as:

Problem 6-1. [30 points] I Can Haz Moar Frendz?

Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a burgeoning social network website. She needs to implement a new friend suggestion feature. For two friends u and v (friendship is undirected), the EdgeRank ER(u, v) can be computed in constant time based on the interest u shows in v (for example, how frequently u views v’s profile or comments on v’s wall). Assume that EdgeRank is directional and asymmetric, and that its value falls in the range (0, 1). A user u is connected to a user v if they are connected through some mutual friends, i.e., $$u = u_0$$ has a friend $$u_1$$, who has a friend $$u_2$$, . . . , who has a friend $$u_k = v$$. The integer k is the vagueness of the connection. Define the strength of such a connection to be $$S(p) = \prod_{i=1}^kER(u_{i−1}, u_i)$$ For a given user s, Alyssa wants to have a way to rank potential friend suggestions according to the strength of the connections s has with them. In addition, the vagueness of those connections should not be more than k, a value Alyssa will decide later.

Help Alyssa by designing an algorithm that computes the strength of the strongest connection between a given user s and every other user v to whom s is connected with vagueness at most k, in O(kE + V) time (i.e., for every pair of s and v for v ∈ V\{s}, compute the strength of the strongest connection between them with vagueness at most k). Assume that the network has |V| users and |E| friend pairs. Analyze the running time of your algorithm. For partial credit, give a slower but correct algorithm. You can describe your algorithm in words, pseudocode or both.

After reading the problem, the first intuition I got is to:

• Do a BFS from the source node s and stop the BFS as soon as kth level is reached.
• And, while doing the BFS, calculate and maintain the strength that each node encountered has with s
• At the end, when the BFS stops after the k levels, we iterate the strengths stored, and find the one with maximum value.

Here is the (pseudo/Python)code for the same:

def find_strongest_connection(graph, source_node, k):
nodes_discovered = deque()

strengths = {source_node: 1}
parents, levels = {source_node: None}, {source_node: 0}
nodes_discovered.append(source_node)

while nodes_discovered:
parent_node = nodes_discovered.popleft()

current_level = levels[parent_node] + 1
if current_level > k:
break

if current_node not in levels:
# current_node is now discovered
strengths[current_node] = strengths[parent_node] * ER(parent_node, current_node)
parents[current_node], levels[current_node] = parent_node, current_level
nodes_discovered.append(current_node)

strongest_connection, max_strength = None, -1
for connection, strength in strengths.items():
if strength > max_strength:
max_strength = strength
strongest_connection = connection

return strongest_connection, max_strength


To me, this solution looks correct. But when I was going through the solutions provided by MIT for the problem set, I see they are first transforming the graph, and then applying the Bellman-Ford's algorithm. What I want to know is that am I missing something really basic in my understanding of the problem and the algorithm that I have come up with?

I am asking this because seeing the complex solution provided in the solution set is making me doubt my overly simple solution. Unfortunately, I cannot think of a case, where my solution would fail. If there is any issue with my algorithm, any hint would be much much appreciated.

PS: I am not a student looking for an answer to my homework. I am a full time working professional.

• Have you tried to write a proof of correctness for your answer? That's the standard way that we know whether our algorithm is correct. – D.W. Apr 26 at 19:28
• okay, I will try to write a proof of correctness and will add it as an edit in the post. Thanks. – Vikas Prasad Apr 27 at 1:31