链接算法（精选七篇）
链接算法 篇1
作为一种抽象结构, 社会网络是指由节点和边组成的, 用来描述节点之间复杂关系的网络。由于社会网络在社会学、心理学、计算机学甚至生物学等多个领域的广泛应用, 研究者们对社会网络的研究方兴未艾。随着社会网络数学性质不断被挖掘, 研究者发现社会网络中节点之间的链接关系对整个社会网络分析起到重要作用。对链接关系进行挖掘意义较大, 可以揭露网络中隐藏的关系。而链接预测是链接挖掘中的一个最基本问题, 它基于节点属性以及已经观察到的链接信息, 对两个节点之间是否会出现链接进行预测。链接预测不仅可以用来预测在时间演化尺度下未来可能出现的链接关系, 还可以用来检验出由错误信息所导致的虚假链接。作为社会网络分析的一个重要方向, 链接预测与社会学、图形学有着密切关系, 并逐渐发展成为国内外研究热点。
近年来, 研究者提出了很多解决链接预测的相关算法, 这些算法一般是基于监督学习的链接预测、基于概率模型的链接预测、基于节点相似度的链接预测等。但是社会网络是动态发展变化的, 随着时间的推移会出现很多新的节点和边, 同时一些旧的节点和边会消失。因此传统的链接预测算法只有与时间属性相结合才能更好地刻画网络的演变机制, 从而发现网络的演变规律。
1 相关研究
目前, 社会网络链接预测研究主要分为如下3个方向:
(1) 基于节点相似度的链接预测[1,2]。根据预先设定好的相似度评分函数对节点间的相似度进行打分, 然后根据打分值将所有没被发现的链接进行排序, 相似度分数越高则该两个节点存在链接的可能性越大。该方法的缺点是考虑网络拓扑结构, 而忽视了网络的其它因素, 例如时间因素, 从而导致预测结果差强人意。
(2) 基于概率模型的链接预测[3,4]。首先利用社会网络中的节点或者边构造一个统计模型, 然后利用该统计模型进行链接预测。统计模型构建是该方法的核心, 将直接影响后续链接预测的结果。该方法主要有两个缺点:一是获取节点信息的难度很大, 无法获得足够的先验知识, 因此统计模型构建非常困难;二是算法的复杂性比较高, 因此在实际应用中具有一定难度。
(3) 基于监督学习的链接预测[5,6]。根据已知的网络信息获取链接关系, 并在这些链接关系中提取相关的特征属性构建分类器, 然后根据该分类器对未知网络进行二类划分, 即判断链接关系存在或者不存在。该方法的主要缺点是社会网络中的节点不是简单的统计上的独立采样点, 节点之间存在着联系, 并不满足传统的机器学习条件。
近几年, 研究者对链接预测的研究越来越深入, 并不断加入影响算法的新因素。除实现基本的发现隐藏链接的任务外, 还需要考虑新的细节。例如, 可以考虑时间演化尺度下社会网络中的链接预测。随着时间的推移, 社会网络中节点之间的链接在不断变化, 可能会有新链接的产生, 也可能有旧链接的消亡, 因此链接预测需要考虑时间因素。
2 算法提出
共有邻居相似度算法是一种经典的基于节点相似度的链接预测方法, 该算法利用两个节点共有邻居的多少来确定链接存在的概率, 即共有邻居越多链接存在的概率越高, 反之则越低。例如, 如果两个人之间的学历、爱好和收入都比较相近, 就可以认为他们之间的相似度较高。然而该算法仅考虑共有邻居的数目, 没有考虑其它因素 (例如时间因素) , 显然是不全面的。因此, 本文尝试将时间因素融入到共有邻居相似度算法, 提出了新的节点相似度评价标准。
2.1 问题定义
为简化问题, 只考虑无向社会网络, 首先给出无向社会网络的定义。
定义1:无向社会网络可以定义为G=
上述定义是基于传统的静态社会网络, 但社会网络是动态变化的。考虑社会网络的时间属性, 提出了基于不同时刻快照的社会网络定义。
定义2:无向社会网络可以定义为由不同时刻的快照所组成的图序列G=
然后再给出基于定义2的链接预测定义。
定义3:给定一个社会网络在不同时刻所组成的图序列G=
2.2 共有邻居相似度
共有邻居相似度认为如果两个节点拥有越多的共同节点, 则这两个节点越相似。
定义4:对于节点u和节点v, 其共有邻居相似度定义如下:
其中, neighbor (u) 是节点u的邻居, neighbor (v) 是节点v的邻居。
共有邻居相似度算法简单高效, 但是仅仅依靠共有邻居的多少来判断两个节点的相似度显然是不够的, 需要考虑社会网络的时间属性。
2.3 结合时间属性的链接预测算法设计
移动平均线是金融学中用来从短期的噪声数据中提取金融长期发展趋势的一种手段, 它通过求取某指标值在某段时间内的平均值来预测未来发展趋势。这里采用移动平均线的原理来提取平均共有邻居相似度。
定义5:假定有n个时间点的社会网络快照, 对于节点u和节点v, 其平均共有邻居相似度定义如下:
平均共有邻居相似度可以去除一些噪声数据, 从而得到一个较为平滑的长期趋势。
结合时间属性的链接预测算法设计如下:
输入:社会网络G=
输出:节点u和节点v的相似度
算法描述:
(1) 找出节点u和节点v在所有子图上的共有邻居;
(2) 根据定义5计算节点u和节点v的平均共有邻居相似度。
算法完毕。
3 结语
社会网络链接预测是数据挖掘的一个新的研究方向。链接预测侧重于挖掘社会网络中所隐藏的关系模式, 具有重大的研究意义。考虑节点的时间属性, 采用平均共有邻居相似度来平滑节点的动态变化, 可以有效去除噪声数据。本文将共有邻居相似算法与时间属性相结合, 提出了结合时间属性的链接预测算法。
参考文献
[1]G JEH, J WIDOM.Simrank:a measure of structural-context similarity[C].Proceedings of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002:538-543.
[2]张宗宇.社会化网络的链接预测[D].北京:北京邮电大学, 2011.
[3]胡谦谦.Markov逻辑网及其在社会网络中的应用研究[D].北京:北京交通大学, 2010.
[4]V LEROY, B B CAMBAZOGLU, F BONCHI.Cold start link prediction[C].Proceedings of 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2010:393-402.
[5]M A HASAN, V CHAOJI, S SALEM M ZAKI.Link prediction using supervised learning[C].SDM Workshop of Link Analysis, 2006.
链接算法 篇2
一、内链：就是内部链接，是指同一网站域名下的内容页面之间互相链接。如频道、栏目、终极内容页之间的链接，乃至站内关键词之间的Tag链接都可以归类为内部链接。
二、外链:就是你的网站连接到别人网站的链接，是你的网站通向其他网站的出口。比如，在自己网站的某一个页面上引用了一个标题，一张图片，点击一下这个标题或图片，可以跳转别人的网站去。这样的连接对于你的网站来说就是外链，而对于跳转到的那个页面来数就是反链。（曾看到有网友说，外链就是你自己网站的地址在别人的网站上出现，这个不对。）
三、反链:是单向链向你站的文字链接或图片带有ALT文字的链接或其它能够让现有搜索技术搜索到的链接。比如在bd上搜索某一个关键词，搜索结果中你自己的网站赫然在望，对于你的网站来说这就是反向链接，而对于bd来说就是外链，
外链和反链是成对出现的。自己的网站有外链自己肯定知道，但是被反链了不一定知道。
四、交换链接一般指的是A站和B站链接,从A站能链接B站,同时能从B站能访问A站,A和B之前的互相链接.（这个指的是双方都是知情的，主动的。不向反链是被动的。而且是双向互动的，也不像外链是单相思的。）
五、交叉链接就是别人用A站连你B站，你用B站连他C站。。就是一个换一个,是三个站之间的交换关系，或者站内几个页面的相互链接关系，形成一种网状。
六、友情链接是各个站长对建立友好关系的通用语，更多的一种社交的概念，主要表现形式就是交换链接，即网站与网站之间的连接。它把网上的网站一个一个地关链起来，访问者可以方便地从一个网站找到另一个网站。（实质上就是交换连接）
链接算法 篇3
摘要： 对搜索结果的排序是搜索引擎中至关重要的一项技术，算法的好坏直接关系到用户输 入关键词后能不能迅速查看到要查找的信息。系统的介绍超链接分析技术及基于超链接分析 的搜索引擎页面排序算法。对两种最基本的页面排序算法PageRank和HITS的算法思想和实现 原理进行详细阐述。通过分析对比，总结出它们各自存在的优点和不足进而指出适合其应用 的条件领域。最后指出搜素引擎应用超链接分析时应注意的一些影响因素。
关键词：搜索引擎；超链接分析；页面排序；PageRank；HITS
中图分类号：TP301文献标识码：A[WT]文章编号：16721098(2008)02007305
Analysis of Two Kinds of Search Engine Pageranking
Algorithm Based on Hyperlink Analysis
ZHANG Shujiang
(School of Computer Science and Engineering, Anhui University of Science and Tec hnology, Huainan Anhui 232001, China) Abstract: Search results sorting is a key technology in search engine, the algo rithmhas a direct influence on whether users can quickly find their expected i nformation afterkeywords are entered or not. The technology used for hyperlinkanalysis andpageranking algorithms based on hyperlink analysis were system ic ally presented. The ideas and principles of two of the most fundamental pager an king algorithms, PageRank and HITS, were expatiated. After analysis and comparis on, their respective advantages and disadvantages were summed up, and the condit ions and fields suitable for their application given. Finally some factors to benoted when search engine uses hyperlink analysis were pointed out.
Key words:search engine; hyperlink analysis; pageranking;PageRank; HITS
在互联网发展初期，网站相对较少，信息查找也比较容易。然而伴随互联网爆炸性的发展， 从1994年万维网（World Wide Web，WWW或Web）出现到现在短短十几年的发展，由于其开放 性和其上信息广泛的可访问性极大的鼓舞了人们创作的积极性使其日益发展成为一个最为丰 富庞大的信息资源库。对于一个普通互联网用户要想在这个硕大的信息库中找到自己所需的 资料简直如同大海捞针，这时为满足大众信息检索需求的专业搜索网站便应运而生了。
这些专业搜索网站的核心就是搜索引擎技术。而搜索引擎技术中搜索结果页面的排序算法在 搜索引擎中处于举足轻重的地位，因为排序算法决定了系统索引的网页与用户查询意图的相 关程度，同时也决定了网页在查询结果中出现的次序。它的好坏直接关系到用户输入关键词 后能不能得到要查找的信息。因此搜索引擎页面排序算法越来越受到众多研究学者的青睐， 尤其是基于超链接分析的排序算法更是层出不穷。
1超链接分析技术简介
传统的Web搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档。也有基 于目录分类的搜索引擎，比如早期的Yahoo、新浪的搜索服务。但这些搜索引擎的搜索结果 并不令人满意。因为有些网站拥有者为了使自己的网站在搜索结果中能排在较为前端的位置 故意提高某些关键字的出现频率从而破坏了搜索结果的客观性和准确性。此外，有些重要网 页可能并没有包含查询项因而也就不可能被搜索引擎检索到。
然而，一些研究学者们逐渐发现，Web上超链结构是个非常丰富和重要的资源，如果能够充 分利用的话，可以极大的提高检索结果的质量［1］189。进而提出了基于超链接分析 的搜索结果排序算法。文献［2］78提出的PageRank算法开启了超链接分析研究的热 潮 。超链接分析的基本原理是：在某次搜索的所有结果中（大型商业搜索引擎通常会有数十万 甚至上百万个搜索结果），被其它网页用超链指向越多的页面，其价值就越高，在输出排序 中就应该排得越靠前［3］。即一个网页的重要性取决于该网页被其它网页链接的数 量，特别是被一些已经被认定为“重要”网页链接的数量。
超链接分析其实是一种引用投票机制，也就说如果一个网页被另外一个网页链接一次就相当 于另一网页对其投了一票，其重要性被肯定一次。对于静态网页或网站主页，这种机制具有 一定的合理性。因为这样的网页容易根据其在互联网上受到的评价而产生超链接指向的数量 ，超链分析的结果可以从很大程度上反映该网页的实际重要程度，能够为搜索用户返回接近 其搜索意图且很有价值的搜索结果。事实上，超链分析技术除了分析网页本身的文字外，还 分析所有指向该网页的链接URL、链接文字、甚至链接周围的文字。这样，有时候即使某个 网页html1中并没有包含某个词，比如“下载”，但如果有别的网页html2用链接文字“下载 ”指向这个网页html1，那么用户在搜索“下载”这个关键词时也能找到网页html1。而且， 如果有越多网页（html2、html3、html4、html5…）用“下载”链接指向这个网页html1 ，或者给出这个链接的源网页（html2、html3、html4、html5…）越优秀，那么网页html 1在用户搜索“下载”时就会被认为越相关，在搜索结果中的排名也就会越靠前。
由此看见，所谓链接分析主要基于如下两个重要假设:①超文本链接包含了用户对一个网站 的判断信息;②对一个网站而言，如果其他网站链接到该网站的链接数（即入链数）越多， 则该网站越重要。这两个假设在各种基于链接分析的算法中均以某种方式体现出来［2 ］78。
基于这种超链分析思想，一些学者提出了许多页面排序算法。目前有：PageRank算法、HITS算法、SALSA（Stochastic Approach for LinkStructure Analysis）算法、PHITS算法（Probabilistic analogue of the HITS）；贝叶斯算法、Reputation算法［3］6。还有在各自的基础上进行改进而产生的算法变种。这些算法 有的已经在实际的系统中实现和使用，并且取得了良好的效果。在这些算法中，PageRank和 HITS是最著名也是最基本的页面排序算法，其它算法是在两者基础之上进行某种程度的改进 版。下面对这两个基本算法作个详细的介绍与分析以为以后的研究工作做好基础准备工作。
2基于超链接分析的算法
2．1PageRank算法
2.1.1基本思想在基于超链接分析的排序算法中，PageRank算法是最有名的一种。它最初是Sergey Brin和L awrence Page在1998年提出的，后来被用在世界上最著名的搜索引擎Google中一直到今天。 Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在搜索结果集中的出现 位置，PageRank值越高的网页，在结果中出现的位置越靠前。
其基本思想是:如果某一网页玊存在一个指向网页A的链接，则表明网页T的所有者认为网页 A是比较重要的，从而把T重要性得分值（即网页T的PageRank值）的一部分赋予獳。A 得到的分值大小由玊的PageRank值玃R(T)和T的出链(从T链出的链接)数C(T)决定。用公 式表示为:PR(T)/C(T)。因而对于页面A，其PageRank值玃R(A)就是从所有指向它的页 面分得的重要性分值的总和。可用以下公式计算オPR(A)=PR(T1)/C(T1)+…+
PR(Tn)/C(Tn)(1)
其中：玊1、T2、T3…Tn为含有指向A的链接的页面。
由于互联网上也存在一些页面没有入链或出链那么就无法计算其PageRank值。为避免这个问 题（即所谓的LinkSink问题）一些研究学者对其进行改进，为式（1）添加一个阻尼系数 玠使其变为
PR(A)=(1-d)+d［PR(T1)/C(T1)+…+PR(Tn)/C(Tn)］(2)
玠为阻尼系数，Google常指定为0.85［4］。这样在整个网络内的页面经过多次递 归迭代计算，直到PR值达到收敛即求得页面的PageRank值。
2.1.2优缺点分析从以上PageRank的计算公式中也以看出，一个页面会将自己的PageRank值均匀的分配给它所 引用的页面，它引用的页面越多，每个被它引用的页面所分得的PageRank值越少。因而一个 页面会因为别的页面对自己的引用而增加自己的PageRank值，但并不会因为自己对别的页面 的引用而提高自己的PageRank值。这样，对于一个网页来说要想获得较为靠前的排名就要获 得较大的PageRank值，而要获得较大的PageRank值就要被较多重要的网站所引用，因为只有 那些重要网站才有较大的PageRank值。而如果两个页面各自本身的PageRank值都很低，则它 们互相链接后也增加不多，重复链接对两者更是有害无益。由于页面的链接数越多，被链接 页面得到的PageRank值就会越低因此高级别的网站也不会与质量不高的网站互换链接。一个 网站要想获得较高级别的PageRank值就只有一个办法那就是要求网站拥有者老老实实地做好 自己的每一个网页，提高整个网站的质量水平才能换得高级别网站的链接。所以PageRank技 术可以很有效的避免某些网站为获得较高排名来欺骗搜索引擎。
PageRank技术的另外一个优点在于它是一个与查询无关的静态算法。尽管所有网页的PageRa nk值都要通过进行递归迭代计算以求得收敛值，这一过程中计算量很大，但这些计算不要求 实时性，可以离线计算获得结果后保存起来。这样能有效的减少在线查询时的运算量极大的 缩短查询响应时间。
然而，PageRank技术的缺点也是显而易见的。因为PageRank仅仅依靠计算网页的外部链接数 量来决定该网页的排名，而完全忽略了页面的主题内容与用户查询意图的相关性从而影响搜 索结果的相关性和准确性。另外，有一些Hub页本身并不突出，除了链接外也没有多少内容 也没有多少链接指向它，但它却指向了某个话题最突出的页面链接。可以说一个好的页面由 多个好的Hub页面所指向，一个好的Hub页面指向多个好的页面。这应该是一种互动关系，但 在PageRank中并没有考虑到［5］。再者，对于一些较新的网页由于还没有被发现故 被引用的次数很少因而即使质量很高也不会获得很高的PageRank值。也就是说PageRank会对 新网页表现很大的歧视性。
2．2HITS算法
2.2.1基本思想HITS（Hyperlink Induced Topic Search）算法是Kleinberg在1998年提出的，是基于超链 接分析排序算法中另一个最著名的算法之一。在该算法中,按照超链接的方向,将网页分成两 种类型的页面：Authority页面（权威页）和Hub页面（目录页）。二者是HITS算法中两个十 分重要的概念。Authority页面是指与某个查询关键词和组合最相近的页面；Hub页面是指它 的出链中包含了很多的Authority页面的页面，它的主要功能就是把这些Authority页面联合 在一起［6］。
HITS基本思想是：将查询玵提交给传统的基于关键字匹配的搜索引擎，搜索引擎返回很 多网页，从中取前玭个网页作为根集(Root Set)，用玆表示。R一般满足如下三个条件 ：① R中网页数量相对较小；② R中网页大多数是与查询q相关的网页；③ R中包 含 较多的权威网页。然后根据这个集合R在整个网页有向图中的位置来扩展这个根集合。即通 过向R加入被R引用的网页和引用R的网页将R扩展成一个更大的集合称为基集T。在得到这 个集合后，就开始计算集合中每个网页的目录型权值和权威型权值。利用Authority页面和H ub页面互相增强属性,对集合玊进行链接分析,通过迭代的计算方法为玊中的每个页面 计算一个Authority值和一个Hub值,作为结果页面排名的依据。
假定基集玊中的页面分别为 1，2，3，…玴 。每个页面玴有一个Authority值玜 p和Hub值玥p；页面玴的入链页面集表示为Bp(m），出链页面集表示为獸p（n ）。则ap和hp用如下公式进行计算
ap=∑[DD(]m[]i=1[DD)]hi(i∈Bp(m))
hp=∑[DD(]n[]i=1[DD)]ai(i∈Fp(n))
这样的递归式很容易用矩阵方法表示。令所有选出来的网页都进行标号，得到所有网页的编 号集｛1,2,…,玭｝。令相邻矩阵A为一个n×n的矩阵，如果存在一个从 网页i 链接到网页j 的超链，就令矩阵中A的第（i, j）个元素置为1，否 则置为0。同时，将所有网页的权威型 权值x和目录型权值y都分别表示成向量x=(x1,x2,x3,…,xn),y=(y1,y2,y3, …,yn)。由此可以得到计算x和y的简单矩阵公式：y=A•x,x=A 琓•y其中A琓是A的转置矩阵。进一 步，我们有：
x=A琓•y=A琓•Ax=( A琓A)•x
y=A琓•x=AA琓y=(AA琓)• y
因此向量玿,y均可经过多次迭代而得。经过一定次数的递归运算后，会得到集合中每个网 页的权威型权值和目录型权值。按照这两个不同的权值，分别取出前k个页面输出返回给 用户。根据线性代数的理论,迭代序列经过标准化最终将收敛于矩阵A的 特征向量,即上文计 算的Hub权值和Authority权值是页面集合的固有特征,不是由初始向量和参数的选择决定的 。
2.2.2优缺点分析由HITS的计算过程我们可以看出这种算法是一种依赖于查询关键字的算法。每得到一个检索 ，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子图，再通过 运算获得各个网页的相应链接权值。实际应用中，由R生成T的时间开销是很昂贵的 ，需要下 载和分析R中每个网页包含的所有链接，并且排除重复的链接。一般玊比R大很 多，由T生 成有向图也很耗时。需要分别计算网页的A/H值，计算量比PageRan k算法大。已有实验数据 表明，这种算法获得的排名准确性高于PageRank算法。但在用户检索时进行如此大量的运算 ，检索效率显然不高。
HITS算法最大的弱点是处理不好主题漂移问题（topic drift），也就是紧密链接TKC（Tigh tlyKnit Community Effect）现象［7］。由于HITS只计算主特征向量，也就是只 能发现玊集合中的主社区（Community），忽略了其它重要的社区。如果在集合玊中 有少数与查询主题无关的网页，但是他们是紧密链接的，HITS算法的结果可能就是这些网页 ，从而偏离了原来的查询主题。因此，HITS更适合于宽主题的查询。
另外，HITS算法不能有效的识别网站制作者对搜索引擎的欺骗。Web页面中有许多链接是为 其他目的而创建的,例如付费广告、网站本身导航等等,因此单凭链接数目来判断页面的Auth ority值和Hub值,是不合理的。
用HITS进行窄主题查询时，还可能产生主题泛化问题，即由根集到基集的扩展后引人了比原 来主题更重要的新主题，新主题可能与原始查询无关。泛化的原因是因为网页中包含不同主 题的向外链接，而且新主题的链接更加具有重要性。
3超链接分析应注意的问题
基于超链接分析的算法，提供了一种衡量网页质量的客观方法，独立于语言，独立于内容， 不需人工干预就能自动发现Web上重要的资源，挖掘出Web上重要的社区，自动实现文档分类 ［3］4。但由于互联网的开放性和自由性使得Web页面上的超链接也呈现鱼龙混杂状 态，给超链分析工作带来一定的干扰和欺骗。避害趋利，力求算法做到最大程度的精确 有效。有一些共同的问题影响着算法的精度我们必须给与重视。
(1) 根集的质量根集质量应该是很高的，否则，扩展后的网页集会增加很多无关的网页， 产生主题漂移，主题泛化等一系列的问题，计算量也增加很多。算法再好，也无法在低质量 网页集找出很多高质量的网页。
(2) 噪音链接Wed上不是每个链接都包含了有用的信息，比如广告，站点导航，赞助商， 用于友情交换的链接，对于链接分析不仅没有帮助，而且还影响结果［1］196。如何 有效的去除这些无关链接，也是算法的一个关键点。
(3) 锚文本的利用锚文本有很高的精度，对链接和目标网页的描述比较精确。在具体的实 现中我们应大加利用锚文本来优化算法。如何准确充分的利用锚文本，对算法的精度影响很 大。
(4) 查询的分类每种算法都有自身的适用情况，对于不同的查询，应该采用不同的算法， 以求获得最好的结果。因此，对于查询的分类也显得非常重要。
4结束语
随着Internet上信息量的爆炸式增长，人们越来越依赖于搜索引擎获取所需信息。虽然目前 的商用搜索引擎取得了很大的成功，但还有许多方便需要进一步完善。本文主要对基于超链 接分析的两种最基本的搜索结果排序算法PageRank和HITS进行了详细介绍和分析对比。希望 为将来在这两种算法思想的基础上进行改进，提出更精确更完善的排序算法打下基础。搜索 引擎的研究是一个热点,要能真正的研究并有所创新,对现有基础技术理论的学习和深入理解 是基础。
参考文献：
［1］李晓明，闫宏飞，王继民.搜索引擎——原理、技术与系统［M］.北京：科 学出版社,2004：189，196.
［2］吴江.使用超链分析技术的搜索引擎［J］.图书情报工作，2004，48(7)：78 81.
［3］李绍华，高文宇.搜索引擎页面排序算法研究综述［J］. 计算机应用研究，2007,24(6):47.
［4］刘琨，郑有才.搜索引擎剖析［J］.微机发展，2004,14(3):1922.
［5］徐宝文,张卫丰.搜索引擎与信息获取技术［M］. 北京:清华大学出版社,200 3：109110.
［6］张娜，张化祥.基于超链接和内容相关度的检索算法［J］. 计算机应用，2 006,26(5):1 1711 173.
［7］郑煜,钱榕.一个基于链接分析的相关度排序算法及其在专题搜索引擎中应用 ［J］.计算机应用与软件，2007，24（7）：5455.
基于链接分析的HITS算法研究 篇4
关键词：HITS算法,权威网页,中心网页
0 引言
互联网与传统数据环境相比, 具有另一种丰富的信息, 就是互联网的超链接拓扑结构。链接能反映一种思想:如果存在一条超链接从网页A指向网页B, 那么A的作者认为B包含了有价值的信息, 且B中的信息是与A相关的。HITS (Hyperlink-Induced Topic Search) 算法是Web结构挖掘中最具有权威性和使用最广泛的算法, 其基本思想为利用页面之间的引用链来挖掘隐含在其中的有用信息 (如权威性网页) , 具有计算简单且效率高的特点。
1 HITS算法
广泛主题搜索过程往往返回大量的结果以至于用户无法消化。针对这种情况, Kleinberg致力于提供有效的搜索方法过滤网页以得到一个最权威的网页集合。根据权威性网页能被大量的网页作者所认可的特点, Kleinberg于1999年提出了关于超链接的检索算法--HITS算法。HITS算法基本思想是通过网页的链接分析得出每个网页的权值从而得出网页的权威性。HITS算法将页面分为两种类型:一种为表达某一主题的权威页面, 称为Authority页面;另一种为能把这些Authority页面联结在一起的页面, 称为Hub页面。HITS算法涉及两个重要的权值概念:
Authority:表示一个权威网页被其它网页所引用的加权数量, 即该权威网页的加权入度值。若某网页被引用的数量越大, 则该网页的加权入度值越大, Authority越大。
Hub:表示一个Web页面指向其它网页的加权数量, 即该Web页面的加权出度值, 它提供了指向权威页面的链接集合。若某网页的加权出度值越大, 则该网页的Hub值越大。Hub起到了隐含说明某话题权威页面的作用。
1.1 创建万维网集中子图
设查询字段为σ, 创建一个网页集合Sσ使其满足以下条件:
(1) Sσ相对较小;
(2) Sσ包含了丰富的与查询相关的网页;
(3) Sσ包含了绝大多数最重要最权威的网页。
网页集合Sσ的收集过程:首先从一个基于文本的搜索引擎如Alta Vista开始, 得到关于的查询字段σ排序最先的t (t为参数, 一般设置为200) 个网页, 称这t个网页为根集合Rσ。此根集合满足上述 (1) 、 (2) 的要求, 但与 (3) 的要求相差甚远。因为在Rσ中的网页只有很少的链接。实验表明, 查询词"java"的Rσ集合中网页仅有15个链接关系, 而查询词"censorship"只有28个链接, 与200个根集合Rσ中的网页潜在链接数200×199=39800相比是极少的, 算法所基于的思想是权威网页必将有大量的链接。因此, 需要利用Rσ集合来产生满足三个条件的Sσ集合。HITS算法的另一个思想是:与主题相关的权威网页极有可能被Rσ中至少一个网页所指向。
通过沿Rσ中网页链接来增加子图中权威网页的数量。具体地, 通过如下过程实现Sσ的收集过程:
根据上述过程将得到的Sσ集合称为查询σ的基础集合。实验中令t=200, d=50在Alta Vista中构建的基础集合Sσ, 满足上述三个条件, 集合所含的网页数量介于1000到5000之间。图1表明了基础集合的收集过程。
1.2 HITS算法数据结构描述
HITS算法使用的数据结构为图G[Sσ]= (V, E) , 其中结点集合V是所有属于Sσ的网页, 而边集合E为属于且仅属于基础集合Sσ中网页之间的链接, 其中的有向边 (p, q) 表示链接从网页p指向网页q。
1.3 Authority权威度和Hub中心度的计算
Hub中心网页和Authority权威网页之间显示了一种相互加强的关系:好的Hub网页会指向Authority网页;Authority网页会被许多好的Hub网页所指向。利用中心网页和权威网页之间的关系, 通过一个交互算法来保持并更新每个网页数值权重。
HITS算法输入数据是图G[Sσ]的一个N×N (N为Sσ所含网页个数) 的相邻矩阵A, 其中如果网页i存在一个链接到网页j, 则Aij=1, 否则Aij=0。
HITS算法为每个网页i分配两个度量值:中心度hi和权威度ai。设向量a= (a1, a2, …, aN) 代表所有基础集合中网页的权威度, 而向量h= (h1, h2, …, hN) 则代表所有的中心度。最初, 将这两个向量均置为u= (1, 1, …, 1) , 操作In (a) 使向量a=ATh, 而操作Out (h) 使向量h=Aa。反复迭代上述两个操作, 每次迭代后对向量a和h范化, 以保证其数值不会使计算溢出。Kleinberg证明经过足够的迭代次数, 向量a和h将分别收敛于矩阵ATA和AAT的主特征向量。通过以上过程可以看出, 基础集合中网页的中心度和权威度从根本上是由基础集合中的链接关系所决定的, 更具体地说, 是由矩阵ATA和AAT所决定。
2 HITS的改进算法
HITS算法遇到的问题, 大多是因为HITS是纯粹的基于链接分析的算法, 没有考虑文本内容, 没有区别对待不同的链接 (即没有区分链接的重要性) 。继Kleinberg提出HITS算法后, 很多研究者对HITS进行了改进, 这里主要介绍ARC算法和SALSA算法。
2.1 ARC算法
IBM Almaden研究中心的Clever工程组提出了ARC (Automatic Resource Compilation) 算法, 以HITS算法为核心, 并试图通过增加对网页内容信息的利用来克服HITS算法的主题漂移。ARC算法考虑在链接 (href) 周围的文本内容会较大程度地反映链接所指向的网页的内容。如果这个链接周围的文本出现了查询的主题, 那么可以更加确信链接所指向的网页也是与查询主题相关的。这样在赋予网页集对应的邻接矩阵初值时结合了链接锚文本内容, 适应了不同的链接具有不同权值的情况。
剩下的问题就是如何将这种信息反映到HITS算法的迭代过程中, 基本思想是为每个链接分配一个权值w (p→q) , 如果p到q的链接周围出现的与主题相关的文本越多, 那么这个链接的权值也就越高。与HITS算法一样, 迭代过程也始于两个向量x和y, 其分量的初值均设为1, 但与HITS算法不同, 相邻矩阵的构造不再是布尔型矩阵。邻接矩阵W的每一项对应于一对网页, 如果他们之间存在链接, 则Wpq=w (p→q) , 反之。迭代过程的每一步可以表示为x=WTy, y=Wx。
如何将链接 (href) 周围的文本映射成一个量化的权值呢?Chakrabarti的方法是将href的左右看作是一个B字节的窗口 (包括和之间的文本) 。B是一个由实验决定的参数, 设n (t) 表示在窗口中出现的与主题相关的词 (用户查询的关键词) 的频度, 那么链接权重的定义可以表示为W (p→q) =1+n (t)
2.2 SALSA算法
从理论基础上看, SALSA算法基于概率论中的马尔可夫链原理, 并依赖于数据收集时的"随机漫游"的随机特性。
R.Lempel和S.Moran在SALSA算法中, 仍然沿用了HITS算法的两个基本概念, 将网页分为两类, 即Hubs和Authorities。对每个页面而言, 它们也有两个权重, 即hub weight (中心权重) 和authority weight (权威权重) 。与此同时, SALSA算法更强调Web用户浏览的随机性及向前浏览网页的直觉知识, 借鉴了Page R-ank算法的随机冲浪思想, 同时摈弃了HITS算法所描述的hub与authority相互增强的方法
具体的算法步骤如下:
(1) 首先用基于文本的搜索引擎 (如Alta Vista或Hotbot) 来得到查询式的结果, 取排名最高的前t位形成根集Rσ, 其中的t一般取值为200。其次, 扩充根集, 分两步进行, 一是将所有Rσ所指向的页面扩充进去, 该扩充在数量上没有限制;二是将指向Rσ的每一页面的链接页面取其中任意d (d<=50) 个页面扩充到原来的Rσ中形成基本集Sσ去除无关链接, 如内在链接、CGI脚本链接、广告和赞助商的链接等, 只保留提供信息的链接, 形成集合Gσ。
(2) 从集合Gσ中构造二分无向图G'= (Vh, Va, E) , 其中Vh={sh|s∈C and out-degree (s) >0} (G'的hub边) ;Va={sa|s∈C and in-degree (s) >0} (G'的authority边) 。E={ (sh, sa) |s→r in Rσ}。从而定义了两条马尔可夫链, 即hub链和authority链。
(3) 通过定义矩阵方法分别定义了hub矩阵和authority矩阵, 并求出其特征向量, 即可找出两条马尔可夫链的静态分布。其中authority矩阵中值大的网页即为所求的authority网页。
3 结束语
HITS算法是Web结构挖掘中的重要算法之一, 针对该算法存在的一些问题, 许多学者提出了各种改进算法, 且这些改进算法还在不断研究发展中。通过改进的HITS算法, 可以获得高的查询精确度, 当然, 也可能增加了算法的复杂度。如何改进HITS算法, 使其具有较高查准率和查全率, 同时又能降低算法的复杂度, 这应是HITS算法研究的方向。
参考文献
[1]KLEINBERG J.Authoritative sources in a hyperlinked environment[C]Proceedings of the9th ACM-SIAM Symposium on Discrete Algorithms.New Orleans.ACM Press, 1997.
[2]Sergey Brin, Lawrence Page.The Anatomy of a Large-Scale Hy-pertextual Web Search Engine.Proceedings of the Seventh Interna tional Conference on World Wide Web7, Brisbane, Australia, 1998Amsterdam, The Netherlands, The Netherlands, Elsevier Scienc Publishers B.V., 1998.
[3]ZhangMin, Gao Jianfeng, Ma Shaoping.Anchor Text and Its Con text Based Web Information Retrieval.Journal of Computer Re search and Development, 2004 (1) .
[4]王晓宇, 周傲英.万维网的链接结构分析及其应用综述[J].软件学报, 2003 (10) .
[5]冯国臻.基于结构分析的大规模WWW文本信息检索技术的研究[D].北京:中国科学院计算技术研究所, 2001.
[6]张聪.基于HITS的链接分析算法研究与改进[D].大连:大连理工大学, 2007.
[7]刘悦.WWW上链接分析算法的若干研究[D].北京:中国科学院2003.
硬链接和符号链接的区别 篇5
链接是一种在共享文件和访问它的用户的若干目录项之间建立联系的一种方法。Linux中包括两种链接：硬链接（Hard Link）和软链接（Soft Link），软链接又称为符号链接（Symbolic link）。
一、硬链接
硬链接说白了是一个指针，指向文件索引节点，系统并不为它重新分配inode.可以用：ln命令来建立硬链接。语法：
ln [options] existingfile newfile
ln[options] existingfile-list directory
用法： 第一种：为“existingfile”创建硬链接，文件名为“newfile”.第二种：在“directory”目录中，为“existingfile-list”中包含的所有文件创建一个同名的硬链接。常用可选[options] –f 无论“newfile”存在与否，都创建链接。-n 如果“newfile”已存在，就不创建链接。
下面举一些例子：
$ ls –il
13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1
13059 -rwx - - - - - - 1 longcheng longcheng 57 8月 5 16:40 file2
$ ln file2 file2hard
$ ls –il
13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1
13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2
13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2hard
注意在创建链接前，file1 显示的链接数目为1,创建链接后（1）file1和file1hard的链接数目都变为2;（2） file1和file1hard在inode号是一样的（3） file1和file1hard显示的文件大小也是一样。可见进行了ln命令的操作结果：file1和file1hard是同一个文件的两个名字，它们具有同样的索引节点号和文件属性，建立文件file1的硬链接，就是为file1的文件索引节点在当前目录上建立一个新指针。如下图，你可以删除其中任何一个，如rm file2 ,每次只会删除一个指针，
链接数同时减一，只有将所有指向文件内容的指针，也即链接数减为0时，内核才会把文件内容从磁盘上删除。当前目录逻辑结构：（不好意思图没有显示出来）。
还可以在不同目录，但同一文件系统中建立文件的硬链接。设file1、file2在目录/home/longcheng/dir1中，下面的命令，在/home/longcheng中建立file2的硬链接。
ln file2 /home/longcheng/file2hard
下面的程序，是将dir1目录中所有文件，在目录dir2中建立硬链接
$mkdir dir2
$ln /home/longcheng/dir1/* /home/longcheng/dir2
如果使用了 ln –f existingfile newfile,如果newfile已经存在，则无论原来newfile是什么文件，只用当前用户对它有写权限，newfile就成为exisitngfile的硬链接文件，
尽管硬链接节省空间，也是Linux系统整合文件系统的传统方式，但是存在一下不足之处：（1）不可以在不同文件系统的文件间建立链接（2）只有超级用户才可以为目录创建硬链接。虽然很多树上说root用户可以创建，但是笔者在学习过程中发现即使是root用户也不能创建，我的系统是Redhat,内核2.4、2.6都试过，在其他系统中不知道是不是可以。其实， 在ubuntu下，切换到超级用户也是不能为目录创建硬连接的。
注意，硬连接的文件容量是要成倍增加的。
二、软链接（符号链接）
符号链接是对一个文件的间接指针。硬链接直接指向文件的i节点。
软链接克服了硬链接的不足，没有任何文件系统的限制，任何用户可以创建指向目录的符号链接。因而现在更为广泛使用，它具有更大的灵活性，甚至可以跨越不同机器、不同网络对文件进行链接。
建立软链接，只要在ln后面加上选项 –s,下面举个例子
$ ls -il
13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1
13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2
13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2hard
$ln –s file1 file1soft
$ls -il
13058 -rwx - - - - - - 1 longcheng longcheng 48 8月 5 16:38 file1
13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2
13059 -rwx - - - - - - 2 longcheng longcheng 57 8月 5 16:40 file2hard
13061 lrwxrwxrwx 1 longcheng longcheng 5 8月 5 16:58 file1soft->file1
从上面链接后的结果可以看出来软链接与硬链接，区别不仅仅是在概念上，在实现上也是不同的。区别：硬链接原文件&链接文件公用一个inode号，说明他们是同一个文件，而软链接原文件&链接文件拥有不同的inode号，表明他们是两个不同的文件；在文件属性上软链接明确写出了是链接文件，而硬链接没有写出来，因为在本质上硬链接文件和原文件是完全平等关系；链接数目是不一样的，软链接的链接数目不会增加；文件大小是不一样的，硬链接文件显示的大小是跟原文件是一样的，这用强调，因为是等同的嘛，而这里软链接显示的大小与原文件就不同了，file1大小是48B,而file1soft是5B,这里面的5实际上就是“file1”的大小。
总之，建立软链接就是建立了一个新文件。当访问链接文件时，系统就会发现他是个链接文件，它读取链接文件找到真正要访问的文件。
在不同系统之间建立软链接、对目录建立链接，这里就不举例了，读者可以自己去尝试，我也是在不断实践中学习的。
链接算法 篇6
互联网出现了许多在线社交网站, 用户在该平台下可发布、分享信息, 吸引了越来越多的用户。最近一些文献将此类数据建模为“内容网络 (text-associated network) ”, 网络节点表示社交网站的用户, 链接表示用户间的各种关系, 不同于传统网络, 节点包含内容属性, 表示用户产生的内容信息。将社交平台产生的数据建模为内容网络, 挖掘其潜在结构可为基于该平台的应用服务提供依据, 社区发现是一种基本的结构分析技术。
社区发现的方法很多[1], 大致分为基于链接的方法、基于内容的方法及基于链接和内容的方法。研究表明基于链接的方法因链接存在噪音或缺失链接, 导致错误的分析结果;基于内容的方法大多采用生成式模型, 内容属性的不相关性使分析性能低;融合内容和链接的社区发现方法优于基于单个信息的分析。文献[2]提出了一个有向网络的社区发现概率模型 (PPL模型) , 对网络的有向链接生成过程建模, 并引入流行度 (node popularity) 变量对节点的入链 (incoming links) 建模, 引入节点生成度 (node productivity) 变量对节点的出链 (outgoing links) 建模, 最后通过EM算法求解生成模型的参数。PPL模型是一个通用框架, 可将各类概率链接分析模型统一, 是目前较优的链接分析模型。但该模型没有考虑节点的内容信息, 且不能处理大型网络。本文提出一个有效的融合内容和链接的社区发现算法, 根据网络链接和内容信息进行网络抽样[3], 以适应大型网络的处理;对抽样后的网络采用PPL模型建模。
1 内容网络社区发现算法
PPL模型可以准确地发现网络的潜在社区结构, 但其不能处理大型网络, 且没有考虑节点的内容属性。这里将网络节点的内容属性转换到网络的链接中, 并利用采样方法对网络链接进行稀疏化。
本文处理的网络记作G= (V, EL, T) , 其中V表示网络节点集合, E表示网络的实际链接集合, T表示节点的内容属性集合。
算法samplePPL主要步骤如下: (1) 预处理阶段:根据网络节点的内容属性T创建内容链接集合EC;将内容链接和网络实际链接融合后的网络抽样得链接集合E; (2) 社区发现节点:基于PPL模型对链接集合E形成的网络建模和求解。
下面分别给出各步骤的具体实现细节。
1.1 预处理阶段
对V中的每个节点Vi, 可从T中找到其的内容属性向量, 内容向量的每维元素表示相应属性值的TF-IDF取值, 如果不是此值, 需转换为该形式。利用余弦函数可得每个节点的最相似的k个近邻。将每个节点和其k个最近邻间建立链接, 这些链接集合就构成了内容链接集合EC。
将内容链接集合EC和网络实际链接集合EL进行合并得到一个比初始网络更稠密的内容网络, 其不仅融入链接信息, 还融入了节点的内容信息。为了使算法处理的效率更高, 需要对网络链接进行裁剪。对每个节点Vi进行如下操作:
从EC和EL中选择节点Vi的最相似的m个节点, 保留其与这些节点间的链接, 其余删除。
对EC边节点Vi与另一个端点的相似度可以根据内容链接建模节点获得。
对EL边节点Vi与另一个端点Vj的相似度通过Jaccard系数计算相似度:
其中nei (x) 表示在EL中节点x的邻居节点集合。
对相似度值进行均一化, 保留两类边中相似度大于阈值的边。按照某种融合规则对节点间的内容相似度和链接相似度进行融合, 选择与节点Vi融合相似度最大的节点, 保留Vi与它们的链接。
构造抽样网络的链接E:
根据上述步骤可得每个节点Vi的最近邻节点集合, 将Vi与其近邻间边加入到链接集合E。
对所有节点进行上述操作, 则得到所有内容网络抽样网络的链接集合E。
1.2 社区发现阶段
其中γik表示节点i隶属社区k的概率, ai表示节点i产生链接的概率, bj表示节点j接受链接的概率。
根据上述生成过程可得网络的似然函数:
采用EM算法最大化公式 (2) 的似然函数值, 可得模型的参数γik, ai和bj。
根据γik (k=1, …, K, K为社区个数) 可得节点i隶属于各个社区的概率, 如果需要对节点进行硬指派, 选择隶属度最大的社区作为节点i的社区。
根据ai可知节点的中心度, 根据bj可知节点的权威度。
2 实验
为了验证社区发现算法samplePPL的有效性, 在Cora[4]和Citeseer[5]数据集上进行测试, 并与PPL模型的实现算法进行比较。实验环境为Windows XP系统, 运行环境采用Visual studio 2010 (C#语言) , PC机配置为主频3.0GHz, 内存2.0GB。如文献[2], 算法准确度结果的评价标准采用NMI、PWF和Modu, 表1和2给出了比较结果。
由表1和2可知本文提出的算法samplePPL由于引入节点的内容信息, 优于PPL模型。另外由于sampleP-PL采用了采样预处理, 算法运行的速度也比PPL要快。
3 结语
本文提出了一个社区发现算法, 其将节点的内容信息融合到网络的链接中, 并利用采样方法对链接进行过滤, 基于过滤的链接建立PPL模型对节点进行划分。该算法还有待采用更多技巧来提高速度。
摘要：设计一个社区发现方法挖掘在线内容网络的潜在结构, 在预处理阶段基于网络的链接和节点内容属性对内容网络进行重构, 基于重构网络进行链接抽样;在社区发现阶段利用概率链接模型对采样后的网络建模, 并用EM算法求解模型参数, 根据参数可得内容网络的潜在结构。
关键词：社区发现算法,链接分析,内容分析,概率模型
参考文献
[1]YANG TB, JIN R, CHI Y, et al.Combining link and content for community detection:a discriminative approach[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009:927-936.
[2]YANG TB, CHI Y, ZHU S, et al.Directed network community detection:A popularity and productivity link model[C]//Proceedings of the SIAM Conference on Data Mining, 2010:742-753.
[3]RUAN YIYE, FUHRY DAVID.Parthasarathy srinivasan.efficient community detection in large networks using content and links[J].CoRR abs, 2012 (12) .
链接算法 篇7
社会网络是一种有效的对人们之间的交互行为进行建模的方法。从图论的角度分析, 社会网络是一个图, 图中的节点表示人, 图中的边表示人们之间的交互行为。在社会网络中, 一部分人往往拥有共同的兴趣和爱好, 这些人在一起组成了一个小的社团。然而随着时间的推移, 人们的生活习惯也在不断的发生变化。例如, 用户在社交网站中进行注册, 或者和某人建立了好友关系等等。这些行为使得社会网络形成的图是在不断变化的, 研究复杂网络的动力学是一项复杂的问题。相比之下, 研究社会网络中两个特点节点的关系是一项简单的任务。例如, 节点间的关系模式如何随时间的改变而改变?哪些因素迫使节点间的关系模式如此改变?其它的节点通过什么方式影响两个节点间的关系?本文研究的内容是复杂的社会网络中的链接预测问题, 即预测两个不相关联的节点间建立关联的可能性[1]。
随着Web和社交网络的日益发展, 链接预测问题在近几年是社会网络领域的重点研究内容之一, 其主要应用在社交网络、生物网络、学者合作网络等领域。在社会网络中, 链接预测是指根据网络中已有的信息预测该网络在未来可能出现的链接。网络中的已有信息主要有两种:网络的链接结构和节点的属性。社会网络中的节点链接并不是均匀的。简单地利用网络的链接结构进行链接预测的方法有Newman的相同近邻方法[2], 该类方法考察两个节点的相同的邻居数目, 并没有考虑链接的权重。基于随机游走的链接预测方法同时考虑了网络的链接结构和网络中边的权重。
在微博服务中, 用户频繁地在网络中发言, 他们发言的内容可以作为节点的属性用来进行好友推荐, 即链接预测。然而, 用户不停的在网络中发言, 这样系统长期积累了海量的用户发言信息。这些海量的用户发言信息增加了好友推荐算法的执行时间。此外, 随着用户关注点的不断变化, 大量的历史发言也会影响好友推荐的准确度。
本文研究了时间变化对用户好友推荐的影响, 设计了一种基于随机游走的时间加权社会网络链接预测算法。该算法将时间属性作为重要的维度, 通过随机游走的方式对其他用户进行排名, 然后将排名靠前的用户作为好友推荐给当前用户。
1 相关工作
网络中节点的链接预测方法主要有三种:基于相似性的方法, 极大似然估计法和概率模型方法。
1.1 基于相似性的方法
基于相似性的方法是最简单的链接预测方法。在基于相似性的方法中, 任意两个节点x和y都有一个相似性值sxy。根据这些节点间的相似性值将其进行排名, 相似性值越大, 说明这两个节点在未来建立链接关系的可能性就越大。在该类方法中, 如何定义节点间的相似性是最大的挑战。在定义节点间的相似性过程中, 可以根据图中节点间的局部关系, 如公共邻居[2], 优先链接[3]等;可以根据节点在图中的全局信息, 如矩阵森林指数[4], 余弦相似性[5]等;也可以根据节点间的半局部指数, 如局部路径指数[6], 局部随机游走[7]等。基于相似性的链接预测方法的优点是可以利用矩阵的协同过滤方法来提高预测的准确性, 缺点是没有利用网络已有的链接关系, 主要应用于隐式的网络链接预测。
1.2 极大似然估计法
极大似然估计法假设网络的组织结构符合某种规律, 然后按照此种规律对网络进行建模, 模型中含有参数。在建立了带参数的网络模型后, 按照已有的数据对网络进行评估。在参数按照极大似然估计法计算出来之后, 根据该模型对未来可能建立的链接进行预测。典型的极大似然估计法有层次结构模型和随机块模型。
大量的实验表明, 许多真实的社会网络都是按照层次结构组织的[8]。在这类网络中, 节点被划分成许多的小组, 这种小组又进行划分为稍大点的小组, 依次类推知道构成一个庞大的网络。关注社会网络的层次结构可以更好地预测网络中尚未存在的链接。更准确地说, 层次结构模型可以揭露网络中隐含的层次结构。设计良好的极大似然估计算法可以在合理的时间内处理网络规模在几千个节点的网络上, 但是当网络规模在几百万节点的社会网络中却无能为力。随机块模型[10]是最常用的网络模型之一。在随机块模型中, 节点被划分为许多的小组, 两个节点链接的概率完全取决于他们所在的小组。随机块模型可以描述网络的社团结构, 角色到角色的链接, 以及其它的可能建立链接的因素。极大似然估计法的缺点是耗时长, 不能应用于大规模的社会网络链接预测。此外, 极大似然估计法的准确性也是有限的, 明显低于基于相似性的算法。然而, 极大似然估计法可以很好地洞察网络的组织结构, 这是其它链接预测算法达不到的[9]。
1.3 概率模型方法
概率模型是对社会网络的结构进行抽象, 然后利用机器学习的方法预测网络中尚未存在的边。给定一个社会网络G= (V, E) , 概率模型建立一个包含多个参数Θ的目标函数, 此函数可以很好描述社会网络的结构。假设节点i和j尚未建立链接, 那么节点i和j之间建立链接的概率为P (Aij=1|Θ) 。通过对目标函数进行优化, 我们便可以得到P (Aij=1|Θ) 的实际取值。典型的概率模型算法有概率关系模型 (有的文献中将其称为关系贝叶斯网络) [11], 概率实体关系模型[12]和随机关系模型。概率模型方法的缺点是需要对具体的网络结构进行抽象, 不是一种通用的方法, 但是链接预测的准确性高。
2 基于随机游走的时间加权网络链接预测
2.1 问题定义
给定一个微博网络图G= (V, E, A) , 其中V为用户的集合, E为用户之间的关系额集合, A为节点的属性集合。如图1所示, 节点a, b和c表示用户, 边表示用户之间的关系, 节点的属性表示用户的发言。
当用户访问微博服务时, 我们希望预测潜在的用户链接, 从而将最可能建立链接的用户作为好友推荐给登录的用户。用户在微博中含有大量的发言, 这些发言内容可以反映用户的兴趣爱好, 对这些信息的充分利用可以提高推荐算法的性能。然而, 由于用户发言内容信息量大, 并且新近的发言更能体现出用户目前关注的内容。因此, 本文研究利用用户的新近发言来预测社会网络可能发生的链接。
2.2 时间加权网络结构图的生成
在用户组成的微博社会网络结构图中, 每个用户的发言都有一个时间戳, 而在链接预测中, 那些过早的时间戳包含的信息对链接预测的贡献不大。我们根据时间信息将用户新近的发言信息 (例如一周) 提取出来结果如图1所示。由于不同用户可能关注同一个话题, 即他们之间有共同的发言信息。
如果这两个用户之间已经有了链接, 我们将他们之间的边的权重赋值为他们共同关注的话题个数。如在图1中, 节点a和b都包含了属性Culture和Math, 节点b和c都包含了English, Culture和Chinese, 节点a和c都包含了Culture, Engineering和Architecture, 我们将这些相同属性作为边的属性便可以得到图2所示的结构。
2.3 基于随机游走的链接预测算法
在上述加权的社会网络图中G= (V, E) , V表示图G的节点的集合, E表示图G的边的集合, 其中节点的个数为n, 边的个数为m。
用M表示G的临界矩阵:
其中, mij为边 (i, j) 在图G中的权值。图G的转移概率矩阵为P:
在图G中, 以节点s为例, 假设对节点s进行好友推荐, 其随机游走模型是:以节点s作为出发点进行随机游走;在每一个随机游走中, 以概率ε返回到初始节点, 以概率1-ε走向下一节点;在走向下一节点的过程中, 在当前节点的临边中按照每条边的权重所占的比例随机选取一条边, 并走到目标节点;在到达某点后, 仍然按照该点的每条边的权重所占的比例随机选取一条边, 走向目标节点;重复上述过程。
在上述的随机游走中, 当游走的步数趋于无穷时, 随机游走停在每个节点的概率为一固定值, 即稳态概率。在一个有向网络中, 节点的稳态值与其父节点的稳态值成正比, 与其父节点的子节点个数成反比。假设初始节点为u, 节点v∈V的稳态值πu (v) 可通过如下公式计算:
其中δu (v) =1当且仅当u=v, δu (v) =0当且仅当u≠v。
随机游走的稳态值的计算可以通过线性代数的迭代方式进行, 也可以通过蒙特卡洛的统计方法进行。本文应用蒙特卡洛方法, 通过在网络上进行真实的随机游走模拟, 分析网络的稳态值。由于采用蒙特卡洛方法的随机游走并不能进行无穷步, 因此计算出的几点稳态值只是一个近似计算。
基于随机游走的蒙特卡洛方法的思想如下:以节点s作为出发点进行随机游走;在每一部游走时, 以概率λ停止游走, 以概率1-λ进行下一步游走;在进行下一随机游走中, 以概率ε返回到初始节点, 以概率1-ε走向下一节点, 假设当前节点为i, 在进行下一节点的选择时, 以概率走向节点j;继续随机游走直到算法停止。
当整个随机游走结束时, 用节点的访问频率来估计节点的稳态值。当初始点为u, 随机游走序列为RW时, 节点v的访问次数与整个序列的长度的比值为节点v的访问频率为, 即:
其中|RW|为该随机游走序列的长度, |v|为该随机游走中节点v的个数。
当计算出了每个节点的稳态值的近似值后, 我们按照该近似值的大小对节点进行排名, 近似值大的排名靠前, 近似值小的排名靠后。最后将排名靠前的节点作为初始节点的好友推荐给初始节点。
3 实验与分析
3.1 评价标准
TP (True Positives) 是指被模型预测为正的正样本;可以称作判断为真的正确率。
FP (False Positives) 是指被模型预测为正的负样本;可以称作误报率。
FN (False Negatives) 是指被模型预测为负的正样本;可以称作漏报率。
本实验所采用的评价标准是查准率 (precision) , 召回率 (recall) 和F-measure, 其定义分别为如下公式:
3.2 数据集
为了对本文提出的时间加权网络链接算法进行评价, 我们对新浪微博的数据进行采集。数据的采集过程中主要包括网络的结构关系, 即用户之间的关注与被关注关系, 和采集的用户发言。本实验共采集204 074个用户以及他们的相互关系, 同时收集了他们在2012年12月在微博上的发言信息。
3.3 实验结果
在本实验中, 我们令时间加权的随机游走方式预测网络链接的方法为TRWLP, 令没有时间加权的随机游走预测网络链接的方法为RWLP。我们首先通过实验验证时间属性在链接预测时的重要作用, 再通过对比实验验证TRWLP算法的有效性。
在新浪微博上收集的数据包含了该社会网络的网络结构, 同时也包含了每个节点的发言内容。为了对用户推荐潜在的好友, 我们认为距离当前节点的发言信息是有用的, 而早期的发言对好友推荐来说意义不是很大。我们将一个月的30天分成5个阶段, 每6天表示一个阶段。图3为TRWLP算法的性能与时间段的关系图。从图3可以看出, 距离当前时间越近的发言对推荐用户好友的准确性越好。
为了验证算法的有效性, 我们将TRWLP算法对RWLP算法进行比较, 分别对比了算法的Precision, Recall和F-measure。我们将链接预测结果的前k个节点 (k=10, k=100) 推荐给目标点, 分别观察推荐结果的Precision, Recall和F-measure, 实验结果见图4和图5所示。从图中我们可以看出, 本文提出的TRWLP方法在查准率, 召回率和F-measure三种评价标准上都高于RWLP, 因此其在链接预测的准确性上优于RWLP。
5 结语
微博作为一种新媒体, 无时无刻不影响着人们的生活。在微博中, 用户可以发布或浏览信息, 那些关注共同话题的人很可能成为潜在的好友。然而, 在好友推荐的过程中, 时间信息起着非常重要的作用, 人们更愿意结交那些当前和自己兴趣爱好相同的用户。本文设计了一种基于随机游走的时间加权社会网络链接预测算法。实验表明, 基于时间因素在好友推荐算法明显好于无时间因素的好友推荐算法。
参考文献
[1]Newman M.Clustering and Preferential Attachment in Growing Networks[J].Physical Review Letters E, 2001, 64 (2) :95-102.
[2]LüL, Zhou T.Link prediction in complex networks:A survey[J].Physica A:Statistical Mechanics and its Applications, 2011, 390 (6) :1150-1170.
[3]Barabasi A, Albert R.Emergence of Scaling in Random Networks[J].Science, 1999, 286:509-513.
[4]Chebotarev P, Shamis E.The matrix-forest theorem and measuring relations in small social groups[J].Automation and Remote Control, 1997, 58:1505.
[5]Fouss F, Pirotte A, Renders J, et al.Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation[J].IEEE Trans.Knowl.Data.Eng, 2007, 19:355-365.
[6]Lu L, Jin C, Zhou T.Similarity index based on local paths for link prediction of complex networks[J].Phys.Rev.E, 2009, 80:046122.
[7]Liu W, Lu L.Link prediction based on local random walk[J].EPL, 2010, 89:58007.
[8]Sales-Pardo M, Guimera R, Amaral L A N.Extracting the hierarchical organization of complex systems[C]//Proc.Natl.Acad.Sci.U.S.A, 2007, 104:15224.
[9]Clauset A, Moore C, Newman M E J.Hierarchical structure and the prediction of missing links in networks[J].Nature, 2008, 453:98.
[10]Friedman N, Getoor L, Koller D, et al.Learning Probabilistic relational models[C]//Proceedings of the 16th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2009.
[11]Heckerman D, Meek C, Koller D.Probabilistic Entity-Relationship Models, PRMs, and Plate Models[C]//Proceedings of the 21st International Conference on Machine Learning, Banff, Canada, 2012, 55.