李 源，范晓林，孙 晶，赵宇海

1(北方工业大学 信息学院，北京 100144) 2(东北大学 计算机科学与工程学院，沈阳 110819)

1 引 言

图模型的提出使现实世界万物得以被描述和分析，这使得图模型可以被应用到许多不同领域，例如社交网络，生物网络以及协作网络等.给定一个图G=(V，E)，其V中的顶点代表感兴趣的实体，E中的边代表实体之间的关系.则本文研究的密集子图(Densest Subgraph，DS)是图G中最稠密或具有最高密度的子图[1].而密集子图发现可以解决现实生活中的许多问题，比如它可以被用于事件检测，生物分析以及社区发现等方面.具体地，在事件检测方面，发现的密集子图是社交网络中的“稠密部分”，可代表一个事件[2]；在生物分析方面，密集子图可以帮助生物学的研究人员鉴定基因组DNA[3]和基因注释图[4]中的调控基序；在社区发现方面，密集子图可以在社交媒体中找到具有相同兴趣的社区[5]，可根据社区的特性实现产品的精准推荐和营销.因此密集子图发现这一关键问题值得被深入研究.

目前为止，密集子图发现已经在简单静态图和特定动态图中被广泛研究.1)对于简单静态图中的密集子图发现主要有基于边密度、h-团密度和模式密度的研究[6]，其主要是先定义团[7]或模式，再从图中检测其最高密度的子图；还有一种是最优类团[8]，它提取了比基于边密度更密集、直径更小的子图；当然，还有其它的密集子图发现方法，比如k-truss[9]，k-(r，s)核[10]，k-plexes[11]等.2)特定动态图中的密集子图发现方法有:McGregor等人[12]提出了在动态图数据模型上逼近密集子图的方法，其增加了对动态图的挖掘分析；……