第41卷第13期
2011年7月
数学的实践与认识
MATHEMATICS
IN
PRACTICE
AND
THEORy
Vbl.41.No.13
JuL.2011
J.t’'’’-’,'',·,、
;应
用i
~t·‘·tI。·。t‘·‘,
图模式挖掘中的子图同构算法
董安国·,一,高琳。,赵建邦。
(1.长安大学理学院,陕西西安710064)
(2.西安电子科技大学计算机学院,陕西西安710071)
摘要:图模式挖掘问题在w|eb挖掘、生物信息学、社会关系等众多领域有广泛的
应用,它涉及到子图的搜索以及子图的同构问题.这两个问题都具有相当高的计算
复杂度,现有的子图同构问题大多采用最小编码算法,但对无标签图特别是对无标
签无向图,该算法效率较底,从而子图的同构成为图模式挖掘问题的一个瓶颈.针对
无标签图,以代数理论为基础,分别利用度序列和特征值构造了两种子图同构算法,
用于对有向图和无向图的同构判别.最后对2个真实生物网络进行了仿真实验,结
果表明,算法的效率优于现有算法.
关键词:
图模式;频繁子图;子图同构;特征值
1引言
在生物信息学、药物发现、社会网络、集成电路的布局布线、wreb数据挖掘、软件测试、
网络安全等众多领域都积累了大量的关于图的数据,这些数据中包含了重要的信息,需要对
图进行挖掘.例如在基因调控网络和蛋白质相互作用网络中,存在一种具有特定生物功能的
结构,用图的模型来描述即为模体,它就是一个子图,这个子图在真实网络中出现的频率远高
于对应的随机网络.在社会网络中发现具有一定功能的社团结构等问题,也涉及到频繁子图
的搜索.所以,图模式挖掘问题的研究具有重要的理论和应用价值.
图模式挖掘问题的研究涉及到两个基本问题:子图搜索和子图频率的计算.
子图搜索就是从一个大图中搜索出所有固定大小的子图(庇个节点),最近几年,关于这
一问题的研究很受关注,比较有影响的算法有:2000年,A.Inokuchi等人【1】提出的AGM算
法,2002年,x.Yan
and
J.Han【2】提出的gSpan算法,2004年,M.Kuramoclli等人【3j提出的
FsG算法,2006年,S.w醯nicke【4j提出的Esu算法等.
计算子图频率就是将所有的子图按同构关系进行分类,然后统计出各类子图的频率;所
以其根本问题是子图同构.在一般意义下,判定图的同构是NP一完全问题【5】'有人试图用图
的一组不变量来确定图的同构,如回路数、树数、连通片数等,这些尝试都归于失败,因为不
同构的图也会出现完全相同的不变量【6】’多年来,人们一直在寻找一种有效的同构判定方法.
但是,在图模式挖掘问题中,涉及到图均是节点数很小的子图(见文献【1—4】,节点数不超过7),
收稿日期:2008-08-06
资助项目:国家自然科学基金(60933009);陕西省自然科学计划项目(sJ08-zTl5)
万方数据