社交网络分析--找出认识每个人的最小一组人

Question

我有一个社交网络，表示为一组人、S和每个人的个人权重(体重是人的成本)。

我还定义了这些人之间的关系(不管人们是否认识对方)。

我必须找到这样一个子集D，以便该子集中的每个人要么属于set S，要么认识来自set S的人。

将会有很多这样的子集。

我想要一个子集，它的权重之和最小。

我不知道如何解决这个问题。

我想创建一个无向图，其中：

• 每个顶点代表人。
• 每个顶点都有一个权重分配给它。
• 顶点之间的边表示人们是否认识对方。

是个好主意吗？

哪种图形算法对我有用？

编辑:致: Arnol Singh Jaggi

不，我是说别的。只允许直接的关系。这意味着，在你的例子中，答案是亚当(15)，因为他涵盖了整个集合S-他本身在一个子集D中，并且直接了解John和Viktor。

让我们看看这个例子：

{ John (7)，Adam(15)，Viktor(6)，Bob(2)}和连接是Bob.解决方案有: Adam、Bob(17)或John、Victor(13)或Adam、Victor(21)或John、Bob(9)。最好的是最后一个--约翰，鲍勃(9)。

我认为这是有向图问题上的最小生成树。我发现了Chu-Liu/Edmond的算法，我知道这个算法适用于边加权图，而且我有顶点加权，所以我只是将边权设置为边尾顶点的权重。但这不是最佳解决方案。我不需要在片场的人之间有直接的联系。

因此，在得到算法的结果之后，我可以在其上应用一些贪婪的算法，它将递归地遍历每个元素，并检查从子集D中删除它将如何影响结构--当权重之和最小时，将确保没有任何元素从集合D中掉出(请检查下面的检查)。

参考一个例子，我的MST结果将是John，Adam，Victor，Bob(27)。最好的解决方案是John，Bob(9)。有趣的坏解是Viktor，Bob(8) -和是最小的，不幸的是John将从D子集中掉下来。

假设可以从任何其他顶点到达每个顶点，我认为搜索所有连接的组件是错误的。

在解释了它的确切工作原理之后，你有什么不同的解决方案吗？

Answer 1

我假设I must find such a subset D, such that every person in this subset either belongs to the set S or knows someone from the set S意味着D中的每个人要么属于S，要么直接认识来自S的人，或者间接地认识，。

这意味着，如果集合S是{John(10), Adam(15), Viktor(6)}，连接是John - Adam - Viktor，那么答案集D将是Viktor(6)，因为Viktor直接了解Adam，间接了解John。

根据上述假设，您的图形建模是正确的。

在无向图中找到所有的连通元件。

假设有n个连通的组件。

现在，找到每个分量中权重最低的顶点。

你会得到n个顶点，每个组件都有一个。

答案子集D是这些n个顶点的集合。

这是对这个问题最有效的算法，因为时间复杂度与顶点+边的数目成线性关系。

这里是一个使用DFS的连接组件的简单实现。

编辑：

我想你要找的是无向图的最小顶点覆盖问题。