关键词:
社区结构
社团划分
局部搜索算法
圈比
高阶结构
摘要:
社团是复杂网络最重要的非平凡拓扑结构之一,其对于复杂系统的功能实现具有重要意义,如何实现高效、准确的社团划分是复杂网络领域最重要的任务之一。有别于基于模块度优化、动力学或谱分析等方式的经典全局算法,局部搜索(Local Search,LS)算法提出了社团中心这一概念,从全新视角出发只需依赖节点局域信息即可在线性时间复杂度内取得很好的社团划分效果,同时具有良好的可解释性,对于处理大规模网络更具优势。然而,原始LS算法使用度值来近似节点影响力,在同质网络中,由于节点度值过于接近,难以基于度值差异识别出社团中心,进而导致划分效果不佳。近期研究表明,复杂网络中的环结构等高阶结构能够更好反映节点影响力,因此我们使用圈比中心性来改进原始LS算法,不仅提高了其在同质网络中的准确率,在绝大多数实际异质网络中也取得了更好的划分效果。