algorithm - 以概率最大化社交网络中的预期 yield

Question

我需要解决一个特定的问题。我得到了一个社交网络的表示。每个节点是一个人，每条边是两个人之间的连接。该图是无向的(如您所料)。每个人都有购买产品的个人“亲和性”(为简化起见，假设整个问题只涉及一种产品)。

在时间的每个“步骤”中，每个人都独立地选择是否购买该产品。这里涉及概率。考虑了一些参数:

1. 他对产品的个人亲和性，
2. 他的 friend 中已经购买该产品的百分比

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

问题是指出 X 个人(假设 5 个人)将在第 0 步收到产品，并在 Y 步(假设 10 步)后最大化 yield 的总期望值

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

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

谢谢。

附言在google和wikipedia查这件事的时候，不断冒出几个名词:

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

但这并没有帮助我找到答案

Answer 1

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

因此，我的启发式方法是首先按照他们拥有的邻居数量(降序)对人们进行排序，然后按照每个邻居拥有的邻居数量(从高到低的顺序)，依此类推。您最多需要 Y 级的邻居计数，尽管在实践中更少可能就足够了。然后只需选择此列表中的前 X 个人即可。

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

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

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