如何确定社交网络中的可能联系？

Question

我很好奇确定一种解决“建议朋友”算法的方法。

Facebook 具有一个功能，它将向您推荐个人，以为您可能会熟悉。这些用户通常（不包括在 用户专门推荐朋友）与自己具有高度相似的网络。也就是说，共同的朋友人数很高。我认为Twitter遵循了类似的途径，他们的“谁遵循”机制。

斯蒂芬·道尔（igy）, ，Facebook员工建议使用的相关新闻源 Edgerank公式 这似乎表明比外表之类的朋友更重要的是相似的帖子。另一位用户建议使用Google等级系统。

Facebook将他们的新闻提要优化为$ sum u_ {e} w_ {e} d_ {e} $在其中

$ u_ {e} $ =查看用户和边缘创建者之间的亲和力得分
$ w_ {e} $ =此边缘的重量（创建，注释，喜欢，标签等）
$ d_ {e} $ =根据创建了多长时间的时间衰减因子

总结这些项目应该给出一个对象的等级，我认为这是IGY所暗示的，这意味着以类似格式的某些内容用于建议的朋友。

因此，我猜这是所有类型的连接通常通过等级系统完成的方式吗？

Answer 1

您可以将社交图视为矩阵$ mathbf {m} $。解决问题的一种方法是首先计算$ mathbf {m}^2 $，这将提供社交网络中两个参与者之间的所有长度二的路径。这可以看作是这些朋友朋友之间联系的重量。下一步是从$ mathbf {m}^2 $的行中选择与感兴趣的人相对应的列，以获得新朋友的最佳候选人。

Answer 2

以同等概率的方式向朋友推荐朋友是一个相对便宜但不准确的启发式方法。例如，我父亲有朋友，但我不会说我是与他们中的任何一个朋友（尽管我可能会说我是父亲的朋友，例如，例如社交网络）。让一个人处于相对较近的距离，并不一定会使他们成为一个很好的候选人。

建议您与您有很多扩展联系的人似乎也是一个糟糕的选择，因为这往往会导致人们早日提前领先的朋友的指数成长（凯文·培根游戏的七个分离程度是一个这个例子）。

我建议基于电路的模型。假设每个链接都是电阻$ r $的电阻。那么，新朋友的最佳候选人可能是等效抵抗力最低的个人。这是一个执行不良的ASCII图形示例：

  _____
 /     \
a---c   f
|   | /
b   d---e
| \ |
g   h   i

说我们想找到新朋友 a. a目前的朋友是 b, c, ， 和 f. 。我们评估净等效性 a 和每个 d, e, g, h, ， 和 i:

pair   resistance
(a,d)   6/7
(a,e)  13/7
(a,g)   7/4
(a,h)   1/1
(a,i)   inf

根据这个启发式， d 是最好的候选人朋友，紧随其后 h. g 是下一个最好的选择，紧随其后的是 e. i 通过这种启发式，永远不会成为候选朋友。您是否发现这种启发式的结果代表了真实的人类社会互动，这一点很重要。从计算上讲，这将涉及找到一个子图，该子图包含两个个体之间的所有路径（或者有趣的是，对此有意义地选择了截断），然后评估源节点和源节点之间的等效电阻。

编辑：那我的社交动机是什么？好吧，这可能是一个粗略的模型，说明与中介（朋友）之间的联系有多么困难，随后可以通过中介（朋友）传达大量信息。用CS术语（而不是物理术语），这可能被解释为图中两个节点之间的带宽。该系统的扩展是允许重量不同（阻力，带宽等）之间的不同类型的联系，并按照上述进行。

Answer 3

这里 和 这里. 。该方法范围从非常简单（例如节点之间的JACCARD相似性）到非常复杂的（例如构建生成连接过程的统计模型）。这在很大程度上取决于您在数据集中可用的特定功能（例如，网络结构，节点属性？，边缘属性，...），但是这些调查将为您提供一个很好的开始。

Answer 4

免责声明：我在这里疯狂地猜测；我没有阅读任何类型的研究。

每个节点$ n $（人或其他概念）都有一组连接$ C_N $。现在，给定两个节点$ n_1 $和$ n_2 $，建议$ n_2 $ to $ n_1 $如果

美元

对于[0,1] $中的某些合理的$ alpha （另一方面）。

另一个想法更全局：确定一组节点 相似的 向手头的人提出了许多人共享的联系。因此，定义类似节点的集合

美元

以及设定的合理建议

美元

再次为合理的$ alpha， beta in [0,1] $。

实际上，您当然想单独加权连接；例如，您已经连接的$ s_n $的元素应该比离您遥远的导入更大。