我有我的 Facebook 朋友的无向朋友图，G即G[i][j] = G[j][i] = true如果我的朋友i和朋友j彼此是朋友。我想找到“令人惊讶的”共同朋友，即我通常不希望彼此认识的一对朋友。我可以应用哪些好的启发式/算法？我最初的想法是运行一个聚类算法（不确定哪一个是最好的），看看我是否能找到跨集群的边。还有其他想法吗？我可以使用什么好的聚类算法来接收 G 并吐出聚类。
问问题
396 次
2 回答
2
这是我的想法。友谊是一种优势。令人惊讶的友谊是一条边，这样如果你去掉这条边，两个节点之间的距离就会变得非常大。
于 2013-04-10T03:52:56.803 回答
2
Wu Yongzheng 的回答可以与现有的网络概念相关联，该概念是一种稳健且可能更敏感的度量，即对节点之间距离的量化采取变得非常大。这个概念是边缘介数。在这种情况下，人们会计算一个估计的版本。参见例如https://en.wikipedia.org/wiki/Betweenness_centrality和http://igraph.sourceforge.net/doc/R/betweenness.html。
于 2014-03-10T10:27:32.530 回答