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