基于pagerank算法的无标度网络建模(张翼2010,5).ppt

基于pagerank算法的无标度网络建模Outline:引言pagerank基于pagerank的无标度网络模型总结引言什么是复杂网络?社会关系网络、科学家合作者网络、、食物链、新陈代谢、蛋白质相互作用网络等如果用复杂性的眼光来看,绝大部分事物都是复杂网络。个体与个体之间关系的复杂组成。为什么要研究复杂网络?20世纪三大科学:信息论,控制论,系统论系统论:强调整体的作用并不是单纯部分的叠加1+……+1>n复杂性科学旨在研究个体的叠加为什么会爆发如此惊人的作用,从而通过控制个体的行为和特征,来掌控全局。同步现象,病毒传播等等统计数据,分析网络的特征,建立网络的结构,从而进一步的认识网络的行为,改善网络的性能。首屈一指的工作就是网络的建模。小世界模型无标度模型度分布为幂律分布的网络,即绝大部分的节点的度很低,但存在少量的度相对较高的节点,称为无标度网络为了解释幂律分布的产生机理,Barabási和Albert提出了无标度网络模型(BA模型)。动态增长优先连接:马太效应,富者越富BA模型对于无标度网络的研究起了极大的推动作用,它比较准确的把握了真实网络的最基本特点,揭示了无标度网络的形成机制,但是对于现实网络,BA模型过于简化,忽略了网络演化过程中一些因素的影响。许多实例表明在真实系统中节点的新增连接也参考了其他节点得到的评价高低,但是度并不能客观的反映节点的被认可程度,本文借鉴Google的网页排名算法pagerank,基于BA模型,提出了一种无标度网络的演化模型。pagerankpagerank算法是google的创始人LarryPage和SergeyBrin提出的网页排名算法,它是搜索引擎google的核心技术之一。pagerank算法将文献检索中的引用理论用到Web中,引用网页的链接数,一定程度上反映了该网页的重要性和质量。每个到页面的链接都是对该页面的一次投票,被链接的越多,就意味着被其他网站投票越多。pagerank值可以比较客观的反映一个页面的吸引力,代表了一个页面被“认可”的程度。pagerank算法是基于以下的假设:“一个网页被引用(即反向链接)的次数越多,则说明越重要;一个网页虽然没有被多次引用,但是被重要的网页引用,则它也可能是很重要的;一个网页的重要性被平均的传递到它所引用的网页。”pagerank值是这样被计算的:整个互联网是一个大的有向图,V是所有页面的集合,E是有向边的集合,表示页i有指向页j的超链接。代表页面Vi的pagerank值,是页面Vi的链接数即出度,d是阻尼系数,它的值在0到1之间。网页的pagerank值由下式给出:对于所有的页面的PR值满足,因此可以得出其中M为系数矩阵,PRT对应所有页面的pagerank值,所以,PRT为M的特征根为d-1的特征向量。只需求出特征向量,就是网页集对应的pagerank值,因此可以用迭代方法计算。给定初始向量P做第一次迭代,就相当于用初始向量乘以上面的矩阵。第二次迭代用第一迭代的结果再乘以上面的矩阵,这样迭代下去,最终得出网页集对应的pagerank值。如果有一个页面,它不含有任何的超链接,即它的出度为0,那么经过有限次迭代后所有顶点的PR值都将变为0。这是因为由于该页面不对外贡献任何PR,所以整体的PR总和在不断减少,最终减为0。为了克服这个问题,改进如下: