邹晓红,郭景峰,2,贺释千,2,陈 晶,刘院英

1(燕山大学 信息科学与工程学院,河北 秦皇岛 066004)2(河北省虚拟技术与系统集成重点实验室,河北 秦皇岛 066004)3(河北经贸大学 信息技术学院,石家庄 050061)

1 引 言

图是表现力很强的数据结构,能够充分表示实体自身的信息及实体间的联系,因而在生物信息学、化学等领域广泛应用.并且随着对结构化数据分析需求的大量增加,通过图建模进行图挖掘问题已经成为一个非常重要的研究课题.图分类是图挖掘的一个重要研究分支[1],而图向量化是图分类的基础,通过对图提取特征向量化后根据得到的图向量可以进行图分类.目前关于图分类的研究中能用于提取分类特征的算法有两类,一类是子图分布算法,另一类是频繁子图挖掘算法.用于图分类的子图分布算法的相关研究最早起源于生物学与社会网络等领域,其目的是检测图的非平凡特性用于发现不同图之间的异同,在生物学研究中,通过检测两组蛋白质交互网络的拓扑结构的不同可以发现两者功能上的差异.例如通过把要检测物质的化学结构和已知的致癌症物质抽象成图比对,就可以初步判断要检测物质是否致癌.

国外对用于图分类的子图分布算法研究已经有很多,一般是基于一定的图模型,将现实世界中的网络抽象为图并建模,在构建图模型的基础上再进行算法研究.如文献[2]中首先定义小诱导子图为Graphlet,简称为Graphlet模型,提出使……