网络中关键节点的识别

最近半年一直在尝试从复杂的关系网络中，挖掘可能从事某种恶意的团伙，比如在交易数据中挖掘潜在可疑交易的诈骗团伙等。在对全网的复杂网络分团后，面临一个问题，就是需要识别可疑恶意团伙的核心节点，或者关键节点。

从调研的情况来看，主要有如下衡量节点重要性的手段：

1、度

这是一种最简单也最直观的衡量方式，计算网络中每个节点的度数，根据度数大小衡量重要性。度数越大，说明与该节点连接的节点越多，即该节点越重要。典型的案例，如微博的大V，因为其分数多，度数高，因此根据度衡量，大V们往往会被计算为团中的关键节点。

优点：计算简单，成本低，是一种考虑节点近邻的排序方式。

存在的问题：缺乏全局的考虑，因为其仅考虑了1度关联的节点数，甚至没有考虑关联节点的重要性。如果某个大V购买了很多僵死粉，也会被计算为关键节点，虽然这个“大V”对其他正常用户的影响力很小。

2、介数

某个节点的介数，是指网络中所有的最短路径中经过该节点的路径数。介数越高，说明网络中任意两个人的关系与这个节点的关系越大，即这个节点在全局中的影响力越大，也就越重要越关键。

优点：相比度，介数考虑节点在整个网络中的重要程度，是一种基于路径的衡量，或叫排序方式。

存在的问题：计算时间复杂度较大，尤其在节点较多的网络中，在实际应用中需要进行优化。

3、核度

核度也是一种基于近邻度量的计算方式。对网络从外围一层一层剥离直到没有节点，节点的核度是指该节点处于被剥离的位置。如度为1的节点为最外层，也就是核度为1的层，剥离这些节点后，会再次出现度为1的节点，重复剥离。值得注意的是，并不是度越大的节点，核度越大，越最后被剥离。

如果一个节点的核度越大，越是最后被剥离，说明它越处于网络中的中心位置，也就越重要。

优点：相比度的局限性，核度考虑了节点在整个网络的重要程度，并且计算复杂度没有明显增大。

存在的不足：划分力度太粗，导致很多看起来并不属于同一层级的节点，被划分为相同的重要层级，即每一次剥离的节点很多。

除了上述3个指标，还有很多其他衡量节点的方式，如H指数等。综合来看，挖掘和识别网络中的重要节点，目前存在如下的问题：
1、无法找到一种适合所有网络结果的衡量方式，也就是说，不同网络结果的节点重要性衡量是不一样的。
2、即使在明确的衡量公式下，不同参数也会导致结果不同。
3、众多的分析算法都是对单个点的重要性衡量，而不是节点集，重要的节点集，并不是单个节点的集合，而是对复杂网络的一种抽取。