[1]柴变芳,曹欣雨,魏春丽,等.一种主动半监督大规模网络结构发现算法[J].深圳大学学报理工版,2020,37(3):243-250.[doi:10.3724/SP.J.1249.2020.03243]
 CHAI Bianfang,CAO Xinyu,WEI Chunli,et al.An active semi-supervised structure exploring algorithm for large networks[J].Journal of Shenzhen University Science and Engineering,2020,37(3):243-250.[doi:10.3724/SP.J.1249.2020.03243]
点击复制

一种主动半监督大规模网络结构发现算法()
分享到:

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第37卷
期数:
2020年第3期
页码:
243-250
栏目:
电子与信息科学
出版日期:
2020-05-20

文章信息/Info

Title:
An active semi-supervised structure exploring algorithm for large networks
文章编号:
202003005
作者:
柴变芳1曹欣雨1魏春丽1王建岭2
1)河北地质大学信息工程学院,河北石家庄 050031
2)河北中医学院教务处,河北石家庄 050200
Author(s):
CHAI Bianfang1 CAO Xinyu1 WEI Chunli1 and WANG Jianling2
1) School of Information Engineering, Hebei GEO University, Shijiazhuang 050031, Hebei Province, P.R.China
2) Office of Educational Administration, Hebei University of Chinese Medicine, Shijiazhuang 050200, Hebei Province, P.R.China
关键词:
计算机应用大规模网络半监督聚类主动学习在线变分期望最大算法成对约束
Keywords:
computer application large networks semi-supervised clustering active learning online variational expectation maximization (onlineVEM) algorithm pairwise constraints
分类号:
TP181
DOI:
10.3724/SP.J.1249.2020.03243
文献标志码:
A
摘要:
在线变分期望最大(online variational expectation maximization, onlineVEM)算法可快速发现大规模网络的聚类模式,但在网络结构复杂时算法的处理结果稳定性和准确性欠佳.为更快更准地识别其聚类模式,提出一种主动半监督在线变分期望最大(active semi-supervised onlineVEM, ASonlineVEM)算法.算法首先自动选择代表节点,确定类的个数,并基于代表节点初始化模型;然后迭代执行3个任务:运行在线算法onlineVEM、主动选节点及模型更新,直至算法达到准确率的设定阈值或收敛.在不同结构的人工网络和真实网络上的实验结果表明,ASonlineVEM算法的准确性和效率均优于同类算法.ASonlineVEM算法利用主动选择的节点先验信息提高了网络聚类模式发现的稳定性及准确性,提高了在线算法的运行效率.
Abstract:
The algorithm of online variational expectation maximization (onlineVEM) can explore the clustering patterns of large networks fast. But the stability and accuracy of the algorithm are poor when the network structure is complex. In order to identify the clustering patterns faster and more accurately, an active semi-supervised online variational expectation maximization (ASonlineVEM) algorithm is proposed. Firstly, the algorithm selects the representative nodes automatically, determines the numbers of clusters, and initializes the model based on the representative nodes. Then, it iteratively executes three tasks: running the online algorithm onlineVEM, actively selecting nodes, and updating parameters until the algorithm reaches the preset threshold of accuracy or convergences. Experiments on artificial networks and real networks with different structures show that the accuracy and efficiency of ASonlineVEM algorithm are better than those of similar algorithms. The ASonlineVEM algorithm uses the priori information of actively selected nodes to improve the stability and accuracy of clustering pattern detection of networks and to improve the efficiency of online algorithm.

参考文献/References:

[1] CHAI Bianfang, JIA Caiyan, YU Jian. An online expectation maximization algorithm for exploring general structure in massive networks[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 438: 454-468.
[2] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3/4/5): 75-174.
[3] 赵学华,杨博,陈贺昌.一种高效的随机块模型学习算法[J].软件学报,2016,27(9):2248-2264.
ZHAO Xuehua, YANG Bo, CHEN Hechang. An efficient stochastic block model learning algorithm[J]. Journal of Software, 2016, 27(9): 2248-2264.(in Chinese)
[4] YA Fangli,CAI Yanjia,JIAN Qiangli, et al. Enhanced semi-supervised community detection with active node and link selection[J]. Physica A:Statistical Mechanics and Its Applications,2018, 510:219-232.
[5] EATON E, MANSBACH R. A spin-glass model for semi-supervised community detection[C]// Proceedings of the 26th AAAI Conference on Artificial Intelligence. Atlanta, USA: AAAI Press, 2012: 900-906.
[6] MA Xiaoke, GAO Lin, YONG Xuerong, et al. Semi-supervised clustering algorithm for community structure detection in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2010, 389: 187-197.
[7] ZHANG Zhongyuan. Community structure detection in complex networks with partial background information[J]. Europhysics Letters, 2013, 101(4): 48005.
[8] ZHANG Zhongyuan, SUN Kaidi, WANG Siqi. Enhanced community structure detection in complex networks with partial background information[J]. Scientific Reports, 2013, 3(11): 3241.
[9] YANG Liang, JIN Di, HE Dongxiao, et al. Improving the efficiency and effectiveness of community detection via prior-induced equivalent super-network[J]. Scientific Reports, 2017, 7(1): 634.
[10] YANG Liang, CAO Xiaochun, JIN Di, et al. A unified semi-supervised community detection framework using latent space graph regularization[J].IEEE Transactions on Cybernetics, 2015, 45(11): 2585-2598.
[11] YANG Liang, GE Meng, JIN Di, et al. Exploring the roles of cannot-link constraint in community detection via multi-variance mixed Gaussian generative model[J]. PLoS ONE, 2017, 12(7): e0178029.
[12] CHENG Jianjun, LENG Mingwei, LI Longjie, et al. Active semi-supervised community detection based on must-link and cannot-link constraints[J]. PLoS ONE, 2014, 9(10): e110088.
[13] YANG Liang, JIN Di, WANG Xiao, et al. Active link selection for efficient semi-supervised community detection[J]. Scientific Report, 2015, 5(3): 9039.
[14] JIA Caiyan, LI Yafang, CARSON M B, et al. Node attribute-enhanced community detection in complex networks[J]. Scientific Reports, 2017, 7(1): 2626.
[15] LI Yafang, JIA Caiyan, YU Jian. A parameter-free community detection method based on centrality and dispersion of nodes in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2015, 438: 321-334
[16] NEWMAN M E J, LEICHT E A. Mixture models and exploratory analysis in networks[J] Proceedings of the National Academy of Sciences, 2007, 104(23): 9564-9569.
[17] LIU Xin, CHENG Huimin, ZHANG Zhongyuan. Evaluation of community detection methods[J]. IEEE Transactions on Knowledge and Data Engineering. (2019-04-17).http://ieeexplore.ieee.org/stamp.jsp?tp=&arnumber:8693534.
[18] NEWMAN M. Network data[DB/OL]. (2013-04-19). http://www-personal.umich.edu/~mejn/netdata/.
[19] TRAUD A L, MUCHA P J, PORTER M A. Social structure of Facebook networks[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(16): 4165-4180.

相似文献/References:

[1]蔡华利,刘鲁,樊坤,等.基于BPSO的web服务推荐策略[J].深圳大学学报理工版,2010,27(1):49.
 CAI Hua-li,LIU Lu,FAN Kun,et al.Web services recommendation based on BPSO[J].Journal of Shenzhen University Science and Engineering,2010,27(3):49.
[2]朱泽轩,张永朋,尤著宏,等.高通量DNA测序数据压缩研究进展[J].深圳大学学报理工版,2013,30(No.4(331-440)):409.[doi:10.3724/SP.J.1249.2013.04409]
 Zhu Zexuan,Zhang Yongpeng,You Zhuhong,et al.Advances in the compression of high-throughput DNA sequencing data[J].Journal of Shenzhen University Science and Engineering,2013,30(3):409.[doi:10.3724/SP.J.1249.2013.04409]
[3]张滇,明仲,刘刚,等.基于传感器节点的无线接收信号强度研究(英文)[J].深圳大学学报理工版,2014,31(1):63.[doi:10.3724/SP.J.1249.2014.01063]
 Zhang Dian,Ming Zhong,Liu Gang,et al.An empirical study of radio signal strength in sensor networks using MICA2 nodes[J].Journal of Shenzhen University Science and Engineering,2014,31(3):63.[doi:10.3724/SP.J.1249.2014.01063]
[4]廖日军,李雄军,徐健杰,等.Arnold变换在二值图像置乱应用中若干问题讨论[J].深圳大学学报理工版,2015,32(4):428.[doi:10.3724/SP.J.1249.2015.04428]
 Liao Rijun,Li Xiongjun,Xu Jianjie,et al.Discussions on applications of Arnold transformation in binary image scrambling[J].Journal of Shenzhen University Science and Engineering,2015,32(3):428.[doi:10.3724/SP.J.1249.2015.04428]
[5]李雄军,廖日军,李金龙,等.图像Arnold变换中的准对称性问题与半周期现象[J].深圳大学学报理工版,2015,32(6):551.[doi:10.3724/SP.J.1249.2015.06551]
 Li Xiongjun,Liao Rijun,Li Jinlong,et al.Quasi-symmetry and the half-cycle phenomenon in scrambling degrees for images with pixel locations scrambled by Arnold transformation[J].Journal of Shenzhen University Science and Engineering,2015,32(3):551.[doi:10.3724/SP.J.1249.2015.06551]

备注/Memo

备注/Memo:
Received:2019-04-15;Accepted:2019-06-27
Foundation:National Natural Science Foundation of China(61503260); Natural Science Foundation of Hebei Province (F2019403070)
Corresponding author:Professor WANG Jianling. E-mail: wang_jl@126.com
Citation:CHAI Bianfang, CAO Xinyu, WEI Chunli, et al. An active semi-supervised structure exploring algorithm for large networks[J]. Journal of Shenzhen University Science and Engineering, 2020, 37(3): 243-250.(in Chinese)
基金项目:国家自然科学基金资助项目(61503260);河北省自然科学基金资助项目(F2019403070)
作者简介:柴变芳(1979—),河北地质大学副教授、博士.研究方向:复杂网络分析和机器学习等.E-mail:chaibianfang@163.com
引文:柴变芳,曹欣雨,魏春丽,等.一种主动半监督大规模网络结构发现算法[J]. 深圳大学学报理工版,2020,37(3):243-250.
更新日期/Last Update: 2020-05-30