基于网络连接图的转移矩阵P的分析和修正矩阵乘积

　　基于网络连接图的转移矩阵P的分析和修正矩阵乘积

　　《毕业论文：谷歌搜索引擎中网页排序算法研究.doc》由会员分享，全文可免费在线阅读。更多《毕业论文：谷歌搜索引擎中网页排序算法研究》相关文档，请在棒棒图书馆()数亿文档库存中搜索。

　　1、，文章中的主要参考资料多为谷歌商业化前设计者发表的学术论文，大大增加了引入这项技术的难度。但其排名算法的机制并没有发生本质的变化，PageRank技术仍有研究价值。 PageRank 是一个复杂的计算。其本质是找到一个大矩阵的主特征值（最大特征值）对应的特征向量。传统的幂法是解决此类问题最有效的数值方法。由于网络的复杂性，本文对转移矩阵P进行了分析和修改，并利用网络结构中的这种稀疏性，将应用于矩阵P（完全稠密）的幂法转化为应用于大的向量矩阵乘积形式。稀疏矩阵 P 被实现。在这个过程中，不需要构造和存储修改后的矩阵P和P，大大减少了存储空间。由于矩阵P极其稀疏，每行非零元素的平均个数不超过1，同时有很多全零行，这使得幂法的收敛速度非常快。在参考文献[]中，通过最小二乘法外推整体得到的向量在原创迭代中重复使用，而本文给出的外推方法只检测原创迭代得到的向量序列，并外推这个序列形成一个新的，更快收敛序列，同时检查这个新序列的终止条件。与 [] 的区别在于它不会。

　　2、一直是这个领域的佼佼者。本文深入研究了PageRank排名算法。从数学的角度发现，可以通过基于网络连接图计算转移概率矩阵的主特征向量v（PageRank向量）来实现。同时，根据网络的复杂情况，对转移概率矩阵进行修改，分析修改后的矩阵()PPEαα＝+的特性。给出了计算主特征向量的数值解幂方法。利用修正矩阵P中链接矩阵P的稀疏性，优化了迭代中幂法的计算量，减少了存储空间。在幂法理论的基础上，给出了一种新的加速收敛的外推方法TheVector。算法，最后结合真实复杂的网络数据测试，验证了外推方法的良好实用效果。 关键词：搜索引擎；网页排名;转移概率矩阵；主要特征向量；加速收敛；外推法；功率法；矢量算法摘要随着电子技术的发展，搜索引擎技术变得越来越重要。

　　3、 页面。例如，当用户不知道其他网站的超链接到百度，但用户知道其网址时，他也可以访问该网页。图中的两个子网都有访问平衡，也可以推断出级别是一样的。可见，这种基于链接的PageRank页面排名是合理的。 ABCDABCDABCD在版块中分析了一个真实的复杂网络，验证了基于链接的PageRank页面排名的合理性。下面用一个真实的网络来测试外推法的收敛加速效果。测试数据wwweagovdat来自[]。该数据库收录一个网页和一个超链接。相关链接如下图所示。为了体现外推法的效果复杂网络的链接图中提供的vector算法，使用阻尼因子α=来降低收敛速度，使外推法的效果更加明显。该图基于图的真实网络，显示了这种情况下幂法和外推法在求其主特征值时的收敛性。从图中可以看出，幂法和外推法在多次迭代后都变得非常稳定，它们的主要特征值序列都收敛到。当误差容限为 - 时，幂法迭代后满足要求，外推法迭代后满足要求。图幂法和外推法的主要特征值变化曲线也是为了更好地反映外推法阻尼因子的差异。

　　4、 是要走的路。参考文献：[]CNETGoogle 检测到超过一万亿个独立页面 [EBOL]htt:itenorthcomcnsystemshtml,[]TobySegaran 集体智慧编程[M]北京：电子工业出版社[]GrimmettG,StirzakerDProbabilityandrandomrocesses[M]OxfordUniversityPress[]李庆阳，王能超，易大奕数值分析（版）[M]武汉：华中科技大学出版社[]AmyNlangvilleandCarlDMeyerDeeerinsidePageRank[J]InternetMathematics():[]KurtBryanandTanyaLeiseThe$,,,Eigenvector:TheLinearAlgeabehindGoogle[J]Mathematics:TheLinearAlgeabehindGoogle[J]MathelinedTheLinearAlgeabehindGoogle[J]Mathematics sLargestMatrixComutation[EBOL]ht.

　　根据上面的伪代码，5、值的加速效果是在matlab、Pentium(R)CPUGHz、GB内存、WindowsXP环境下实现的。程序见附录。下表显示了这个真实网络的幂法和外推法的迭代次数和运行时间。表幂法和外推法收敛测试表 Accel_PowerMothod 法 PowerMethod 方法 主特征值迭代次数 运行时间（秒） 主特征值迭代次数 运行时间（秒） α 该图直观地反映了幂法和外推法向量算法对比关系阻尼系数和应用程序中的迭代次数之间。可以看出，外推法向量算法在*敏*感*词*网络的排序计算中，在加速收敛方面有很好的表现。当阻尼因子的值较小时，加速度不明显，但仍比传统幂法收敛得更快；当阻尼因子接近时，有明显的加速效果（迭代次数不超过）。迭代曲线结论和展望的图幂法和外推法谷歌可以说是当今最成功的搜索引擎之一，国内对谷歌的研究较少文章，对其核心技术进行深入分析对搜索引擎开发的研究具有很大的借鉴作用。作为商业搜索引擎，其核心技术细节是安全性。

　　6、 archenginekeesonthetobyitsPageRankandconvergencealgorithmWewillseethat，fromthemathematicalointofview，itcouldbesolvedbycomutingtherincialeigenvector（thePageRankvector）ofaTransitionProbabilityMatrixoftheWebAccordingtotheWeb'scomlexity，wewillgivethemodifiedmatrix（）PPE，andalsoanalyzeitscharacteristicsWewillstudythemathematicalroertiesoftheowermethodthatcomutingthePageRankvectorWeusethesarseoftheWebmatrixPintheiterativematrixP，otimizethecomu。

　　7、 修正上述问题 修正悬点修正dim(())TLP 修正PAGERANK问题求解方法Power方法 PAGERANK上的Power方法初始优化PageRank矩阵幂方法伪代码Power方法加速外推向量algorithmThevectoralgorithm 伪代码应用 一个简化网络的层次分析 一个现实复杂网络的分析 结论与展望 参考文献 引言 目前，互联网上有大量的站点在不断地向用户进行搜索。数据，并使用机器学习和统计方法获取所需信息。谷歌搜索 k) 得分。在理想图中，图中有挂点。简化图中有子图。秩图中的节点是 ABCD。图中节点A的得分来自B和C，C只投了一半的票给了A，从这点可以得出节点C的得分高于A。图中发现B没有来自任何节点的投票，但从表中我们可以看到它的排名不为零。这种处理的原因是用户行为的多样性，网页可能来自其他形式的理解或一种盲目跳转，有机会访问该网页，或者访问该页面时，访问者会随机跳转无需通过页面上的超链接即可访问新的。

　　8、 ationofeachiterationandreduceitsstoragesaceTheVectoralgorithm, anextraolationalgorithmforvectorsequences,isroosed based ontheowermethodIt willachievethehigherrateconvergenceinthecomutingerformanceofowermethodFinally, somesimulationworkofthe racEngine网页排名;转移概率矩阵； rincialeigenvector;收敛和加速；外推法；方法； Vector算法目录线程。

　　9、 的序列应用于原创迭代。当然，幂法中的收敛速度不仅与特征值有关，还与初始初始状态有关，因此可以考虑优化初始状态，使其收敛得更快。对于一个大的稀疏矩阵P，也可以对矩阵做一定的初等变换，使悬点下沉，即所有零行下沉。复用矩阵块的属性可以减少存储空间，加快计算速度。具体理论可以参考[]。目前，部分网站制作者使用站点链接和网站maps来提高站点中PageRank的反馈价值。那么谷歌会不会打折这种内部链接的投票价值呢？而这会影响这种基于链接的排名计算方法吗？因为这本身就是PageRank工作最基本的机制，所以有人认为PageRank在谷歌排名算法中的作用已经下降。但对于1亿多页的庞大网络链接图，人为影响能有多大？ PageRank 技术的分析不是我们的最终目标。关键在于对PageRank排序算法的深入理解，从而提出一种新的网络搜索引擎排序机制，研究应用一些新的计算加速算法。互联网变得越来越复杂，谷歌的搜索结果并不完美，同时面临同行的竞争，排序算法的优化还有很多。

　　10、tiontechniquesforiteratedvectorandmatrixroblems[J]MathCom,():[]PGravesMorrisVectorvaluedrationalinterolantsI[J]NumerMath,():[]WolframMathWordAitkensDeltaSquaredProcess[EBOL]htt:mathedwolframAitkenWorlds of China []SergeyBrin,LawrencePage,etalThePageRankcitationranking:ingingordertotheweb[M]ComuterScienceDeartment[]JohnHMathewsandKurtisDFinkAitken'sProcessandSteffensen'sandMuller'sMethods[M]N.

　　11、:wwwmathworkscomcomanynewslettersnews_notesclevescorneroct_clevehtml, [] TaherH, Haveliwala, etalTheSecondEigenvalueoftheGoogleMatrix [J] Stanford, (): [] AnaCMatosConvergenceandaccelerationroertiesforthevectorεalgorithm,AAccelerationroertiesforthevectorεalgorithm,AAcceleratora,C.A.D.Algorithm,C, Micheliag 和 , 米歇尔, *敏*感*词*, 米歇尔, 米歇尔, 米歇尔, 米歇尔, 和*敏*感*词*, 向量MatrixAnal,():[]CBrezinskiSomeresultsintheoryofthevectorεalgorithm[J],LinearAlgeaAr,():[]PWynnAcceler.

　　12、mericalMethodsUsingMatlab[]SeandarDKamvar,TaherHHaveliwala,etalExtraolationMethodsforAcceleratingPageRankComutations[M]ACMPress[]JonKleinbergwwweagovdat[EBOL]htt:wwwcscornelleduCoursescsfareddata[EBOL]htt:wwwcscornelleduCoursescsfareddata][EBOL]htt:wwwcscornelleduCoursescsfaddata][EBOL][EBOL][EBOL][EBOL][EBOL][EBOL]优化工程[EBL :wwwcscornelleduCoursescsfadata ): []AmyLangvilleandCarlMeyerAreorderingforthePageRankroblem[J]ScientificComuting,():武汉纺织大学毕业设计[论文]题目：谷歌搜索引擎网页排序算法研究综述 搜索引擎技术的发展是信息的数字化与不断的电子技术的进步 数据联网的必然产物，网页排序算法一直是搜索引擎的核心技术之一。谷歌搜索引擎依赖其PageRank机制和收敛计算