链接分析与图挖掘

数据挖掘与商务智能DataMining&BusinessIntelligence西安电子科技大学　软件学院主讲人：黄健斌第七章链接分析与图挖掘内容提纲链接分析与权威资源发现“权威性”度量 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证度量标准(1)度数中心度(DegreeCentrality)节点的度(Degree)，即链接到它的边的数目，在社会网络文献中有时称作DegreeCentrality紧密度中心度(ClosenessCentrality)中介度中心度(BetweennessCentrality)度量标准(2)特征向量中心度(EigenvectorCentrality)假设每个节点i起始中心度为，再将中心度不断改变为其邻居节点中心度的和，即其中，是邻接矩阵中第i行第j列的元素。用矩阵的记号还可写为（x是元素为的向量）。这样，在重复t次之后的中心度x(t)为：度量标准(3)将x(0)写为由邻接矩阵特征向量构成的线性组合的形式：这时，会有：其中是A的特征值，是其中值最大的。则对所有因此，在时，，即向量中心度的极限与其邻接矩阵对应的主要特征向量成正比。即：度量标准(4)从上述的公式可以发现一个特性：中心度大的节点要不它有很多邻居，要不它有比较重要的邻居，或者两者兼有。入度为0的点其中心度为0，则级联导致中间所有起于入度为0的点的度也为0度量标准(5)Katz中心度(KatzCentrality)给每个节点（忽略其位置或邻居中心度）一个较小量的初始中心度，即：其中，都是正常数其矩阵表示为：其中，是向量(1,1,1…)，则，由于不关心中心度的绝对量值，只在乎哪个节点的中心度最高或最低，因此取值不重要，一般设定，则：度量标准(6)参数控制着式(1)中特征向量项和常数项比例。当时，式(1)中只存在常数项，所有点的中心度都一样为当把从0增大的时候，中心度也增加，渐渐地就会到一个发散点，这时式(2)中的发散，即：对应特征向量和特征值定义：,有：等价于邻接矩阵的特征值。当增加到（A的最大的特征值）时，行列式第一次跨过0。因此，如果我们想要中心度的表达式收敛，应该挑选一个度量标准(7)在计算时，由于矩阵求逆操作的时间复杂度在，通常采用式(3)进行迭代求解式(1)的扩展形式：可得当存在一个高中心度节点时，其所指向的其他节点也都得到了高中心度。但它们确实是吗？内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证1.基于链接关系分析的网页排序算法PageRank但是存在一个问题，如果网络中存在出度为0的节点，即，那么式(4)就无法确定大小。出度为0的节点对其他节点的中心度贡献为0，我们可以手工设定没有出度的节点，其，或其他非零值。PageRank（续）这时，有：其中，是向量(1,1,1…)，是元素为的对角阵转换后，，同前面一样，设有：这个中心度标准就称为PageRankPageRank（续）同前面一样，对应的取值应该小于最大特征值对应的倒数。同Katz中心度一样PageRank也可以做如下的扩展：PageRank（续）PageRank（续）内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证2.基于权威度和中心度的网页互排序算法HITSHITS:Hyperlink-InducedTopicSearch创建Focused子图计算Hubs和AuthoritiesHITS(续)问题描述：给定由网页之间超链接构成的网络和一个查询为这个查询找到最权威的网页查询类型：指定查询：“NetScape是否支持Java1.1的代码签名API？”广义主题查询：“查找与Java编程语言相关的信息”相似网页查询：“找到与java.sun.com相似的网页”HITS(续)(一)创建Focused子图(1)对于一个特定的字符串，用表示所有包含的网页的集合(2)需要寻找一个网页集合满足:相对较小、其中的相关网页要多、包含多数权威网页(3)利用基于文本的搜索引擎(AltaVista,Hotbot)查询，取其排名靠前的前t(t一般设置为200左右)个网页，将其记为根集，但是其中网页之间链接很少，“structureless”(4)对于该主题比较权威的网页，尽管可能不在根集中，但存在很大的可能性与根集中的网页之间存在链接，这时我们就扩展根集，得到基本集HITS(续)d一般取50左右HITS(续)处理中的边(链接)：Transverse:如果两个网页域名不同保留Intrinsic:如果域名相同，则主要起导航作用，对于提供与权威网页相关信息的关系不大删除域名：URL第一次字符串http://www.gamelan.com/http://java.sun.com/最终得到图HITS(续)(二)计算Hubs和Authorities在图中，用入度值的降序对网页节点进行排序问题：可能前面都很好的和主题相关，但是其他的却和主题相差很远，那么怎样来去掉那些高入度节点但和主题相关较差的网页？我们发现，与初始查询相关的权威页面不仅有比较大的入度，而且由于其都面对同一主题，那么在指向它们的页面集合中一定会有重叠Hub页面：与多个权威页面都有链接正是这些hub页面将权威页面统一到一个主题上，去除了无联系的高入度页面HITS(续)Hub页面和Authority页面之间存在一种互相增强关系：一个好的hub页面指向多个好的权威页面；一个好的权威页面被多个好的hub页面所指向HITS(续)对每一个页面p，给其一个非负的Authority权重，一个非负的Hub权重根据相互增强关系有：在数量上，网页p指向多个较大x值的页面，则它能够得到一个比较大的y值；如果p被多个较大y值的页面指向，则它能够得到比较大的x值I操作（更新x权重）：O操作（更新y权重）：HITS(续)HITS(续)HITS(续)c一般取5~10HITS(续)结果：HITS(续)针对相似网页查询的处理：如果一个网页p被多次引用，p附近最权威的网页潜在的充当了与p有关的广义主题 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 的角色改动：对于广义主题查询，在基于文本的搜索引擎中找到前t个包含搜索字符的页面对于相似网页查询，在基于文本的搜索引擎中找到前t个指向页面p的页面HITS(续)结果：内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证频繁子图模式挖掘的意义在各种图模式中，频繁子结构可以用来刻画图解的特征，区分不同的图组群，对图进行分类和聚类，构造图索引和更方便的在图数据库中进行相似性搜索。通过对比不同类中频繁图的支持度，发现HIV甄别数据集中活跃的化学结构；把频繁结构作为特征对化合物分类，利用频繁图挖掘技术研究蛋白质结构族；使用频繁图模式在图数据库中建立图索引和进行相似性搜索；……内容提纲链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法PageRank基于权威度和中心度的网页互排序算法HITS频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraph链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证3.频繁子树模式挖掘算法TreeMiner频繁子树相关概念：树的大小：给定一棵树记为T，树T中所有节点的数量总和称为树的大小，记为|T|根节点：根节点记为r，树中其他任何节点都是根节点r的子孙节点k阶子树：给定一棵树T，树S是树T的子树，树S的大小为k，则树S就是树T的k阶子树树的深度：给定一棵树记为T，根节点r，对于任何一个节点v，从根节点r到节点v经过的路径长度就是节点v的深度，这些节点深度中最大值，就是整个树的深度也称为树高。TreeMiner(续)节点关系：给定树，如果并且存在一条从x到y的路径，这时x就被称为是y的一个祖先，记为其中p是从x到y的路径的长度。如果，即x是直接祖先，这时x就是y的父节点，y是x的子节点。如果x,y有同一父节点，则x,y是兄弟节点。TreeMiner(续)有序树：给定一棵树，按照一种遍历方法记录树中节点时，各个节点的位置是具有一定顺序的，并且各个节点之间的顺序是不能任意改变的，则这样的树称为有序树，否则称为无序树。森林：森林是由很多棵不相交的树组成，这些若干棵树的集合就是森林。标号树：给定一棵树T(r)，标号集L，点集N，仅当存在一种映射，所有的节点，且，则树T为标号树有序标号树：一棵树既是有序树又是标号树则为有序标号树。一个带标签的有序树，记为T=(r,V,E,L)。其中，r表示根节点，v表示树中节点的集合，E表示所有边的集合，L表示所有节点标签的集合TreeMiner(续)最右路径及最右叶子节点：给定一棵树T，以前序遍历方法遍历树T，树T的最右路径就是从根节点r到最后一个被遍历的节点之间的路径。这个最后一个被遍历的节点就是最右叶子节点，根节点r到最右叶子节点之间的路径长度就是最右路径长度。TreeMiner(续)树的拓扑编码表示：采用深度优先遍历的方法，前序遍历树中所有节点，每个节点对应一个标签，用此方法获得一个字符串序列，这个序列就可以用来表示树的拓扑编码，当一个节点回溯到该节点的父节点时添加-1到字符串中。TreeMiner(续)三元组编码：有序树中每个节点采用三元组(tid,scope,high)编码。其中，，表示这个节点所在树的标号。点根据它在树T的深度优先遍历的位置进行编号。用T(x)表示根在x的子树，y表示x下最右叶子节点（即T(x)中编号最大的子孙）。这时，x点的scope给定为s(x)=[x,y]或[,]。high表示该节点在树中的高度。TreeMiner(续)支持度：用表示k阶子树S在树T中出现的次数，如果，则；如果，则，子树S在数据库D中的支持度则为，支持度一般以百分比的形式给出，即频繁子树：给定一个森林和一个最小支持度阈值minsup（），如果一个子树不小于最小阈值minsup时，这个子树被称为频繁子树完全子树：给定两棵树T=(V,E,L)和T1=(V1,E1,L1)，满足一下条件则为完全子树:(1)(2)(3)在T1中子树的节点集V1及边集E1在连接顺序上同在树T中的节点以及边的连接顺序保持一致(4)树T中的任意节点，如果节点v也在树T1的V1中，则节点v的所有子孙节点也应该在树T1的节点集V1中（5）如果树T是有序树，则T中和T1中也应该有相同的顺序。这时T1就是T的完全子树。TreeMiner(续)诱导子树：给定树和，我们说S是T的一个同构子树当且仅当存在一个映射，使得当时，。如果是满射，这时S和T是同构的。当且仅当S是T的一个同构子树且保持标签，即保留了父子关系，同时还有点的标签S就称为是的一个诱导子树。完全子树：被称为是的一个嵌入子树，当且仅当存在一个一对一映射满足：(1)仅当时(2)，即对嵌入子树来说，保留了祖先后代关系和标签完全子树是诱导子树的子集，而诱导子树是嵌入子树的子集TreeMiner(续)频繁子树如无显式说明，均指嵌入子树TreeMiner(续)两个k阶子树X,Y在同一等价类(EquivalenceClass)中，当且仅当它们有共同的前k-1个前缀。即，用X，Y表示两个数的字符编码，用函数p(X,i)返回第i个节点的前缀，则X，Y在同一等价类中当且仅当p(X,k-1)=p(Y,k-1)，也就是说，一个等价类中任意两个成员之间只在最后一个节点的位置上不同。TreeMiner(续)等价类则由前缀和元素列表表示TreeMiner(续)用P表示k-1阶前缀子树，表示它的等价类，如果(x,i)是类的一个元素，则记作，用记号表示向P中添加了(x,i)后形成的新的前缀树，也称作是P的一次扩展(Extension)。引理1：用P表示一个根为，最右叶子节点为的前缀子树，用R(P)表示从根到的最右路径。即，则当且仅当表明P的合法扩展只能通过将标签x绑定到P中从根到最右叶子节点的路径上的节点。TreeMiner(续)定理1(ClassExtension)：用k-1阶子树P表示编码为P的前缀类。(x,i)，(y,j)表示类中的任两个元素。用k阶子树表示P在添加元素(x,i)后的一次扩展。表示所有可能扩展的集合。定义两元素之间的操作，即如下：(1)i=j:(a)如果，将(y,j)和(y,)添加到，其中是点(x,i)在树上深度优先遍历的位置(b)如果，将(y,j+1)添加到(2)i>j:将(y,j)添加到(3)i