1、数据挖掘与商务智能Data Mining&Business Intelligence西安电子科技大学软件学院主讲人：黄健斌第七章第七章 链接分析与图挖掘链接分析与图挖掘内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法
2、PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证度量标准(1)n度数中心度度数中心度(Degree Centrality)节点的度(Degree)，即链接到它的边的数目，在社会网络文献中有时称作Degree Centralityn紧密度中心度(Closeness Centrality)n中介度中心度(Betweenness Centrality)度量标准(2)n特征向量中心度特
3、征向量中心度(Eigenvector Centrality)假设每个节点 i 起始中心度为 ，再将中心度不断改变为其邻居节点中心度的和，即其中，是邻接矩阵中第 i 行第 j 列的元素。用矩阵的记号还可写为 （x 是元素为 的向量）。这样，在重复 t 次之后的中心度 x(t)为：xijjijixxAAijxxAxi)0()(xtxtA度量标准(3)将x(0)写为由邻接矩阵特征向量 构成的线性组合的形式：这时，会有：其中 是 A 的特征值，是其中值最大的。则对所有 因此，在 时，即向量中心度的极限与其邻接矩阵对应的主要特征向量成正比。即：viiiivcx)0()0()(xtxtAiiititiit
4、iiiiitvkkckvkcvctx11)(Akik11i11kkitvkctxt111)(xkx1A度量标准(4)从上述的公式可以发现一个特性：中心度大的节点要不它有很多邻居，要不它有比较重要的邻居，或者两者兼有。入度为0的点其中心度为0，则级 联导致中间所有起于入度为0的点 的度也为0 jjijixkxA11xkx1A度量标准(5)nKatz中心度中心度(Katz Centrality)给每个节点（忽略其位置或邻居中心度）一个较小量的初始中心度，即：其中，都是正常数 其矩阵表示为：其中，是向量(1,1,1)，则 ，由于不关心中心度的绝对量值，只在乎哪个节点的中心度最高或最低，因此 取值不重
5、要，一般设定 ，则：(1)jjijixxA,1Axx11A)(1Ix1(2)(11AIx度量标准(6)参数 控制着式(1)中特征向量项和常数项比例。当 时，式(1)中只存在常数项，所有点的中心度都一样为当把 从 0 增大的时候，中心度也增加，渐渐地就会 到一个发散点，这时式(2)中的 发散，即：对应特征向量和特征值定义：,有：等价于邻接矩阵的特征值。当 增加到 （A的最大的特征值）时，行列式第一次跨过0。因此，如果我们想要中心度的表达式收敛，应该挑选一个0)(1AI0)(det1IAvAvk0)(vIA k1k11k11度量标准(7)在计算时，由于矩阵求逆操作的时间复杂度在 ，通常采用式(3)
6、进行迭代求解式(1)的扩展形式：可得当存在一个高中心度节点时，其所指向的其他节点也都得到了高中心度。但它们确实是吗？)(3nO(3)1Axx ijjijixxA)(1AIx内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证1.基于链接关系分析的网页排序算法 PageRankn但是存在一个问题，如果网
7、络中存在出度为0的节点，即 ，那么式(4)就无法确定大小。n出度为0的节点对其他节点的中心度贡献为0，我们可以手工设定没有出度的节点，其 ，或其他非零值。(4)joutjjijikxxA0kouti1koutiPageRank（续）n这时，有：其中，是向量(1,1,1)，是元素为 的对角阵n转换后，同前面一样，设 有：这个中心度标准就称为 PageRank1DAxx1(4)joutjjijikxxA1D)1,(maxkoutiiiD1DAI)(11x11ADD1DAI)()(111xPageRank（续）n同前面一样，对应 的取值应该小于 最大特征值对应的倒数。n同Katz中心度一样PageR
8、ank也可以做如下的扩展：1DAI)(11x(2)(11AIxDA1ijoutjjijikxxA)(1ADDxPageRank（续）PageRank（续）内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证2.基于权威度和中心度的网页互排序算法 HITSnHITS:Hyperlink-Induced
9、Topic Search创建创建 Focused 子图子图计算计算 Hubs 和和 AuthoritiesHITS (续)n问题描述：给定由网页之间超链接构成的网络和一个查询为这个查询找到最权威的网页n查询类型：指定查询：“NetScape是否支持Java1.1的代码签名API？”广义主题查询：“查找与Java编程语言相关的信息”相似网页查询：“找到与相似的网页”HITS (续)n(一)创建 Focused 子图(1)对于一个特定的字符串 ，用 表示所有包含 的网 页的集合(2)需要寻找一个网页集合 满足:相对较小、其中的相关网页要多、包含多数权威网页相对较小、其中的相关网页要多、包含多数权威
10、网页(3)利用基于文本的搜索引擎(AltaVista,Hotbot)查询 ，取 其排名靠前的前 t(t一般设置为200左右)个网页，将其记 为根集 ，但是其中网页之间链接很少，“structureless”(4)对于该主题比较权威的网页，尽管可能不在根集中，但 存在很大的可能性与根集中的网页之间存在链接，这时我 们就扩展根集，得到基本集QSRSHITS (续)d一般取50左右HITS (续)n处理 中的边(链接)：Transverse:如果两个网页域名不同 保留保留Intrinsic:如果域名相同，则主要起导航作用，对于提供与权威网页相关信息的关系不大 删除删除域名：URL第一次字符串 htt
11、p:/ (续)n(二)计算Hubs 和Authorities在图 中，用入度值的降序对网页节点进行排序 问题：可能前面都很好的和主题相关，但是其他的却和主题相差很远，那么怎样来去掉那些高入度节点但和主题相关较差的网页？我们发现，与初始查询相关的权威页面不仅有比较大的入度，而且由于其都面对同一主题，那么在指向它们的页面集合中一定会有重叠Hub页面：与多个权威页面都有链接正是这些hub页面将权威页面统一到一个主题上，去除了无联系的高入度页面GHITS (续)nHub页面和Authority页面之间存在一种互相增强关系：一个好的hub页面指向多个好的权威页面；一个好的权威页面被多个好的hub页面所指
12、向HITS (续)n对每一个页面p，给其一个非负的Authority权重 ，一个非负的Hub权重n根据相互增强关系有：在数量上，网页 p 指向多个较大 x 值的页面，则它能够得到一个比较大的 y 值；如果 p 被多个较大 y 值的页面指向，则它能够得到比较大的 x 值nI I操作（更新x 权重）：O O操作（更新y y权重）：xpypEpqqqpyx),(:Eqpqqpxy),(:HITS (续)Epqqqpyx),(:Eqpqqpxy),(:HITS (续)0000000011001100Ayyyyxxxxdcbadcba0011001100000000 xxxxyyyydcbadcba00
13、00000011001100Epqqqpyx),(:YAXTXAAXTEqpqqpxy),(:XAYYAAYTHITS (续)n n n n c一般取510HITS (续)n结果：HITS (续)n针对相似网页查询的处理：如果一个网页 p 被多次引用，p 附近最权威的网页潜在的充当了与 p 有关的广义主题总结的角色n改动：对于广义主题查询，在基于文本的搜索引擎中找到前 t个包含搜索字符的页面对于相似网页查询，在基于文本的搜索引擎中找到前 t个指向页面 p 的页面HITS (续)n结果：内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和
14、中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证频繁子图模式挖掘的意义n在各种图模式中，频繁子结构可以用来刻画图解的特征，区分不同的图组群，对图进行分类和聚类，构造图索引和更方便的在图数据库中进行相似性搜索。n通过对比不同类中频繁图的支持度，发现HIV甄别数据集中活跃的化学结构；n把频繁结构作为特征对化合物分类，利用频繁图挖掘技术研究蛋白质结构族；n使用频繁图模式在图数据库中建立图索引和进行相似性搜索；n
15、内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证3.频繁子树模式挖掘算法TreeMiner频繁子树相关概念：n树的大小：给定一棵树记为T，树T中所有节点的数量总和称为树的大小，记为|T|n根节点：根节点记为r，树中其他任何节点都是根节点r 的子孙节点nk阶子树：给定一棵树T，树S 是树T 的子树，
16、树S 的大小为k，则树S 就是树T 的k 阶子树n树的深度：给定一棵树记为T，根节点r，对于任何一个节点v，从根节点r 到节点v 经过的路径长度就是节点v 的深度，这些节点深度中最大值，就是整个树的深度也称为树高。TreeMiner (续)n节点关系：给定树 ，如果 并且存在一条从x 到y 的路径，这时x就被称为是y 的一个祖先，记为 其中p 是从 x 到 y 的路径的长度。如果 ，即x 是直接祖先，这时 x 就是 y 的父节点，y 是 x 的子节点。如果x,y有同一父节点，则x,y是兄弟节点。yxpyx1),(EVT Vyx,TreeMiner (续)n有序树：给定一棵树，按照一种遍历方法记
17、录树中节点时，各个节点的位置是具有一定顺序的，并且各个节点之间的顺序是不能任意改变的，则这样的树称为有序树，否则称为无序树。n森林：森林是由很多棵不相交的树组成，这些若干棵树的集合就是森林。n标号树：给定一棵树T(r)，标号集L，点集N，仅当存在一种映射 ，所有的节点 ，且 ，则树T为标号树n有序标号树：一棵树既是有序树又是标号树则为有序标号树。一个带标签的有序树，记为T=(r,V,E,L)。其中，r表示根节点，v表示树中节点的集合，E表示所有边的集合，L表示所有节点标签的集合LNf:NvLlvf)(TreeMiner (续)n最右路径及最右叶子节点：给定一棵树T，以前序遍历方法遍历树T，树T
18、的最右路径就是从根节点r 到最后一个被遍历的节点之间的路径。这个最后一个被遍历的节点就是最右叶子节点，根节点r 到最右叶子节点之间的路径长度就是最右路径长度。TreeMiner (续)n树的拓扑编码表示：采用深度优先遍历的方法，前序遍历树中所有节点，每个节点对应一个标签，用此方法获得一个字符串序列，这个序列就可以用来表示树的拓扑编码，当一个节点回溯到该节点的父节点时添加-1到字符串中。TreeMiner (续)n三元组编码：有序树中每个节点采用三元组(tid,scope,high)编码。其中，表示这个节点所在树的标号。点 根据它在树T 的深度优先遍历的位置 进行编号。用T(x)表示根在x 的子
19、树，y 表示 x 下最右叶子节点（即T(x)中编号最大的子孙）。这时，x 点的scope给定为s(x)=x,y或 ,。high表示该节点在树中的高度。Dtid nxnyVxnxTreeMiner (续)n支持度：用 表示 k 阶子树S 在树 T 中出现的次数，如果 ，则 ；如果 ，则 ，子树S在数据库D中的支持度则为 ，支持度一般以百分比的形式给出，即n频繁子树：给定一个森林和一个最小支持度阈值 minsup（），如果一个子树不小于最小阈值 minsup时，这个子树被称为频繁子树n完全子树：给定两棵树T=(V,E,L)和T1=(V1,E1,L1)，满足一下条件则为完全子树:(1)(2)(3)在
20、T1中子树的节点集V1及边集E1在连接顺序上同在树T中的节点以及边的连接顺序保持一致(4)树T中的任意节点 ，如果节点v也在树T1的V1中，则节点v的所有子孙节点也应该在树T1的节点集V1中（5）如果树T是有序树，则T中和T1中也应该有相同的顺序。这时T1就是T的完全子树。)(ST0)(ST1)(SdT0)(ST0)(SdTDTTSdS)()(DS)(1supmin0VV 1EE 1VvTreeMiner (续)n诱导子树：给定树 和 ，我们说S是T的一个同构子树当且仅当存在一个映射 ，使得当 时，。如果 是满射，这时S和T是同构的。当且仅当S是T的一个同构子树且 保持标签，即 保留了父子关系
21、，同时还有点的标签 S就称为是 的一个诱导子树。n完全子树：被称为是 的一个嵌入子树，当且仅当存在一个一对一映射 满足：(1)仅当 时 (2)，即对嵌入子树来说，保留了祖先后代关系和标签完全子树是诱导子树的子集，而诱导子树是嵌入子树的子集),(EVSss),(EVTttVVts:Eyxt)(),(Eyxs),(Vxxlxls),()(),(EVTttVVts:),(EVSss),(EVTtt)()(yxpEyxs),(Vxxlxls),()(TreeMiner (续)频繁子树如无显式说明，均指嵌入子树频繁子树如无显式说明，均指嵌入子树TreeMiner (续)n两个k阶子树X,Y在同一等价类等
22、价类(Equivalence Class)中，当且仅当它们有共同的前k-1个前缀。即，用X，Y表示两个数的字符编码，用函数 p(X,i)返回第i个节点的前缀，则X，Y在同一等价类中当且仅当 p(X,k-1)=p(Y,k-1)，也就是说，一个等价类中任意两个成员之间只在最后一个节点的位置上不同。TreeMiner (续)等价类则由前缀和元素列表表示TreeMiner (续)n用P表示k-1阶前缀子树，表示它的等价类，如果(x,i)是类的一个元素，则记作 ，用记号 表示向P中添加了(x,i)后形成的新的前缀树，也称作是P的一次扩展扩展(Extension)。n引理引理1：用P表示一个根为 ，最右叶
23、子节点为 的前缀子树，用R(P)表示从根到 的最右路径。即 ，则 当且仅当 表明P的合法扩展 只能通过将标签x绑定到P中从根到最右叶子节点的路径上的节点。1PkPxiPixPixn0nrnr,:)(rihas scopennPRii),(Pix)(PRniPixTreeMiner (续)n定理定理1(Class Extension)：用k-1阶子树P表示编码为P的前缀类。(x,i)，(y,j)表示类中的任两个元素。用k阶子树 表示P在添加元素(x,i)后的一次扩展。表示 所有可能扩展的集合。定义两元素之间的 操作，即 如下：(1)i=j:(a)如果 ，将(y,j)和(y,)添加到 ，其中 是点
24、 (x,i)在树 上深度优先遍历的位置(b)如果 ，将(y,j+1)添加到 (2)ij:将(y,j)添加到 (3)ij:没有可能的新候选项 PixPixPix),(),(jyixPniPixniPixPPixPixTreeMiner (续)TreeMiner (续)nTREEMINER 采用DFS来搜索频繁子树，采用一个称为scope-list的树表现方式来实现支持度的快速计数。n用X表示树T的一个k阶子树，用 表示X的最后一个节点，用L(X)表示X的scope-list。Scope-list中的每个元素都是一个三元组(t,m,s)。其中，t表示子树X所在树的tid，m是X的长度为k-1的前缀
25、匹配标签，s是 的范围。n前缀匹配标签给出了T中匹配前缀的节点的位置。由于给定的前缀可能在树中出现多次，则X也就需要不仅标签而且需要范围。xkxkTreeMiner (续)TreeMiner (续)TreeMiner (续)nP中任意两个子树的scope-list 连接(join)是基于它们scope-list的区间代数n用 表示节点x,y的范围。严格小于 ，记作 ，当且仅当 没有重叠 包含 ，记作 ，当且仅当 真子集n仅当i=j时，候选项(y,j+1)被加入到 ，即意味着在候选子树中y 是 x 的孩子节点。要检查该子树是否出现在tid为t的输入树T中，需搜索是否存在元组 使得：(1)(2)(
26、3)如果都满足，则扩展旧前缀 P 的匹配标签 ，获得新前缀 的匹配标签 ，将元组 加入到 中(y,j+1)的scope-list中,ulsxxx,ulsyyyssyxsxsyluyxsxsyssyxllyxuuyxPix)(),(yLsmtyyy)(),(xLsmtxxxtttyxmmmxyssxymyPix)(lmxy),(slmtyxyyPixTreeMiner (续)n候选项(y,j)表示y是x的兄弟，为了检查(y,j)是否出现在tid为t的树T中，需检查是否存在元组 使得：(1)(2)(3)如果这些条件满足，将元组 加入到 中(y,j)的scope-list中)(),(xLsmtxxx
27、)(),(yLsmtyyytttxymmmxyssyx),(slmtyxyyPix内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证频繁子图模式挖掘算法频繁子图挖掘的基本概念n图g的顶点集合用V(g)表示，边集合用E(g)表示n标号函数 L 将顶点或边映射到标号n图g是另一个图 的子图，如果存在从图
28、 g 到图 的子图同构。n给定一个标记的图数据集 ,图 g 的支持度support(g)（或频度 frequency(g)）定义为 g 作为子图在D中出现的百分比（或次数）n频繁图是支持度不小于最小支持度阈值的min_sup的图gg,21GGGDn频繁子图模式挖掘算法n频繁子图挖掘的基本方法有两种：基于Apriori方法和模式增长方法。n在基于Apriori方法的频繁子图挖掘中，对频繁图的搜索开始于小“规模”的图，按照自底向上的方式产生具有附加顶点，边或路径的候选图。n在基于模式增长方法的频繁子图挖掘中，能够采用宽度优先搜索和深度优先搜索，对每个发现的图g，递归地进行扩展，知道发现所有嵌入g的
29、频繁图为止。一旦没有频繁产生，递归停止。基于Apriori算法的频繁子结构挖掘框架 4.FSG算法:Frequent Subgraph DiscoverynFSG算法采用基于边的候选策略，在每一次调用Apriori-Graph时通过增加一条边来扩大子结构的规模。两个大小为k 的模式合并，当且仅当它们共享相同的具有看k-1条边的子图，该子图称作核。这里，图的规模取图中边的个数。新形成的候选包括核和来自大小为k 的模式中的两条附加边。基于Pattern Growth的频繁子结构挖掘框架基于Pattern Growth的频繁子结构挖掘框架nPatternGrowthGraph 简单但是效率低。它的瓶
30、颈是扩展图的低效率。同样的图可能重复发现多次。n例如，可能存在n 个不同的n-1条边的图，可以扩展成相同的n 条边的图。相同的重复发现导致计算的低效率。称二度发现的图为复制图（duplicate graph）。n尽管PatternGrowthGraph 的第1行删除复制图，但是复制图的产生和检测可能增加工作量。为了减少复制图的产生，每个频繁图应该尽可能适当地扩展。典型的就是gSpan算法5.gSpan算法(基于图的子结构模式挖掘算法)n为了遍历图，gSpan算法采用深度优先搜索。初始，随机选择一个起始顶点，并且对图中访问过的顶点做标记。被访问过的顶点集合反复扩展，直到建立一个完全的深度优先搜索
31、(DFS)树。（图中加粗的边）n在构造DFS树时，顶点的访问顺序形成了一个线性序。使用下标来记录这一次序，其中ij意味着在进行深度优先搜索的时候 在 之前被访问。用DFS树做下标的图G记作 T称为G的一个DFS下标。vivjGTgSpan（续）n给定一棵DFS树T，称T 的起始节点 为根。最后访问的节点 称作最右节点。从 到 的直接路径称作最右路径v0vnv0vngSpan（续）n给定图G 和G 的DFS树T，一条新边e 可以添加到最右节点和最右路径上另一个节点之间（后向扩展）；或者可以引进一个新的节点并且连接到最右路径上的节点（前向扩展）。由于这两种扩展都发生在最右路径上，因此称为最右扩展。
32、（黑点为最右路径）gSpan（续）n由于同一个图可能有许多DFS下标，我们选择其中一个作为基本下标（base subscripting），并且只进行DFS下标的最右扩展。否则，最右扩展不能减少复制图的产生。n我们把每个加下标的图转换为边序列，称作DFS编码，以便建立这些序列之间的序，目的是选择产生最小序列的下标作为基本下标。在转换过程中有两种类型的序:（1）边序，将下标图中的边映射到一个序列；（2）序列序，它建立边序列（即图）之间的序。gSpan（续）n图中边可表示为(i,j)。如果ij，则为前向边；否则为后向边。n边序(1)定义前向边发现次序 (0,1)(1,2)(1,3)(2)把后向边添加
33、到该序 给定节点v，它的所有后向边应该正好在它的前向边之前出现。如果v 没有前向边，把它的后向边放在该前向边之后，其中v 是第二个节点。在相同节点的后向边之中，强加一个序。假设节点 有两个后向边(i,)和(i,)。如果 ,则边(i,)将出现在(i,)之前。(0,1)(1,2)(2,0)(1,3)vij1j2j1j2j1j2gSpan（续）n基于边序，如果用5元组(i,j,)表示边，其中 和 分别是 和 的标记，而 是连接它们的边的标记,则lilji),(ljliljvivjlji),(gSpan（续）n序列序：边序列之间的序 一个图可能有几个DFS编码，我们想在这些编码之间建立序列并选择一个编
34、码来代表图。此时通过标记信息来进行排序。令边序关系 拥有第一优先级，节点的标记 拥有第二优先级，边标记 拥有第三优先级，节点标记 拥有第四优先级，来决定两条边的次序。基于上规则的序称作DFS词典序(DFS Lexicographic Order)。根据DFS词典序，对于前面的DFS编码，有 Tliljlji),(210gSpan（续）n基于DFS词典序，给定图G的最小DFS编码记作dfs(G)，是所有编码中的最小者，如 。产生最小DFS编码的下标称为基本下标。n同时，还有：给定两个图G和 ，G和 同构当且仅当dfs(G)=dfs()。基于这个性质，为了挖掘频繁子图，只需要对最小DFS编码执行最
35、右扩展，因为这种扩展将确保挖掘结果的完全性。G0GGgSpan（续）内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证6.闭合频繁子图模式挖掘算法CloseGraphnCloseGraph:Closed Graph pattern mining 在gSpan的基础上，利用等效出现等效出现(equiv
36、alent occurrence)和提前终止提前终止(Early Termination)两个概念，帮助CloseGraph用较小的额外代价对搜索空间进行大量剪枝。n给定一个标号图(边和节点都有标号),将图g 的点集记为V(g)，边集记为E(g)；能够将一个节点或一条边映射到一个标号的标号函数l；CloseGraph（续）n子图同构(subgraph isomorphism)子图同构是一个单射函数 f：，使得：(1)，(2)，且 其中，l 和 分别是g和 的标号函数n图g 是另一个图 的子图，如果存在一个从g 到 的子图同构。n如果图g 是图 的一个子图，则 是g 的一个超图，记作 （真超图，
37、如果 ）)()(gVgV)(gVu)()(uflul)(),(gEvu)()(),(gEvfuf)(),(),(vfuflvullgggggggggCloseGraph（续）nFrequent graph pattern(频繁图模式)的集合,FS,包含所有支持度不小于最小支持度阈值min_sup的图nClosed frequent graph pattern(闭频繁图模式)的集合,CS,定义如下：即CS不包含那些与其真超图具有相同支持度的图nClosed frequent graph mining 问题就是给定了最小支持度阈值，在图数据库D中寻找CS的完全集合)()(,|gsupportgsu
38、pportandggsuch thatFSgandFSggCSCloseGraph（续）n图g 通过加入一条新边e 进行扩展，将扩展后的新图记为 。如果e 引入了新的节点，将新图记为 ，否则，记为n用 表示g 在 中可能的同构子图的数目nOccurrence(出现)：给定图g 和图数据集 ，则g 在D 中的Occurrence是g 在D 中每个图中同构子图数目的总和，即 ，记作I(g,D)egxegxfegxb),(ggg,21GGGDnniiGg1),(2),(1gg1),(2gg0),(3gg3),(),(1niiGgDgICloseGraph（续）n假设 ，f 是从g 到G 的子图同构函
39、数，是从 到G 的子图同构函数，如果 ，是从g 到 的子图同构函数，则称 f 是可扩展的(extendable)，是 f 的一个扩展子图同构(extended subgraph isomorphism)。将可扩展 f 的数目记为nExtended Occurrence(扩展出现)给定 ，D中 的扩展出现是D中每个图中g的可扩展子图同构数目的总和。即 ，记作eggxfgg)()(,vfvfvf),(Gggeggx,21GGGDngniiGgg1),(),(DggLCloseGraph（续）nEquivalent Occurrence(等效出现)给定 ，如果 ，我们说g 和 等效出现，意味着不论g
40、 出现在哪，也会出现。n假设存在图 ，如果 且 ，能否推断 不是闭合的？如果可以，则只需扩展 而不是g，将其称为Early Termination(提前终止)，它终止搜索除 外g 的所有超图。n由于 ，则 。当其相等时，则无论g 出现在哪个 中，也在同一位置出现，即边e 也同g 一起出现。这样，g 的一些没有边e 的超图 将不是闭合的，因为eggx),(),(DggLDgIggg gg gg g gg),(),(GggGgii),(),(DggLDgIGigg)()(egsupportgsupportxCloseGraph（续）对(1)，对(2),则(2)中两个X 节点之间的边a 始终伴随图(
41、1)出现，因此不用计算可知，图(3)的支持度和图(4)的支持度是相等的，因此在模式增长时，直接从图(2)开始增长。3012),(1DgI3012),(21DggLCloseGraph（续）内容提纲n链接分析与权威资源发现“权威性”度量标准基于链接关系分析的网页排序算法 PageRank基于权威度和中心度的网页互排序算法 HITSn频繁子图模式挖掘频繁子树模式挖掘算法TreeMiner频繁子图模式挖掘算法FSG和gSpan闭合频繁子图模式挖掘算法CloseGraphn链接分析与图模式挖掘商务应用案例PageRank算法的简单实现与验证PageRank算法的简单实现与验证n结合前面对于PageRa
42、nk算法的详细过程的描述，现给出基本PageRank算法的伪代码：n其中，S 是各网页初始的PageRank值；A 相当于前面的 ；为用户期望的精度n很明显，在伪代码中，最终 PageRank 的值是通过多次迭代计算，在邻近两次 PageRank 值的差别小于要求精度时终止而获得的。而迭代的次数则由初始值S，精度 共同决定的。DA1试验(续)n实验目的：掌握PageRank算法的基本原理，分析影响算法性能的因素。n实验要求：根据伪代码，实现简单的PageRank算法，并验证结果分析影响迭代次数的两个因素S和 ，并测试n实验步骤：编程实现简单的PageRank算法，采用例子中的数据作为输入，验证输出结果改变S和 ，查看结果输出试验(续)n实验结果(1)：S=(0.715，0.714，0.724，0.718，0.708，0.723，0.726)=0.01试验(续)n实验结果(2):S=(0.715，0.714，0.724，0.718，0.708，0.723，0.726)=0.005试验(续)n实验结果(3):S=(1，1，1，1，1，1，1)=0.005
