4

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

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

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

任何想法将不胜感激

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

我也可能已经简化了一点，但实际上用户可能是许多组的一部分（所以它更像是F->P(G)，其中P(G)是权力组，如果G），所以更好的算法将能够做到这一点。

4

1 回答 1

3

基本想法是尝试根据您的哪些朋友彼此是朋友来将它们分成组。

例如，如果您是 Bob，并且您认识 Sally 和 Larry，并且 Sally 和 Larry 都认识对方，那么他们可能在同一个“组”中。你还不知道那个团体是什么，但既然你们都认识对方，你们可能在同一个地方相遇——无论是工作、大学等。

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

建立组后，只需从组和可能不明确的节点中查询样本即可确定组的实际含义。

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

于 2009-11-04T22:07:10.723 回答