PageRank算法的复杂程度怎么样_2

2019-11-09 20:52:01

我来科普一下Google的PageRank算法吧！不对之处，还望大家指教啦。在PageRank发明之前，搜索引擎采用的还是最原始的关键字匹配技术，于是呢在搜索结果中经常会遇到「挂羊头卖狗肉」的垃圾网站，对这些网站，当时的Yahoo采用还是人工清理的方法。这时候Google的两位创始人Page和Brin就在想，有没有一种算法，能够给出网页重要性的排序呢？这样就可以优先推荐重要网页，而让那些垃圾网页石沉大海了。Page和Brin发现，网页的超链接结构中就蕴含了重要程度的信息。由于一个网页的超链接指向的主要是与其内容相关的网页，那么我们不难想象，如果有许多网页都同时指向某一个网页，这个网页就一定非常重要。我们将互联网想象成一个流网络，网络的节点就是一个个网页，如果两个网页间存在超链接的关系，那么它们之间就存在一条有向的连边。想象存在一种货币，它们在这个流网络上随机地流动，在任意时刻，每个网页上都会有货币流入，也会有货币流出，当最终达到稳定时，将每个网页持有的货币存量，或者说「财富」的多寡由大到小排序，就得到了网页重要性的排序PageRank。我们发现排在前面的主要是被较多引用的网页，当然有幸被重要网页引用的网页也会得到较大的PageRank值。当然我们还要考虑这样一种情况，如果遇到不引用任何其他网页的「铁公鸡」，或者网页A仅引用B，B仅引用C，C又仅引用A的「小团体」，货币只会流入不会流出，他们会积累大量的货币，但显然他们不一定是最重要的。为避免这样的情况发生，PageRank还使货币可以以概率e跳到系统中的任意其他节点。或者我们可以想象系统中存在一个「中央政府」，它在每一时刻都从各个网页节点的「财富」中征缴比例为e的「税金」，然后再平均分给每一个网页。好啦，规则就是这样，那各个网页的PageRank值怎么计算呢？设为各个节点（网页）的货币存量，并令，其中N为节点数。，其中表示货币流入量，表示货币流出量。进而：其中，为货币有节点流向节点的概率，显然等于1/节点的连边数。于是，为货币流入量中的从其他节点流入节点部分，为由「中央政府」赠与的部分（我们已令），为货币流出量中由流向其他节点部分，为「上缴」的「税金」。化简上式可得：我们令，，，则有求方程的稳定解，即让，得到：由于的列和为1，所以上式存在更简单的解法：，因此为矩阵特征值1的特征向量，可以快速求解。所以，大家看到了，PageRank非常简单。正如另一位知友所说：主要的挑战来自海量的数据

上一条：上一篇：F1比赛没落了吗
下一条：下一篇：不能说的秘密是部好电影吗_3

相关产品

相关资讯