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

Research on Clique Detection in Large-Scale Networks

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

Extracting dense subgraphs from large graphs is a key and initial step in a variety of graph application,ranging from mining social networks and the Web graph to bioinformatics. This paper focuses on the k-clique densest subgraph problem under polynomial time solvable formulations. These methods include exact algorithm and sampling algorithm. The exact algorithm can only apply in graph with small size. The sampling algorithm can produce high-quality approximations while providing significant speedups and improved space complexity.