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

A Community Partitioning Algorithm Based on Improved Fast-Newman Algorithm

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

The community partitioning is an important way of organizing and achieving knowledge from the massive scientific literature now. The Newman fast-algorithm is efficient in community partitioning,but its result sets is usually local optimal instead of global optimal due to basis of the local search theory, which make the result of community partitioning in science and technology literature relation network not the best. In this paper,we propose the concept of community contribution degree according to the characteristics of topological structure of com- munity structure in network graph and give its formula. In the meantime, we present a new CCN taking community contribution degree as community integration condition in order to overcome the shortcomings of the Newman Fast-Algorithm that is terminating iteration of com- munity partitioning when getting locally optimal solution of whole network graph. Finally, the experiment of comparison on actual network data in MATLAB shows that the CCN has better effects in community partitioning efficiency and Q value.