| 基于标签传播的半监督社区发现算法研究 |
| |
| 引用本文： | 魏芳芳,睢世杰,睢世凯.基于标签传播的半监督社区发现算法研究[J].教育技术导刊,2019,18(7):92-95. |
| |
| 作者姓名： | 魏芳芳 睢世杰 睢世凯 |
| |
| 作者单位： | 1. 国家开放大学 信息化部，北京 100039； 2. 福建南威软件有限公司，福建 福州 350000；3. 电子科技大学 计算机科学与工程学院，四川 成都 610054 |
| |
| 基金项目： | 国家开放大学校级项目（G18F0023Y） |
| |
| 摘 要： | 近年来，许多关于社区发现的优秀算法被提出并取得了较好的社区划分效果。但是到目前为止，没有任何一种算法能够同时在时间复杂度和准确度方面取得较好的表现。现实网络中往往存在一些有利于指导社区发现的标签信息，如must-link信息、cannot-link信息等。因此提出基于少量标签信息传播、拓扑结构的半监督社区发现算法S_LPA，分别在karate网络、dolphins网络、LFR基准网络上进行测试。实验结果表明，该算法S_LPA时间复杂度为O（m），相对其它算法，S_LPA在karate网络和dolphins网络的NMI值高于CNM、InfoMap、LPA算法，在LRF网络上准确度高出约20%；提高参数u后，S_LPA算法可识别其它算法不能识别的社区结构。
|
| 关 键 词： | 社区发现 半监督 标签信息 标签传播 |
| 收稿时间： | 2019-03-15 |
Semi-supervised Community Detection Based on Label Propagation |
| |
| WEI Fang-fang,SUI Shi-jie,SUI Shi-kai.Semi-supervised Community Detection Based on Label Propagation[J].Introduction of Educational Technology,2019,18(7):92-95. |
| |
| Authors: | WEI Fang-fang SUI Shi-jie SUI Shi-kai |
| |
| Institution: | 1. The Open University of China Information Department，Beijing 100039，China；2. Fujian Nanwei Software Co.， Ltd.， Fuzhou 350000，China； 3. School of Computer Science and Engineering， University of Electronic Science and Technology of China， Chengdu 610054，China |
| |
| Abstract: | In recent years， many algorithms about community detection have been proposed and achieved good results， but they belong to unsupervised learning and none of them can play a role in both time complexity and accuracy. In fact， many information in the network， like must-link information or cannot-link information， can help guide the community detection. So we propose the semi-supervised algorithm S_LPA based on label propagation， and combine the small information of the network with the topological structure. The S_LPA verifies that a small amount of label information in the network is helpful to guide community discovery. With the increase of label information， the NMI value increases continuously. The time complexity of S_LPA proposed in this paper is O（m）. Compared with other algorithms， the NMI value of S_LPA in karate networks and dolphins networks is higher than that of CNM， dolphins networks， InfoMap， LPA algorithm， and the accuracy is about 20% higher in LRF network； after improving the parameter u， S_LPA algorithm can also identify community structures that other algorithms can not recognize. |
| |
| Keywords: | community detection semi-supervised label information label propogation |
|
| 点击此处可从《教育技术导刊》浏览原始摘要信息 |
| 点击此处可从《教育技术导刊》下载免费的PDF全文 |
