我需要解决一个特定的问题。我得到了一个社交网络的表示。每个节点是一个人，每条边是两个人之间的连接。该图是无向的（如您所料）。每个人都有购买产品的个人“亲和力”（为了简化事情，假设整个问题只涉及一种产品）。
在时间的每一个“步骤”中，每个人都独立地选择是否购买产品。这里涉及到概率。考虑了几个参数：
购买该产品的人的收益是 1 美元。
问题是指出将在第 0 步中收到产品的 X 人（比方说 5 人），并且在 Y 步（比方说 10 步）后最大化增益的总期望值
网络非常大。以幼稚的方式模拟所有选项是不可能的。
我应该使用什么工具/库/算法？
谢谢你。
PS 在 google 和 wikipedia 上调查这件事时，一些术语不断出现：
但这并没有帮助我找到答案
查看submodularity的概念，这是一个非常强大的数学概念。特别是，请查看幻灯片 19，其中子模块性用于回答“给定社交图谱，谁应该获得免费手机？”的问题。如果您有访问权限，还请阅读相应的论文。那应该让你开始。
一般来说，拥有最多邻居的人在购买东西时影响最大。
因此，我的启发式方法是首先按人们拥有的邻居数量（按降序排列），然后按每个邻居拥有的邻居数量（按从高到低的顺序）对人们进行排序，依此类推。您将需要最多 Y 个级别的邻居计数，但实际上更少可能就足够了。然后只需选择此列表中的前 X 人。
这只是一种启发式方法，因为例如，如果一个人有很多邻居，但他们中的大多数或全部可能已经通过其他联系购买了该产品，那么它可能会给出更高的期望来选择另一个邻居较少的人，但他们的邻居不太可能已经拥有该产品。
您不需要构建整个列表然后对其进行排序；您可以构建列表，然后将每个项目插入到堆中，然后只提取得分最高的 X 人。如果 X 很小，这将快得多。
如果 X 和 Y 与您建议的一样低，那么此计算将非常快，因此值得重复运行，而不是从拥有产品的前 X 人开始，对于每次运行，您随机选择最初的 X 所有者根据取决于他们在列表中位置的概率（列表越靠下，概率越低）。