一种基于Newman快速算法改进的社团划分算法

社团划分目前是从海量科技文献中进行知识组织和发现的一种重要方法,其中Newman快速算法是目前效率较高的一种社团划分算法,然而由于Newman快速算法是一种基于局部搜索算法,算法的结果集往往是局部最优而不是全局最优,导致科技文献关系网络中的社团划分结果往往不是最优的社团结构。根据网络图中社团结构拓扑关系的特点,提出了社团贡献度的概念,并给出了计算公式;同时,为了克服Newman快速算法在社团合并迭代过程中获取到局部最优解而终止迭代的缺点,提出一种直接以社团贡献度为社团合并条件的CCN算法。最后在MATLAB环境中,用实际网络数据进行对比实验验证,结果表明,改进的CCN算法在社团划分效率和Q值结果上有更理想的效果。