我有一个包含大约 10K 顶点和 100K 边的JUNG 图，我想衡量任何一对顶点之间的相似性。顶点表示概念（例如狗、房子等），而链接表示概念之间的关系（例如相关、is_a、is_part_of 等）。
顶点紧密相连，因此最短路径方法不会给出好的结果（最短路径总是很短）。
您会推荐哪些方法来对顶点之间的连通性进行排名？
JUNG 有一些算法来对顶点的重要性进行评分，但我不明白是否有两个顶点之间的相似性度量。 SimPack似乎也很有希望。
有什么提示吗？
问问题
792 次
1 回答
2
分数不衡量顶点对的centrality相似性，而是衡量一般网络单个节点的某种（取决于方法）中心性。因此，这种方法可能不是您想要的。
SimPack确实有一个很好的目标，但是对于图，它实现了基于同构的比较，而不是比较多个图的相似性，而不是一个给定图的节点对。因此，这暂时超出了范围。
你所寻求的是所谓的graph clustering方法（也称为网络模块确定或网络社区确定方法），它将图（网络）划分为多个分区，使得每个分区中的节点之间的互连比与其他分区。
最经典的方法可能是 Newman & Girvan 的中介中心性聚类，您可以利用树状图进行相似度计算，它在 JUNG 中。当然，现在有很多方法。您可能想尝试（无耻地插入）我们的ModuLand 方法，或阅读电子补充材料末尾的模块检测算法细表。那是一个overlapping graph clustering方法族，即每个节点的结果是一个向量，其中包含属于网络的任何相应集群的强度。成对的节点相似性很容易从这些节点到集群的向量对中推导出来。
图形聚类非常重要，您可能需要调整任何方法以获得非常精确的特定领域结果，但这取决于读者；）祝您好运！
于 2011-07-03T19:36:14.090 回答