作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

基于模糊聚类的社团划分算法

宋俐,谢刚,杨云云   

  1. (太原理工大学 信息工程学院,太原 030600)
  • 收稿日期:2015-09-02 出版日期:2016-08-15 发布日期:2016-08-15
  • 作者简介:宋俐(1992-),女,硕士研究生,主研方向为复杂网络、数据挖掘;谢刚,教授、博士;杨云云,博士研究生。
  • 基金资助:
    国家留学回国人员科技活动择优基金资助项目([2012]258号);山西省(人社部)留学回国人员科技活动择优基金资助项目([2012]316号)。

Community Partition Algorithm Based on Fuzzy Clustering

SONG Li,XIE Gang,YANG Yunyun   

  1. (College of Information Engineering,Taiyuan University of Technology,Taiyuan 030600,China)
  • Received:2015-09-02 Online:2016-08-15 Published:2016-08-15

摘要: 目前大多数的社团划分算法将网络划分为若干个相互独立的社团,但是对于某些实际网络,社团与社团之间不是相互独立的,即某些社团之间存在公共节点,大多数的社团划分算法无法对这类实际网络进行合理的社团划分。针对该问题,提出一种基于节点间共享邻居数的隶属函数,结合模糊聚类算法进行社团划分,即设置合理的截集阈值α,将位于同一个等价类内的节点划分到同一社团。在GN经典人造网和空手道俱乐部网络、海豚网络上进行测试的结果表明,对社团结构已知的网络划分结果符合实际情况,在对海豚网络进行社团划分时,与Newman快速算法、利用堆结构的贪婪算法、标签传播算法相比,该算法得到的模块度更高,并且能够更好地检测出实际网络中的公共节点。

关键词: 复杂网络, 社区发现, 隶属函数, 模糊等价关系, 等价类

Abstract: At present,most of the community partition algorithms divide the network into several independent associations.But for some real networks,the communities are not independent of each other.There is a common node among some communities,and most of the community partition algorithms cannot be divided into rational society.In view of this situation,a membership function based on the number of shared neighbors between nodes is proposed.It uses fuzzy equivalence relation to detect communities with the combination of the fuzzy clustering algorithm,dividing the nodes within the same equivalence class to the same communities by setting a reasonable threshold α.This algorithm is tested on GN benchmark,Karate Club network and Dolphin network.Results show that the network partition results of known community structure conform to the actual situation.When making community detection for Dolohin network,compared with Fast Newman(FN) algorithm,greedy algorithm using pile structure and Label Propagation Algorithm(LPA),this algorithm achieves higher modularity and can better detect public nodes in the real network.

Key words: complex network, community detection, membership function, fuzzy equivalence relation, equivalence class

中图分类号: