[1]付常雷.一种基于 Newman 快速算法改进的社团划分算法[J].计算机技术与发展,2018,28(01):33-35.[doi:10.3969/ j. issn.1673-629X.2018.01.007]
　FU Chang-lei.A Community Partitioning Algorithm Based on Improved Fast-Newman Algorithm[J].Computer Technology and Development,2018,28(01):33-35.[doi:10.3969/ j. issn.1673-629X.2018.01.007]
点击复制

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

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
28
期数:
2018年01期
页码:
33-35
栏目:
智能、算法、系统工程
出版日期:
2018-01-10

文章信息/Info

Title:
A Community Partitioning Algorithm Based on Improved Fast-Newman Algorithm
文章编号:
1673-629X(2018)01-0033-0
作者:
付常雷
中国科学院文献情报中心,北京 100190
Author(s):
FU Chang-lei
National Science Library,Chinese Academy of Sciences,Beijing 100190,China
关键词:
社团划分; Newman 快速算法;  Q 值; 贡献度
Keywords:
community partitioning; fast-Newman algorithm;  Q value; community contribution degree
分类号:
TP311
DOI:
10.3969/ j. issn.1673-629X.2018.01.007
文献标志码:
A
摘要:
社团划分目前是从海量科技文献中进行知识组织和发现的一种重要方法,其中 Newman 快速算法是目前效率较高的一种社团划分算法,然而由于 Newman 快速算法是一种基于局部搜索算法,算法的结果集往往是局部最优而不是全局最优,
导致科技文献关系网络中的社团划分结果往往不是最优的社团结构。 根据网络图中社团结构拓扑关系的特点,提出了社团贡献度的概念,并给出了计算公式;同时,为了克服 Newman 快速算法在社团合并迭代过程中获取到局部最优解而终止迭代的缺点,提出一种直接以社团贡献度为社团合并条件的 CCN 算法。 最后在 MATLAB 环境中,用实际网络数据进行对比实验验证,结果表明,改进的 CCN 算法在社团划分效率和 Q 值结果上有更理想的效果。
Abstract:
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 community 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 community 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.

相似文献/References:

[1]朱永真 夏正友 卜湛 刘新建.虚拟社区中的社团结构研究与分析[J].计算机技术与发展,2011,(01):46.
　ZHU Yong-zhen,XIA Zheng-you,BU Zhan,et al.Research and Analysis on Community Structure in Virtual Community[J].Computer Technology and Development,2011,(01):46.
[2]王伟,李玲娟. 一种基于聚类的社团划分算法[J].计算机技术与发展,2015,25(10):119.
　WANG Wei,LI Ling-juan. A Clustering-based Community Division Algorithm[J].Computer Technology and Development,2015,25(01):119.
[3]张 猛,李玲娟.稳定的标签传播社团划分算法研究[J].计算机技术与发展,2020,30(01):129.[doi:10. 3969 / j. issn. 1673-629X. 2020. 01. 023]
　ZHANG Meng,LI Ling-juan.Research on Stable Label Propagation Community Division Algorithm[J].Computer Technology and Development,2020,30(01):129.[doi:10. 3969 / j. issn. 1673-629X. 2020. 01. 023]
[4]张梦园,李玲娟.基于节点重要性和模块度优化的社团划分算法[J].计算机技术与发展,2023,33(04):126.[doi:10. 3969 / j. issn. 1673-629X. 2023. 04. 019]
　ZHANG Meng-yuan,LI Ling-juan.Community Division Algorithm Based on Node Importance and Modularity Optimization[J].Computer Technology and Development,2023,33(01):126.[doi:10. 3969 / j. issn. 1673-629X. 2023. 04. 019]

更新日期/Last Update: 2018-03-12