下载 - 西安电子科技大学软件学院(1)

《下载 - 西安电子科技大学软件学院(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据挖掘与商务智能DataMining&BusinessIntelligence西安电子科技大学　软件学院主讲人：黄健斌第七章链接分析与图挖掘内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证内容提纲链接分析与权威资源发现“权威性”度量

2、标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证度量标准(1)度数中心度(DegreeCentrality)节点的度(Degree)，即链接到它的边的数目，在社会网络文献中有时称作DegreeCentrality紧密度中心度(ClosenessCentrality)中介度中心度

3、(BetweennessCentrality)度量标准(2)特征向量中心度(EigenvectorCentrality)假设每个节点i起始中心度为，再将中心度不断改变为其邻居节点中心度的和，即其中，是邻接矩阵中第i行第j列的元素。用矩阵的记号还可写为（x是元素为的向量）。这样，在重复t次之后的中心度x(t)为：度量标准(3)将x(0)写为由邻接矩阵特征向量构成的线性组合的形式：这时，会有：其中是A的特征值，是其中值最大的。则对所有因此，在时，，即向量中心度的极限与其邻接矩阵对应的主要特征向量成正比。即：度量标准(4)从上

4、述的公式可以发现一个特性：中心度大的节点要不它有很多邻居，要不它有比较重要的邻居，或者两者兼有。入度为0的点其中心度为0，则级联导致中间所有起于入度为0的点的度也为0度量标准(5)Katz中心度(KatzCentrality)给每个节点（忽略其位置或邻居中心度）一个较小量的初始中心度，即：其中，都是正常数其矩阵表示为：其中，是向量(1,1,1…)，则，由于不关心中心度的绝对量值，只在乎哪个节点的中心度最高或最低，因此取值不重要，一般设定，则：度量标准(6)参数控制着式(1)中特征向量项和常数项比例。当时，式(1)中只存在

5、常数项，所有点的中心度都一样为当把从0增大的时候，中心度也增加，渐渐地就会到一个发散点，这时式(2)中的发散，即：对应特征向量和特征值定义：,有：等价于邻接矩阵的特征值。当增加到（A的最大的特征值）时，行列式第一次跨过0。因此，如果我们想要中心度的表达式收敛，应该挑选一个度量标准(7)在计算时，由于矩阵求逆操作的时间复杂度在，通常采用式(3)进行迭代求解式(1)的扩展形式：可得当存在一个高中心度节点时，其所指向的其他节点也都得到了高中心度。但它们确实是吗？内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的

6、网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证1.基于链接关系分析的网页排序算法PageRank但是存在一个问题，如果网络中存在出度为0的节点，即，那么式(4)就无法确定大小。出度为0的节点对其他节点的中心度贡献为0，我们可以手工设定没有出度的节点，其，或其他非零值。PageRank（续）这时，有

7、：其中，是向量(1,1,1…)，是元素为的对角阵转换后，，同前面一样，设有：这个中心度标准就称为PageRankPageRank（续）同前面一样，对应的取值应该小于最大特征值对应的倒数。同Katz中心度一样PageRank也可以做如下的扩展：PageRank（续）PageRank（续）内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图

8、模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证2.基于权威度和中心度的网页互排序算法HITSHITS:Hyperlink-InducedTopicSearch创建Focused子图计算Hubs和AuthoritiesHITS(续)问题描述：给定由网页之间超链接构成