algorithm - 对社交网络中的 friend 进行分类

Question

我面临以下问题:
假设 u 是社交网络用户，因此有一个 friend 列表 F(u)。 partition 是函数 F->G，其中 G 是一组组，例如高中、大学、工作等' .
我需要想出算法来分割F:

• 对于 F 中的每个 f，输入是 F 和 F(f)(列表u 的每个 friend 的 friend )。
• 在运行过程中，允许算法提出 u 个问题(例如“对于某些特定用户 v 来说最好的组是什么？”)。
• 问题的数量应保持在最低限度(最低限度并不是一个明确的数字，但我会说 5% 的 friend 数量似乎是正确的)。

显然生成的分区不是最优的，但它应该可以作为以后改进的起点。

任何想法将不胜感激

编辑:不，这不是家庭作业。我相信家庭作业会有更明确的要求和目标功能。无论如何不，这实际上是我面临的现实世界问题。

另外我可能已经简化了一点，但实际上一个用户可能是许多组的一部分(所以它更像是F->P(G)，其中P(G ) 是 G) 的幂组，因此更好的算法可以做到这一点。

Answer 1

基本的想法是尝试根据您的哪些 friend 是彼此的 friend 将他们分成几组。

例如，如果您是 Bob，并且认识 Sally 和 Larry，并且 Sally 和 Larry 彼此认识，那么他们很可能在同一个“组”中。你还不知道那群人是什么，但因为你们都认识，所以你们可能在同一个地方见过面 - 无论是工作、大学等。

您可以将其实现为有向图，其中节点是人，边是连接。然后，您需要根据这些节点的连接程度将它们分组在一起。

一旦您建立了群组，接下来只需查询群组中的样本和可能不明确的节点即可确定群组的实际情况。

听起来像是家庭作业，所以我不会放弃任何其他东西，但这应该让你开始。