局部最大核子图搜索算法研究

罗碧彤 孙晶 李源 李欣蔚

（北方工业大学信息学院 北京市 100144）

1 引言

由于图形数据在不同应用中的普遍存在，图形分析已经引起了研究界和行业界的广泛关注。图分析中的一个主要问题是给定一个图，识别图中的内聚子图，如k核，k型桁架，派系，n-派系和n-族。其中，k核能在线性时间复杂度内计算，被定义为无向图G的极大子图，使子图中的所有顶点的度至少为k。社区搜索在社会网络分析中具有重要意义，对于图中给定顶点，目标是找到该顶点所属的最佳社区。直观地说，对于给定顶点的最佳社区应该在顶点附近。Cui等人提出了一种局部搜索策略，即在一个顶点附近进行搜索，以寻找该顶点的最佳社区。大多数现实生活中的复杂网络，包括互联网、社交网络和生物神经网络，都包含了社区结构。网络可以被划分为组，其中连接紧密，组与组之间的连接是稀疏的。在真实的网络中寻找社区是一项重要的分析任务，因为社区结构充满意义，它们与网络的功能高度相关。由于社区结构的重要性，社区搜索的问题，即寻找顶点最可能的社区，对许多现实生活网络和应用十分重要。在信息时代，图的规模变得巨大，图模型所代表的数据中的价值也越来越重要。因此，在大规模图中寻找核数最大的包含查询点的极大连通子图是一个重要且有意义的问题。在探索核数最大的包含查询点的极大连通子图的过程中，从查询点开始向外扩展，其中判断扩展的顶点是否具有提升当前k核的能力是扩展阶段的主要问题。……