Describe the problem as a graph problem. I've tried to modify the breadth first search algorithm, but haven't gotten anywhere. Any ideas?

  • $\begingroup$ Welcome to CS.SE! Please don't put your main question solely in the title. The main content belongs in the body; the title should be a short summary. We have collected some advice here. Also, if you can give us additional context and tell us where you ran across this problem or why you want to solve it, we might be able to give you more useful answers. $\endgroup$
    – D.W.
    Nov 25 '16 at 16:36

This is the Maximum Clique problem, one of the canonical NP-complete problems. On general graphs it probably cannot be solved efficiently, though social networks, with their very particular structures, may lend themselves to more efficient solutions.

  • $\begingroup$ Was not sure how nobody mentioned clique, thought i may we losing it. $\endgroup$
    – Ariel
    Nov 25 '16 at 11:19

You might try finding The strongly connected components , By using modelling the connections as a directed graph and using DFS for the same.

The DFS on directed graphs produces a DAG of strongly connected components . Finding the largest group from this group of connected components is going to take linear time in terms of number of vertices.

  • $\begingroup$ So the largest group of people will be strongly connected component with maximum number of vertexes in it? $\endgroup$ Nov 25 '16 at 8:46
  • 1
    $\begingroup$ I would think that the problem rather asks for a maximum size clique. $\endgroup$ Nov 25 '16 at 9:07

Rather than breadth first search, start with depth first search.

  1. Select your first user , your starting node. This is "Bob".
  2. Go to a random friend. This is "Alice".
  3. This is the modified step. In a list store the nodes you have visited, now it's only "Bob". In Alice's friends search the ones who are also friends with everyone in the list. Go to one of them. This is "Kate".
  4. Now you have "Bob" and "Alice" in your list. Repeat Step 3 for Kate. If Kate does not have any mutual friends return back to Alice and select another friend. Don't add Kate to list. (Depth First Algorithm). In each backtracking save the maximum number of people in list. Change it if you have a new maximum.
  5. In you final step, you won't have anyone who has an unvisited friend that is also friends with everyone in the list. At that step, add the last person and save your list. This list certainly has Bob, and the biggest group that Bob is in. That's why you save the maximum count.
  6. You have to repeat this step for everyone and get the list with maximum number of elements. Someone in one list can also be in another list, so you have to run this for everyone. This step can be improved

You can also check whether a group has the maximum number of people by comparing it with the total number of friendship relations(edges) in the graph. I believe that this whole process can be shortened by using the data from previous groups. For example, after the first run, you will have the biggest group that Bob is in, in your second run you can bypass visiting Bob.

  • For example if you have a group that has more people than the half of the whole population, it's maximum.

This solution is open to objection and faster algoritms, but if you have enough time or your database is not huge, this algorithm gives you the right answer.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.