论文部分内容阅读
图是一种灵活的数据结构,只要涉及到关系就可以表示成图的形式。图在实体网络,软件网络,社交网络中都有很多的应用。然而,大图很难被人们所理解和应用。人们往往喜欢某些特定的结点和连接结构,而认为其余的部分都是不相关的。从大图中挖掘出一个连通稠密子图就是一个基于这种情形的应用实例。例如考虑一个由一百万个结点和八百万条边生成的疾病生物图,给定几种疾病,挖掘出一个小的子图,要求尽量的连通各种疾病。带着几十个结点的稠密子图能很好的给出一个关于这几种疾病直接关系的图例。然而原始的疾病生物图,却不能清晰的给出几种疾病直接连接关系。本文主要讨论了稠密子图的查询算法。首先给出了稠密子图的问题定义：给定一个数据图和一些查询点,寻找一个包含所有查询点并且满足评价函数最大的稠密子图。这里的评价函数主要考虑两个因素：一个是子图相关度,另一个是子图稠密度。然后针对随机游走计算相关度需同步更新迭代的特征,提出了一种快速计算相关度的异步更新的BFS相关度方法。其次对于稠密子图的发现问题,提出了一个Fastsubgraph发现稠密子图的算法,该算法首先寻找一个包含查询点的子图集,然后动态组合子图集,利用评价函数筛选分值最大的候选子图,最后对不满足条件的候选子图进行扩展,得到最终的稠密子图。最后将算法CEPS和SISP算法改进为CEPSplus算法和SISPplus算法,使其也能发现稠密子图。CEPSplus算法的思想是先找一个包含所有查询点的连通子图,然后不断的添加结点,直到子图满足结点个数的限制并且评价函数最大。对于SISPplus算法,首先对粒子初始化阶段进行了改进,使其初始化速度更快；同时本文也修改了计算粒子的适应度公式；最后根据稠密性的信息特征,对算法的更新阶段进行了改进,使其能发现稠密子图。本文在实验阶段分别比较了FastSubgraph, CEPSplus, SISPplus算法在随机游走相关度和广度优先遍历相关度下的性能和参数信息。间接的证明了本文所提出的广度优先遍历相关度的正确性。通过用户评测的方法表明FastSubgraph, CEPSplus, SISPplus算法都能找稠密子图,但Fastsubgraph发现稠密子图的效果较好。