在社交网络中的朋友进行分类

Question

我现在面临寿以下问题：
假设ü是社交网络用户，因此有很多朋友，F（U）列表。 分区是函数F-> G，其中G是一组组，如高中，大学，工作等。
我需要拿出算法三方˚F：

• 输入是˚F也F（F）在为每˚F˚F（的朋友列表每个或的朋友）。
• 运行过程中允许算法询问ü问题（例如“什么是某些特定用户的最佳群体v？”）。
• 问题的数量应该保持在最小值（什么是最小值不是一个真正的数字，但我认为5％的朋友的数量似乎是正确的）。

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

任何想法，将不胜感激

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

也i可以具有简化的有点，但在现实中，用户可以是许多基团的一部分（这样它更像F-> P（G），其中P（G）是功率组如果G），所以更好的算法将能够做到这一点。

Answer 1

的基本想法是尝试将它们划分成基于组上你的朋友是朋友彼此。

例如，如果你是鲍勃，你知道Sally和拉里和Sally和拉里都知道对方，他们很可能是在同一个“组”。你不知道那团是什么呢，不过既然你都知道对方，你可能是在同一个地方见面 - 不管是工作，大学等

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

一旦你建立了组，那么它只是一个查询从群体和潜在的暧昧节点样本找出组实际上是问题。

听起来像功课，所以我不会放弃任何东西，但应该让你开始。