上一篇提到两种网络模型,都有着这样那样的缺陷。下面我们继续来改善建模。

3. Katz Centrality

Katz Centrality解决了之前的问题。它的原理与eigenvector centrality差不多,只是我们给每一个节点提供一个初始化的centrality值β,即对式(6)做简单改变:

(7)

α 和 β 都是正常数。

使用矩阵表达式,我们得到:

(8)

(9)

我们只关心centrality值的相对性,也就是说不管你的centrality值是10还是100,我们只关注你的centrality值是不是大于我的centrality值,因为我们希望找到centrality值最大的前10个节点,目的是做排名。于是β可以设置为1,于是Katz Centrality表达为:

(10)

事实上α和β的比值体现了对邻居节点centrality值的侧重,如果α=0那么所有的节点的centrality值都是β=1了,完全不受邻居的影响了。所以说这个公式更具有普遍性,这就是数学之美。

需要注意的是α不可以太大,当   会导致 ,于是 无法收敛。所以有 .

要计算Katz centrality,就要做逆矩阵运算 ,直接计算的复杂度为O(n3)。我们可以用迭代法

(11)

4. PageRank

Katz centrality的一个缺陷就是,一个拥有高centrality值的节点会将它的高影响力传递给它的所有邻居,这在实际生活中可能并不恰当。比如说Google的网页有很高的centrality值,同时Google也链接了海量的页面。如果Google的网页链接到了我的网页,那我的网页作为一个无名小卒centrality值岂不是有可能比Google还高?我们希望Katz centrality能够由节点的out-degree稀释,或者说我的centrality值能平均分给我的邻居,而不是给每个邻居都得到我的整个centrality值。用数学语言表达为

(12)

对比公式(7)就很容易理解这里对Katz centrality做的修改了。

对于没有外链的节点(例如很多链接指向了一张图片,但图片是没有out-degree指向别处的),将其 值设为1.我们将式(12)写为矩阵形式:

(13)

其中D是对角矩阵, .同样设β=1,上式可以变形为

(14)

这就是著名的PageRank算法。

同样,α的取值也是有范围的,它应该小于AD-1最大的特征值的倒数。对于无向图来说,这个值是1,对于有向图来说就不一定了。Google的搜索引擎将α设为0.85。同样,要执行这个算法,我们需要知道整个图的拓扑结构。

Google 的两位创始人 Sergey Brin 和 Lawrence Page 在斯坦福大学读博士期间发表的关于 PageRank 的论文可以在 这里 找到。