Algorithm for finding strongest connection for a user on social network

Question

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()

    # source is already discovered
    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
    
        for current_node in graph.adj[parent_node]:
            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.

Answer 1

Your algorithm doesn't work. BFS doesn't explore all paths. One of the paths you haven't explored might have much higher strength than all the ones you have explored. There exists a counterexample with only four or five nodes (depending on the exact details of how you implement the steps outlined in your overview). I'll let you have the fun of finding it.