从图表中移除集线器

数据挖掘 图表
2022-01-25 17:27:22

我有一个带有代表一些实体的顶点的图,并且边缘被加权为两个这样的实体之间的相关性。

我想将此图分解为几个具有高内相关性的子图。

我的问题是我有几个“中心”,与许多不同的实体高度相关。

如何检测此类集线器以将其删除?

1个回答

取决于您如何定义“集线器”。在网络科学中,集线器只是一个具有高度数的节点,即那些对度数分布的幂律性质贡献最大的节点。但是您也可以找到其他定义,例如根据网络中的信息流,其中集线器被定义为那些在流程信息流中至关重要的节点(也称为中心节点)。

我的建议

  1. 度分布:最简单的方法是选择高度节点作为枢纽。为了确保您的结果更多一点,我建议计算与每个节点对应的所有相关性的总和,并查看这些数字。在这种情况下,您正在寻找具有高度且包含较大相关值的节点。

  2. Centrality Measure:或由 Linton Freeman 引入的介数,它再次以某种方式测量节点在网络信息流过程中的影响。计算顶点的中心性v在图中基本上有 3 个步骤:

    • 对于每一对顶点(s,t),计算它们之间的最短路径。
    • 对于每一对顶点(s,t),确定通过相关顶点的最短路径的分数(这里,顶点v)。
    • 在所有顶点对上求和这个分数(s,t).

有关更多信息,请仔细阅读内容,如果您需要任何帮助(特别是实施方面的帮助),请在评论中给我留言 :)

祝你好运!