大规模网络中的群组检测研究

在图的各种应用中,如挖掘社交网络、Web图挖掘和生物信息学挖掘等,从大型图中抽取密集子图是一个关键的,也是初始的步骤。本文主要研究多项式复杂度下的k-群组最密集子图问题,包括发现密集子图的精确算法和抽样算法。精确算法适用于小规模的图,而抽样算法在明显的时间加速和空间节省的基础上,产生高质量的近似结果。