基于图论的频繁模式挖掘

计算机研究与发展 ISSN 100021239/ CN 1121777/ TP Journal of Computer Research and Development 42 (2) : 230～235 , 2005 　收稿日期 :2003 - 07 - 08 ;修回日期 :2004 - 10 - 29 　基金项目 :国家自然科学基金项目 (69933010 ,60303008) ;国家“八六三”高技术研究发展 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 基金项目 (2002AA4Z3430) 　 基于图论的频繁模式挖掘 汪 　卫 　周皓峰 　袁晴晴 　楼宇波 　施伯乐 (复旦大学计算机与信息技术系 　上海 　200433) (weiwang1 @fudan1edu1cn) Mining Frequent Patterns Based on Graph Theory Wang Wei , Zhou Haofeng , Yuan Qingqing , Lou Yubo , and Sui Baile ( Depart ment of Com puting & Inf orm ation Technology , Fudan U niversity , S hanghai 200433) Abstract 　Mining the frequent pattern from data set is one of the key success stories of data mining re2 search1 Currently , most of the efforts are focused on the independent data such as the items in the market2 ing basket1 However , the objects in the real world often have close relationship with each other1 How to gain the frequent pattern from these relations is the objective of this paper1 Graphs are used to model the re2 lations , and a simple type is selected for analysis1 Combining the graph2theory and algorithms to generate f requent patterns , two new algorithms are proposed1 The first algorithm , named AM GM , is based on the Aproiri idea and makes use of matrix1 For the second algorithm , a new structure SFP2t ree and an algo2 rithm , which can mine these simple graphs more efficiently , have been proposed1 The performance of the algorithms is evaluated by experiments with synthetic datasets1 The empirical results show that they both can do the job well , while SFP performs better than AM GM1 Such algorithms are also applied in mining of the authoritative pages and communities on Web , which is useful for Web mining1 At the end of the paper , the potential improvement is mentioned1 Key words 　SFP tree ; connected frequent graph ; data mining 摘 　要 　对图数据频繁模式的挖掘是近年的研究热点1 选择了惟一标号图进行分析 ,结合图论和频集 生成的算法 ,提出了基于 Aproiri 思想、运用矩阵乘法的 AM GM 算法和基于 SFP 树的 SFP 算法1 它们可 有效地挖掘简单图中连通频繁子图1 实验表明 ,这两个算法是十分有效的 ,其中 SFP 算法的性能优于 AM GM 1 该算法还被运用于发现 Web 上的权威页面和社团 ,具有良好的效果1 关键词 　SFP 树 ;频繁连通图 ;数据挖掘 中图法分类号 　TP301 1 　引 　　言 经过近 10 年的发展 ,关联规则的研究逐渐拓展 到 Web 挖掘、生物信息学、购物篮分析等众多实际 应用领域1 在这些应用包含大量复杂类型的数据 , 如在化学数据中由于原子与原子之间存在化学键 ,其数据构成一个图1 Web 网站的结构也是一种图的结构等1 如何对图结构数据进行关联规则分析是一项很有意义的工作1本文从标号图的连通频繁子图的分析入手 ,提出对包含结构信息的数据进行初步分析的方法 ,以 求将原先对单个项的频繁模式生成工作扩展到项对 的领域上1 本文在第 2 节介绍相关工作 ;在第 3 节引入标 号图等基本概念 ,在此基础上提出两种算法 :基于 Aproiri 思想、利用矩阵乘法的 AM GM 算法和基于 FP2Growth 算法的 SFP 算法 ;在第 4 节中 ,将给出 这两种算法的思想与实现 ,然后通过一系列实验对 比说明这两种算法的特性 ;在第 6 节 ,这些算法将被 运用于发现 Web 权威资源发现 ;最后给出算法的一 些扩展方向1 2 　相关工作 在频繁模式挖掘方面 Aproiri [1 ]算法是最著名 的基于广度优先思想的算法 ,另一个是 Mannila 等 人提出的 LevelWise 和 Guess & Correct 算法[2 ] ,随 后 Park 等人利用 Hash 技术提出了 DHP[3 ]算法 ,而 Brin 等人提出的 DIC[4 ]算法则充分利用了动态技术 的技巧1 这些工作都是为了减少在频繁项集生成过 程中候选项集产生的个数1 与广度优先相对应的是 深度优先算法 ,它以 Agarwal 等人的 DepthFirst [5 ]和 Tree2Project [6 ]算法为代表1 这类算法特点是适合于 生成长模式1 2000 年裴健等人提出了不产生候选项 集的 FP2Growth 算法[7 ] ,简化了频繁项集的生成工 作 ,之后 ,又有不少工作对该算法进行了改进 ,例如 H2Mine[8 ]等 ,以求逐步提高效率1 在处理的数据对象类型方面 ,算法从最初的对 购物篮数据的处理逐步演化到具有结构特性的序列 数据的处理[9 ] ,Web 访问日志的处理[10 ]等1 以及化 学物质结构、生物 pathway 等图类型数据1 本文针对在 Web 数据管理中广泛应用的惟一 标号图提出了频繁子图的挖掘算法1 目前已有 A GM [11 ]和 FSG[12 ]两个子图的挖掘算法1 这 2 个算 法都利用邻接矩阵分别对图的顶点和边进行逐层构 造 ,以最终获取频繁的子图1 所不同的是 A GM 是求 出了导出 (induced) 子图 ,图不一定连通 ,而 FSG则 求出了连通的频繁子图1 本文提出了两种频繁子图挖掘算法 :第 1 个是 基于 Aproiri 思想和处理这类方法常用的邻接矩阵 的 AM GM 算法 ;第 2 个是基于 FP2Growth 思想的 SFP 算法 ,它没有使用邻接矩阵1 并以惟一标号图 描述 Web 资源 ,研究了 Web 资源中 d 的权威页面 (对应于图中的频繁顶点) 和权威社团 (表征了权威 页面之间的紧密关系)1 3 　基本概念 在详细介绍算法之前 ,首先给出有关的基本概 念和定义1 定义 11 无向简单图1 设 V = { v1 , v2 , ⋯, v n}是 一个非空集合 , E = { e| e =〈 v i , v j〉, v i , v j ∈V } ,其 中〈 v i , v j〉为无序对 ,并且 Πei , ej ∈E , ei ≠ej ,称 ( V , E) 为无向简单图 ,简称图 ,记为 G ( V , E) , V 中的 元素为顶点 , V 为顶点集 ; E 为边集1 若结点上的 标号互不相同 ,则为惟一标号图1 由于图中所有的顶点被惟一地标号 ,因此图中 所有的边也由无序标号对〈 l i , l j〉惟一标定 ,记该标 号边为 l il j1 下文讨论的图都是惟一标号图 ,用标号 图简称1 定义 21 图数据集合1 图库 GD = { G1 , G2 , ⋯, GN} , 其中 , Gi 为标号图 , 称 N 为图库的大小 (size) ,所有标号的全体构成库标号集 L D1 定义 31 子图1 图 G′= ( V′, E′)为图 G = ( V , E) 的子图 ,当且仅当 V′Α V 且 Πv i , v j ∈V′,〈 v i , v j〉∈ E ]〈 v i , v j〉∈E′,记做 G′Α G ,或称 G 包含 G′1 定义 41 支持度1 给定图库 GD ,图 G 的支持度 为 GD 中包含图 G 的图的数目1 定义 51 频繁 (子) 图1 给定图库 GD ,图 G 为频 繁图 ,当且仅当 s ( G) ≥m i nsup1 m i nsup 为指定的 最小支持度 ,称为阈值1 定义 61 连通图1 设 u 和 v 是图 G 的两个不同 的顶点 ,若 u 和 v 之间存在一条路 ,则称顶点 u 和 v 是连通的1 若图 G 中任何两个不同顶点之间存在一 条路 ,则称 G 为连通图 ,否则称 G 为不连通图1 本文的目标是在给定标号图库中 ,找出该图库 中所有的频繁连通子图1 4 　生成频繁连通图 假设图数据以以下的格式存储 ,如表 1 所示 : Table 1 　A Sample of Graph 表 1 　图的例子 GID EID … … 23 AB ,BD ,〈B〉⋯ … … 表 1 中 , GID 代表标号图的 ID 号 , EID 是图中 边的列表1 图中每条边都以 l il j 形式存储 ,每条边的 两个顶点以字母序排序1 132汪 　卫等 :基于图论的频繁模式挖掘 411 　AMGM 算法 AM GM 算法是基于 Aproiri 的 ,它采用逐层构 造的方法 :先构造只含有一条边的频繁子图 ;然后以 此为基础构造含两条边的候选连通子图 ,通过扫描 数据库找到含有两条边的频繁连通图集1 以此类 推 ,从含有 k 条边 ( k2阶) 的频繁连通图找到 k + 1 2 阶的候选连通图集 ,根据最小支持度 ,找到 k + 1 阶 的频繁连通图集1 AM GM 算法采用邻接矩阵存储图数据 ,在矩阵 中行坐标为边 ,列坐标为图1 由于点集的标号有限 , 所以边的数目也是有限的 ,而且该数目不大于 C2n1 AM GM 算法的描述如下 : 算法 11 A proiriMatrixGraphMining( GD , minsup)1 输入 :图库 GD ,最小支持度 m i nsup1 输出 :频繁连通图集 F1 {扫描 GD ,统计 GD 所有点集 V 和边集 E , E 为 12阶候选集合 C1 F0 = { v | v ∈V , s ( v) ≥m i nsup} 计算 C1 中各边的 support ,生成 12阶频繁连通 图集 F1 C2 = gent w ocandi date ( F1 ) / 3 生成 22阶候选 连通图集 3 / for ( k = 2 ; ; k + + ) 　{计算 Ck 中各子图的支持度 　 Fk = { g| g ∈Ck , s ( g) ≥m i nsup} 　 if ( Fk = §) 算法结束 　 Ck + 1 = gencandi date ( Fk) 　 if ( Ck + 1 = §) 算法结束} } 该算法首先扫描数据库 ,并将符合支持度的点 作为频繁图输出1 再利用符合支持度的边的信息构 造矩阵 A ( A 中行向量为边 , 列向量为图库中的 图)1然后生成含有两条边的候选连通图 ,并计算其 支持度 ,将频繁的连通图输出1 然后生成下一轮的 候选连通图1 为了计算 Ci 中每个候选子图的支持度 , Ci 也 用矩阵表示 ,行向量为候选图边 ,列向量为边的集 合1通过计算 B i = Ci ×A 可以得到频繁图同图库中 的图包含关系 ,通过将 B i 同一个只有一列的且元素 全为 1 的矩阵相乘可以得到每个候选图的支持度1 算法中关键的一步是候选图集的生成1 与 Aproiri 算法类似 ,我们首先耀确定那些 k2阶频繁图 可以合并生成 k + 1 2阶候选图1 Gencandi date 过程 的描述如下所示1 Gencandi date ( Fk) { C′k 为 Fk 对应的矩阵 Dk = C′k ×( C′k ) T / 3 Dk 中置 1 的位 d ij代表了第 i 个图可以与 第 j 个图进行合并构成一个新的 k + 12阶的图 for ( i = 1 , k = 0 ; i ≤s′; i + + ) 　for ( j = i + 1 ; j ≤s′; j + + ) 　{ if ( d ij ! = 0) 　　C′k 的第 i 行与第 j 行进行“按位与”运算后 加入矩阵 Ck + 1} 　　删除 Ck + 1中的重复图 　　返回 ( Ck + 1) } 由于算法通过有公共 k - 1 条边的 k2阶图生成 k + 12阶图 ,所以除了从 12阶频繁集生成 22阶候选 集这一步外 ,均能保证了图的连通性1 由于算法中 组成图的两个单边的图有公共顶点 ,因此所得的图 均连通1 412 　基于 FP2Growth 思想的 SFP 算法 与 Aproiri 类似 ,在 AM GM 算法中候选图集的 生成和支持度计算仍是瓶颈1 本文提出了基于 FP2 Growth 的 SFP 算法1 SFP 算法的工作分为 2 步 :构建 SFP 树和从 SFP 树中获取频繁连通图1 SFP 树是一棵包含结构信息的 FP2树1 在树的 每个结点上 ,不仅记录下该结点所代表的标号边及 其支持度 ,还记录该结点与该结点所在的树分支中 其他结点的连接信息1 与 FP2树一样 ,算法维持用于 索引树中标号头表1 该表以支持度从大到小排序1 另外 ,建树时还临时保留于生成只包含一个点的频 繁图集的标号顶点表1 构建 SFP 树的算法如下所示1 算法 21 FP 树的构建1 输入 :图库 GD ,最小支持度 m i nsup1 输出 :一棵 FP 树1 方法 : const ructS FPt ree ( GD , m i nsup) { FV 为记录 GD 中各顶点支持度的列表 FE 为记录 GD 中各边支持度的列表 将支持度初始化为 0 对 GD 中的每个图 g {得到 g 的顶点集 V g 和边集 Eg 所有的 v ∈V g ,修改 FV 中的对应项 所有的 e ∈Eg ,修改 FE 中的对应项} for 所有 v ∈FV , do if ( v1 support ≥m i nsup) 输出 ( v , v1 support) 将 FE 中的边按支持度从大到小排序 删除 FE 中不满足支持度的边 232 计算机研究与发展 　2005 , 42 (2) / 3 FE 构成 FP 树的头表 3 / 初始化 FP 树 T ,建立根结点 ,并标志为“空” for all g ∈GD{ 　按照 FE 中的顺序 ,对 g 中的频繁边进行排序 　insert ( [ e| E ] , T) 　return ( T) } } insert ( [ e| E ] , T) {if ( T 有一个子女结点 N 并且 N 1 edgei d = e1 edgei d) 　N 1 count + + else{ 创建新的结点 N ,并且 N 1 edgei d = e1 edgei d , N 1 count = 1 , N 1 parent = T 将 N 链接到头表中 将 N 与它所有有关的祖先结点建立双向链接 if ( E ≠§) insert ( E , N ) 　return ( T) } } 该算法扫描 2 次图数据集1 第 1 次扫描建立用 于索引的头表1 头表中记录边的有关信息 ,如边的 标号、支持度 ,并对图中的顶点利用标号顶点表计 数1第 1 遍扫描完成后 ,利用支持度阈值进行过滤 , 并将已符合支持度的点作为频繁图输出1 在第 2 次扫描中将剔除不符合支持度的边和孤 立点 ,将余下的边按其在头表中的支持度从大到小 按照路径加入到 SFP 树中1 加入结点时 ,首先判定 该结点在特定分支上是否存在1 如存在 ,则只增加 支持度 ;否则 ,建立新的结点 ,并与其相连接祖先结 点进行双向连接1 下面将利用 SFP 树构建连通频 繁图1 算法 31 挖掘频繁连通图集1 输入 :SFP 树 T ,最小支持度 m i nsup1 输出 :频繁连通图集1 方法 :递归调用 S FPM i ni ng 过程 ,初始调用为 S FPM i ni ng ( T ,NULL) S FPM i ni ng ( T ree ,α) {对于 T ree 的头表中的每一项 ai , do 　{ if ( i < n - 1) then return 　β = union (α, ai ) , 并 且 β1 support = ai1 support 　if β是连通图 , then 输出 (β,β1 support) 　生成β的条件数据库 Dβ 　T reeβ= const ructCS FP( Dβ) 　If ( Treeβ≠§) then S FPMining ( Treeβ,β) } } 算法利用 SFP 树的头表自下而上地依次从 SFP 树中抽取连通频繁图1 对于每个头表中的标号 边 ai ,将其与生成目前的 SFP 树的前缀模式α合 并1如果 ai 和α合成后是连通的 ,则作为结果输出1 然后 ,对 ai 和α构成的新的前缀模式β,在当前的 SFP树上 ,生成β的条件图库 ,并调用 constructCS FP 算法生成β条件 SFP 树 ,以递归进行挖掘 ,直至不再 生成新的 SFP 树1 constructCS FP算法与 constructS FP 基本类似 ,惟一区别在于它不必考虑顶点频繁的问 题 ,只要考虑边的情况1 这个算法的核心包括 2 部分 :β的生成和连通 性的判定和β条件图库的生成1 β本身的生成和连通性的判定利用顶点的标号 完成1 判定方法如下所示1 算法 41β的生成和连通性判定1 假定α=γ1 ∪γ2 ∪⋯∪γn ,这里 i (1 ≤i ≤n) 是 连通子图 , Πγi ,γj (1 ≤i , j ≤n) 不连通1 Pi ( i = 1 , ⋯ n) 为组成γi 中所有边的点的集合 ,并且 P = ∪Pi1 显然 , ΠPi , Pj ( i ≠j) Pi ∩Pj = §1 假定 ai =〈 v , w〉, union (α, ai) {for all Pi , Pj in P { if v ∈Pi , w ∈Pj{β= (α- γi - γj ) ∪(γi ∪γj ∪{ ai} ) } if v ∈Pi , w | Pj{β= (α- γi) ∪(γi ∪{ ai} ) } if v | Pi , w ∈Pj{β= (α- γj) ∪(γj ∪{ ai} ) } if v | Pi , w | Pj{β=α∪{ ai} } } } 例 11 给定 a1 =〈1 ,3〉, a2 =〈2 ,7〉, a3 =〈7 ,8〉, 以及α= {〈1 , 2〉,〈2 , 6〉,〈3 , 4〉,〈4 , 5〉〈3 , 5〉} = {〈1 ,2〉,〈2 ,6〉} ∩{〈3 ,4〉,〈4 ,5〉〈3 ,5〉} 1 这里 ,前缀 模式α由两个连通子图构成 ,这两个部分互不相连1 我们可以根据算法 3 计算以下 3 个集合 : β1 = union (α, a1) = {〈1 , 2〉,〈2 , 6〉,〈1 , 3〉,〈3 , 4〉,〈4 ,5〉,〈3 ,5〉}1 这个计算根据的是第 1 条规则 , 显然它是连通的1 β2 = union (α, a2) = {〈1 , 2〉,〈2 , 6〉,〈2 , 7〉,〈3 , 4〉,〈4 , 5〉,〈3 , 5〉} = {〈1 , 2〉,〈2 , 6〉,〈2 , 7〉} ∩{〈3 , 4〉,〈4 ,5〉,〈3 , 5〉} ,根据规则 2 ,形成的是两个连通 分量1 β3 = union (α, a3) = {〈1 , 2〉,〈2 , 6〉,〈3 , 4〉,〈4 , 5〉,〈3 , 5〉,〈7 , 8〉} = {〈1 , 2〉,〈2 , 6〉} ∩{〈3 , 4〉,〈4 , 5〉,〈3 ,5〉} ∩{〈7 ,8〉} ,根据第 3 条规则 ,形成 3 个连 通分量1 另外 ,当α有 n 个互不连通的连通子图时 ,要 将这些子图连通起来 ,至少需要 n - 1 条边 ,因此 , 如果头表中 ai ( i > 0) 的下标 i 一旦小于 n - 1 ,则不 可能在α的基础上产生连通图 ,因此可以直接返回 上一层的递归调用 ,而不必进行下面的工作1 332汪 　卫等 :基于图论的频繁模式挖掘 为了提高效率 ,β条件图库生成时可利用连通 关系剔除今后对图的连通性无用的边1 当前的 SFP 树是前缀模式α的条件 SFP 树 ,因此 ,我们对于当 前树中每一个标号为 ai 的结点 ,自该结点沿树的分 支一直向上到根 ,路径上的所有能与 ai 连通的结点 或者能与α连通的结点将构成β条件图库中的一个 图1 这样可以剔除那些既不与α连通 ,又不与 ai 连 通的点1 同时考虑与 ai 连通的边和与α连通的边也 可以避免 ,有的边不能在分支上与 ai 连通 ,但却可 以通过α与 ai 其连通 ,反之亦然1 5 　实验与分析 测试环境为 PIII800 ,512MB 的 RAM1 算法用标 准的 C ++库编写 ,在 Windows 2000 Server 上测试1 测试数据生成有 5 个参数 :标号点集的大小 N ,图数据集合的大小| D | ,是否连通 ,图中的平均 顶点数| T | 和图中边的数目| E| 1 生成的测试数据 值服从正态分布1 首先生成标号点的全集 ,然后按照图数据集合 的大小逐个生成图 ,根据每个图的平均顶点数 ,按正 态分布函数生成实际的顶点数 ,并从标号点全集中 随机挑选出符合相应的标号点 ,生成标号边1 AM GM 算法只扫描数据库一遍 , 每一条边用 1b 表示 ,矩阵的运算基本都是位运算1 但随着数据 量的增大 ,矩阵随之增大1 而 SFP 算法摒弃了候选 图集的生成工作 ,虽然在构造时要考虑连通性 ,但总 体讲 ,代价比候选图集生成小得多1 我们对两个算 法进行了测试以进行比较1 我们做了如下 3 项测试 : (1) 对于一定大小的图集 ( | D | = 200 , | T | = 20) ,测试运行时间随支持度的变化情况 (结果见图 1)1 Fig1 1 　The performance and support1 图 1 　运行时间与支持度 (2) 对于一定大小的图集 ( | D | = 200) 和支持 度 15 % ,测试运行时间随顶点数的变化情况 (结果 见图 2)1 (3) 对于一定大小的图 ( | T | = 20) 和支持度 15 % ,测试运行时间随图数的变化情况 (结果见图 3)1 Fig1 2 　The performance and number of nodes1 图 2 　运行时间与平均顶点个数 Fig1 3 　The performance and size of graph database1 图 3 　运行时间与图库大小 　　由实验结果可以看到 SFP 比 AM GM 的性能高 很多 ,特别在支持度小和数据规模大的时候1 6 　利用惟一标号图的频繁模式发现权威 Web 资源 　　权威网页和权威社团的获取是 Web 检索中的 重要问题1 我们基于 SFP 实现了一个权威社团的获 取系统1 为了获取 Web 网页 ,我们实现了一个抓取网页 的工具 pageSnagger ,它以搜索引擎返回的结果为种 子 ,抓取这些网页链接的网页 ,本文设置搜索的页面 深度为 2 1 对获取的网页生成 Web 网页图库 GD 1 然后对 GD 应用 SFP 算法 ,获得最频繁出现的 社团 ,所谓社团就是那些针对某一主题 ,相互之间具 有协作关系的网页集合1 这些社团和我们所关心的 主题高度相符1 在本文中就是频繁出现的网页结构1 我们以 XML 作为检索词 ,对返回的结构构造 图库 ,以 13 作为最小频繁度 ,则找到 14 个网页 ,利 用 SFP 进行分析1 可以获得两个最大的频繁子图 , 它们分别以 w31org 和 xml1com 为中心1 7 　结 　　论 本文针对惟一标号图提出能生成连通频繁图的 AM GM 算法和 SFP 算法 ,相比之下 ,SFP 算法的性 能更优于 AM GM 算法1 今后的工作将主要放在如 何从非惟一标号的图中产生连通频繁图方面1 参 考 文 献 1 Rakesh Agrawal , Ramakrishnan Srikant1 Fast algorithms for min2 432 计算机研究与发展 　2005 , 42 (2) ing association rules in large databases1 VLDB1994 , Santiago , Chile , 1994 2 Heikki Mannila , et al11 Search and borders of theories in knowl2 edge discovery1 Data Mining and Knowledge Discovery , 1997 , 1 (3) : 241～258 3 Jong Soo Park , et al11 An effective Hash based algorithm for min2 ing association rules1 SIGMOD1995 , San Jose , USA , 1995 4 Sergey Brin , et al11 Dynamic itemset counting and implication rules for market basket data1 SIGMOD1997 , Tucson , USA , 1997 5 Ramesh C1 Agarwal , et al11 Depth first generation of long pat2 terns , KDD 2000 , Boston , USA , 2000 6 Ramesh C1 Agarwal , et al11 A tree projection algorithm for gen2 eration of frequent itemsets1 J1 of Parallel and Distributed Com2 puting , 2001 , 61 (3) : 350～371 7 Jiawei Han , Jian Pei , Yiwen Yin1 Mining frequent patterns with2 out candidate generation1 SIGMOD2000 , Dallas , USA , 2000 8 J1 Pei , et al11 H2Mine : Hyper2structure mining of frequent pat2 terns in large databases1 ICDM’01 , San Jose , CA , 2001 9 Mike Perkowitz , Oren Etzioni1 Adaptive sites : Automatically learning from user access patterns1 WWW’97 , Santa Clara , 1997 10 J1 Pei , et al11 PrefixSpan : Mining sequential patterns efficiently by prefix2projected pattern growth1 ICDE’01 , Heidelberg , 2001 11 Akihiro Inokuchi , et al11 An apriori2based algorithm for mining frequent substructures from graph data1 PD KK2000 , Lyon , France , 2000 12 Michihiro Kuramochi , et al11 Frequent subgraph discovery1 ICDM 2001 , San Jose , USA , 2001 Wang Wei , born in 19701 Received Ph1D1 degree in computer science from Fudan Uni2 versity in 19981 Now he is a professor in Fu2 dan University1 His current research inter2 ests include database , data mining and man2 agement of XML data1 汪卫 ,1970 年生 ,博士 ,教授 ,主要研究方向为数据库技术、 数据挖掘、XML 数据管理1 Zhou Haofeng , born in 19751 He received Ph1D1 degree in Computer Science from Fu2 dan University in 20031 Now he is working with IBM1 His current research interests in2 clude database , data mining1 周皓峰 ,1975 年生 ,博士 ,主要研究方向为 数据挖掘1 Yuan Qingqing , born in 19751 She received master degree in computer science from Fu2 dan University in 20031 Now she is a Ph1 D1 candidate in computer science of UCSB1 Her current research interests include database , data mining1 袁晴晴 ,1978 年生 ,博士研究生 ,主要研究方向为数据挖掘1 Lou Yubo , born in 19751 He received mas2 ter degree in computer science from Fudan University in 20031 His current research in2 terests include database , data mining , etc1 楼宇波 ,1978 年生 ,硕士 ,主要研究方向为 数据挖掘1 Shi Baile , born in 19351 Professor and Ph. D. supervisor in Fudan University1 His cur2 rent research interests include database , data mining , digital library and security database1 施伯乐 ,1935 年生 ,教授 ,博士生导师 ,主 要研究方向为数据库系统及其应用、数据 仓库与数据挖掘、数字图书馆、安全数据库1 Research Background Mining the frequent pattern from data set is one of the key success stories of data mining research1 Currently , most of the efforts are focused on the independent data such as the items in the marketing basket1 However , the objects in the real world often have close relationship with each other1 For example the structure of molecule and the map of web site can all be described by graph data1 The structure of XML data can be considered as a tree (a special kind of graph) 1 How to gain the frequent pattern from these graph data is the objective in this paper1 We select a simple type graph (the labels in the node are unique) for analysis1 Combining the graph2the2 ory and algorithms to generate frequent patterns , two new algorithms are proposed1 This paper is supported by the following projects : (1) The key project of NSFC“Research on the key techniques of digital library”; (2) The project of NSFC“The techniques of query and manage aggregate data”; (3) The 863 High Tech Plan“Web based Database new techniques”1 532汪 　卫等 :基于图论的频繁模式挖掘