Describe the problem as a graph problem. I've tried to modify the breadth first search algorithm, but haven't gotten anywhere. Any ideas?
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.
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.
Rather than breadth first search, start with depth first search.
- Select your first user , your starting node. This is "Bob".
- Go to a random friend. This is "Alice".
- 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".
- 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.
- 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.
- 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.