摘要： 针对GN算法计算效率低下的缺陷，提出一个基于边的中介值测度的发现网络潜在社团结构的新算法。该算法在完成所有边的中介值计算后，利用成分的独立性，采用并行移出各个成分中具有最大中介值的边的方法。通过理论分析，在作为实验测试平台的实际的数据集上进行实验验证，结果表明该算法是快速、有效的。

关键词: 社团发现, 社会网络, 社团结构, 图挖掘

Abstract: To address the slow speed of GN algorithm, a new algorithm based on betweenness scores of edges is presented for detecting the underlying community structure in networks. Employing component independency, this algorithm presents a new method through which all edges with the highest betweenness score in respect of each component is simultaneously removed when all betweenness scores are computed. It is proved that this algorithm is fast and effective through theoretical analysis and experiments with several real data sets which are acted as test beds.

Key words: community detection, social networks, community structure, graph mining

中图分类号: 

• TP311.13