每一个可以努力的日子,都是一份厚礼。
PageRank与社交网络模型评估(2)
上一篇提到两种网络模型,都有着这样那样的缺陷。下面我们继续来改善建模。
3. Katz Centrality
Katz Centrality解决了之前的问题。它的原理与eigenvector centrality差不多,只是我们给每一个节点提供一个初始化的centrality值β,即对式(6)做简单改变:
α 和 β 都是正常数。
使用矩阵表达式,我们得到:
我们只关心centrality值的相对性,也就是说不管你的centrality值是10还是100,我们只关注你的centrality值是不是大于我的centrality值,因为我们希望找到centrality值最大的前10个节点,目的是做排名。于是β可以设置为1,于是Katz Centrality表达为:
事实上α和β的比值体现了对邻居节点centrality值的侧重,如果α=0那么所有的节点的centrality值都是β=1了,完全不受邻居的影响了。所以说这个公式更具有普遍性,这就是数学之美。
需要注意的是α不可以太大,当 会导致 ,于是 无法收敛。所以有 .
要计算Katz centrality,就要做逆矩阵运算 ,直接计算的复杂度为O(n3)。我们可以用迭代法
4. PageRank
Katz centrality的一个缺陷就是,一个拥有高centrality值的节点会将它的高影响力传递给它的所有邻居,这在实际生活中可能并不恰当。比如说Google的网页有很高的centrality值,同时Google也链接了海量的页面。如果Google的网页链接到了我的网页,那我的网页作为一个无名小卒centrality值岂不是有可能比Google还高?我们希望Katz centrality能够由节点的out-degree稀释,或者说我的centrality值能平均分给我的邻居,而不是给每个邻居都得到我的整个centrality值。用数学语言表达为
对比公式(7)就很容易理解这里对Katz centrality做的修改了。
对于没有外链的节点(例如很多链接指向了一张图片,但图片是没有out-degree指向别处的),将其 值设为1.我们将式(12)写为矩阵形式:
这就是著名的PageRank算法。
同样,α的取值也是有范围的,它应该小于AD-1最大的特征值的倒数。对于无向图来说,这个值是1,对于有向图来说就不一定了。Google的搜索引擎将α设为0.85。同样,要执行这个算法,我们需要知道整个图的拓扑结构。
Google 的两位创始人 Sergey Brin 和 Lawrence Page 在斯坦福大学读博士期间发表的关于 PageRank 的论文可以在 这里 找到。
这篇文章由lovelucy于2011-05-02 00:31发表在网络。你可以订阅RSS 2.0 也可以发表评论或引用到你的网站。除特殊说明外文章均为本人原创,并遵从署名-非商业性使用-相同方式共享创作协议,转载或使用请注明作者和来源,尊重知识分享。 |
批评不自由
则赞美无意义
Google Chrome 31.0.1650.63 Windows 7 大约9年前
博主请问katz 中心性与介数中心性在衡量重要节点方面,有可以互补的地方吗?是不是可以说katz中心性考虑的不仅仅有最短路径还有非最短路径?求解释
Internet Explorer 9.0 Windows 7 大约12年前
博主能否回答一下kate centraliy中β的值是怎么确定的?有没有具体的算法?
Google Chrome 19.0.1036.7 Windows 7 大约12年前
没有确定的算法。这些参数的确立取决于你的目的,我自己在这里的目的是排名,而不关心节点间权重的步距,于是我为了简化公式将β设为1。事实上,很多时候参数都是在长期统计的基础上设立的,Google的搜索引擎将α设为0.85也并不是固定的,随着整个互联网网页的增加和网页间关系的变化,这个值可能随时都会微调,从而影响到网页排名。