具有概率的社会网络中期望收益的最大化

Question

我需要解决一个具体的问题。我得到了一个社交网络的代表。每个节点是一个人，每个边是两个人之间的连接。图是无向的(正如您所期望的)。每个人都有购买产品的个人“亲和力”(为了简化事情，假设这个问题只涉及一个产品)。

在每一个“步骤”的时间，每个人，独立，选择是否购买该产品。这里有可能。考虑到以下几个参数：

1. 他对这个产品的个人亲和力，
2. 他的朋友中购买该产品的百分比

购买该产品的人的收益是1美元。

问题是指出在步骤0中将接收产品的X个人(例如，5个人)，并且在Y步之后，最大限度地获得收益的总期望值(比方说，10个步骤)

网络很大。不可能以天真的方式模拟所有的选项。

我应该使用什么工具/库/算法？

谢谢。

在谷歌( google )和维基百科( wikipedia )调查此事时，不断出现一些术语：

• 动态网络分析
• 流行病模型

但这并不能帮我找到答案

Answer 1

一般来说，邻居最多的人在买东西时最有影响力。

因此，我的启发是，首先根据邻居的数量(按递减顺序)排序，然后根据每个邻居的邻居数量(从最高到最低)排序，以此类推。你将需要最多Y级的邻居计数，虽然在实践中可能较少。然后简单地把名单上的第一个X人取出来。

这只是一种启发，因为例如，如果一个人有许多邻居，但他们中的大多数或全部很可能已经通过其他联系购买了该产品，那么选择一个邻居较少但邻居不太可能已经拥有该产品的另一个人可能会产生更高的期望。

您不需要构造整个列表，然后对其进行排序；您可以构造列表，然后将每一项插入到堆中，然后只提取得分最高的X人。如果X是小的，这会快得多。

如果X和Y像你建议的那样低，那么这个计算就会非常快，因此值得重复运行，而不是从拥有该产品的第一个X人开始，对于每一次运行，您都会根据一个概率随机选择最初的X所有者，这个概率取决于他们在列表中的位置(在列表中的位置越低，概率就越低)。

Answer 2

看看子模块性的概念，一个非常强大的数学概念。特别是查看幻灯片19，其中使用子模块性来回答“给定社交图表，谁应该获得免费手机？”的问题。如果您有访问权限，也可以阅读对应纸。这应该能让你开始。