对社交网络中的朋友进行分类
我面临以下问题：
假设 u 是社交网络用户，因此有一个朋友列表 F(u)。 partition 是一个函数 F->G，其中 G 是一组组，例如高中、大学、工作等'.
我需要想出一种算法来划分 F：
- 输入是 F 以及每个 fF(f) F 中的 b>（u 的每个朋友的朋友列表）。
- 在运行过程中，算法可以询问u问题（例如“对于某些特定用户v来说最好的组是什么？”）。
- 问题的数量应该保持在最低限度（最低限度并不是一个明确的数字，但我想说 5% 的朋友数量似乎是正确的）。
显然，生成的分区不是最佳的，但它应该可以作为后续改进的起点。
任何想法将不胜感激
编辑：不，这不是作业。我相信家庭作业会有更明确的要求和目标功能。无论如何，不，这实际上是我面临的现实世界问题。
我也可能稍微简化了它，但实际上用户可能是许多组的一部分（所以它更像是 F->P(G)，其中 P(G)< /strong> 是幂组（如果是G），因此更好的算法能够做到这一点。
I'm facing tho following problem:
let's say u is a social network user and as such has a list of friends, F(u). a partition is a function F->G, where G is a set of groups such as High-school, university, work, etc'.
I need to come up with algorithm to partite F:
- the input is F and also F(f) for every f in F (the list of friends for each of u's friends).
- during it's run the algorithm is allowed to ask u questions (for example "what is the best group for some specific user v?").
- The amount of question should be kept to minimum (what is minimum is not really a clear number, but I would say 5% of the number of friends seem about right).
obviously the resulting partition would not be optimal, but it should be acceptable as a starting point for later refinements.
any thoughts would be greatly appreciated
edit: no it's not homework. i believe homework would have clearer defined requirements and target function. anyway no, this is actually real world problem i'm facing.
also i may have simplified it a bit, but in reality a user could be part of many groups (so it's more like F->P(G), where P(G) is the power group if G), so a better algorithm would be able to do that.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
基本想法是尝试根据哪些朋友彼此是朋友来将他们分成几组。
例如，如果您是鲍勃，并且您认识莎莉和拉里，并且莎莉和拉里都互相认识，那么他们可能在同一个“组”中。你还不知道那个群体是什么，但由于你们都互相认识，所以你们可能在同一个地方见面 - 无论是工作、大学等。
你可以将其实现为一个有向图，其中节点是人，边缘是连接。然后，您需要根据这些节点的连接程度将它们分组在一起。
一旦建立了组，那么只需从组和可能不明确的节点中查询样本即可找出组的实际含义。
听起来像是家庭作业，所以我不会透露任何其他内容，但这应该可以帮助您开始。
The basic idea would be to try to partition them into groups based on which of your friends are friends with each other.
For example, if you are Bob and you know Sally and Larry and Sally and Larry both know each other, they are probably in the same "group". You don't know what that group is yet, but since you all know each other, you probably met at the same place - whether that be work, university, etc.
You could implement this as a directed graph where the nodes are people and the edges are connections. You would then need to group those nodes together based on how well connected they are.
Once you've established the groups, then it's just a matter of querying for a sample from the groups and potentially ambiguous nodes to figure out what the groups actually are.
Sounds like homework, so I won't give away anything else, but that should get you started.