基于NSGA2的网络环境下多标签种子节点选择

李磊; 楚喻棋; 汪萌; 韩莉; 吴信东

doi:10.11999/JEIT161266

基于NSGA2的网络环境下多标签种子节点选择

doi: 10.11999/JEIT161266

1.
(合肥工业大学计算机与信息学院合肥 230009) ②(科学技术部基础研究管理中心北京 100862) ③(路易斯安那州立大学计算机与信息学院拉斐特 70503 美国)

基金项目:

国家973规划项目(2013CB329604)，国家重点研发计划项目(2016YFB1000901)，国家自然科学基金项目(61503114)

计量
- 文章访问数: 1320
- HTML全文浏览量: 126
- PDF下载量: 346
- 被引次数: 0
出版历程
- 收稿日期: 2016-11-24
- 修回日期: 2017-04-11
- 刊出日期: 2017-09-19

NSGA2-based Multi-label Seed Node Selection in Network Environments

1.
(School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230009, China)
2.
(School of Computer Science and Information Engineering, Hefei University of Technology, Hefei 230009, China)

Funds:

The National 973 Program of China (2013CB329604), The National Key Research and Development Program of China (2016YFB1000901), The National Natural Science Foundation of China (61503114)

摘要

摘要: 随着社交网络规模的不断扩大，网络节点的标签分类也不再单一，变得丰富多样，这些促使了社交网络中的多标签分类问题成为一个重要的研究领域。以前的研究重点主要集中在提高预测网络节点标签的精度上，而忽略了得到节点信息所产生的包含时间消耗和计算资源等在内的系统开销问题。可现如今随着网络规模不断扩大且复杂性不断增强，之前所忽略的系统开销问题变得越来越严重，增加了预测标签的成本，加重了预测网络节点标签的难度。该文针对这一问题提出了基于NSGA2算法的网络环境下多标签种子节点选择算法(NAMESEA算法)，目的是在能大大降低预测节点标签所消耗的系统开销的前提下一定程度上提高预测标签的精度。该文将NAMESEA算法与其他多标签预测算法在多个真实数据集上进行实验对比，结果证明NAMESEA算法大大降低了预测节点标签的系统开销并且提高了预测精度。
- 社交网络 /
- 多标签分类 /
- NSGA2 /
- 系统开销
Abstract: With the expanding scale of social networks, the label classification of nodes in the network is no longer single but various, which prompts the multi-label classification in social networks to become an important research area. The previous research focuses on how to improve the precision of the predicted labels, while ignoring the system overhead caused by obtaining the node information, such as time consumption and computing memory occupancy. Now, as both expansion and complexity of the networks are increasing, the problem of previously neglected system overhead is becoming the more and the more serious. It increases not only the cost but also the difficulty of predicting labels. In this paper, an NSGA2-based multi-label seed selection algorithm in network environments (NAMESEA) is proposed to improve the accuracy of label prediction on the condition that reducing both the time consume and the memory occupancy. Compared with other multi-label prediction algorithms on multiple real datasets, NAMES
- Social networks /
- Multi-label classification /
- NSGA2 /
- System overhead

HTML全文

参考文献(32)

WANG X and SUKTHANKAR G. Multi-label relational neighbor classification using social context features[C]. Proceedings of the 15th ACM SIGKDD International Conference on knowledge Discovery and Data Mining, Chicago, USA, 2013: 464-472.

吴信东, 赵银凤, 李磊. 基于种子节点选择的网络环境下多标签分类算法研究[J]. 电子学报, 2016, 44(9): 2074-2080. doi: 10.3969/j.issn.0372-2112.2016.09.008.

WU Xingdong, ZHAO Yinfeng, and LI Lei. Multi-label classification in network environments via seed nodes selection[J]. Acta Electronica Sinica, 2016, 44(9): 2074-2080. doi: 10.3969/j.issn.0372-2112.2016.09.008.

LI Lei, HE Jianping, WANG Meng, et al. Trust agent-based behavior induction in social networks[J]. IEEE Intelligent Systems, 2016, 30(1): 24-30. doi: 10.1109/ MIS.2016.6.

许宇光, 潘惊治, 谢惠扬. 基于最小点覆盖和反馈点集的社交网络影响最大化算法[J]. 电子与信息学报, 2016, 38(4): 795-802. doi: 10.11999/JEIT160019.

XU Yuguang, PAN Jingzhi, and XIE Huiyang. Minimum vertex covering and feedback vertex set-based algorithm for influence maximization in social network[J]. Journal of Electronics Information Technology, 2016, 38(4): 795-802. doi: 10.11999/JEIT160019.

陈季梦, 陈佳俊, 刘杰, 等. 基于结构相似度的大规模社交网络聚类算法[J]. 电子与信息学报, 2015, 37(2): 449-454. doi: 10.11999/JEIT140512.

CHEN Jimeng, CHEN Jiajun, LIU Jie, et al. Clustering algorithms for large-scale social networks based on structural similarity[J]. Journal of Electronics Information Technology, 2015, 37(2): 449-454. doi: 10.11999/JEIT140512.

ZHANG M and ZHOU Z. A k-nearest neighbor based algorithm for multi-label classification[C]. Proceedings of the IEEE International Conference on Granular Computing, Beijing, China, 2005: 718-721.

HULLER E, FURNKRANZ J, CHENG W, et al. Label ranking by learning pairwise preferences[J]. Artificial Intelligence, 2008, 172(16): 1897-1916. doi: 10.1016/j.artint. 2008.08.002.

MACSKASSY S and PROVOST F. A simple relational classifier[C]. Proceedings of the Second Workshop on Multi- Relational Data Mining at ACM SIGKDD, Washington, DC, USA, 2003: 64-76.

BOUTELL M R, LUO Jiebo, SHEN Xipeng, et al. Learning multi-label scene classification[J]. Pattern Recognition, 2004, 37(9): 1757-1771. doi: 10.1016/j.patcog.2004.03.009.

刘世超, 朱福喜, 甘琳. 基于标签传播概率的重叠社区发现算法[J]. 计算机学报, 2016, 39(4): 717-729. doi: 10.11897/SP.J. 1016.2016.00717.

LIU Shichao, ZHU Fuxi, and GAN Lin. A label-propagation- probability-based algorithm for overlapping community detection[J]. Chinese Journal of Computers, 2016, 39(4): 717-729. doi: 10.11897/SP.J.1016.2016.00717.

邢千里, 刘列, 刘奕群, 等. 微博中用户标签的研究[J]. 软件学报, 2015, 26(7): 1626-1637. doi: 10.13328/j.cnki.jos.004655.

XING Qianli, LIU Lie, LIU Yiqun, et al. Study on user tags in Weibo[J]. Journal of Software, 2015, 26(7): 1626-1637. doi: 10.13328/j.cnki.jos.004655.

ZHANG Ling and ZHOU Zhihua. A lazy learning approach to multi-label learning[J]. Pattern Recognition, 2007, 40(7): 2038-2048. doi: 10.1016/j.patcog.2006.12.019.

TANG L and LIU H. Scalable learning of collective behavior based on sparse social dimensions[C]. Proceedings of the ACM CIKM, Hong Kong, China, 2009: 1107-1116.

申超波, 王志海, 孙艳歌.基于标签聚类的多标签分类算法[J]. 软件, 2014, 33(8): 16-21. doi: 10.3969/j.issn.1003-6970. 2014.08.004.

SHEN Chaobo, WANG Zhihai, and SUN Yange. A multi- label classification algorithm based on label clustering[J]. Software, 2014, 33(8): 16-21. doi: 10.3969/j.issn.1003-6970. 2014.08.004.

郑伟, 王朝坤, 刘璋, 等.一种基于随机游走模型的多标签分类算法[J]. 计算机学报, 2010, 33(8): 1418-1426. doi: 10.3724/ SP.J.1016.2010.01418.

ZHENG Wei, WANG Chaokun, LIU Zhang, et al. A multi-label classification algorithm based on random walk model[J]. Chinese Journal of Computers, 2010, 33(8): 1418-1426. doi: 10.3724/SP.J.1016.2010.01418.

张振海, 李士宁, 李志刚, 等. 一类基于信息熵的多标签特征选择算法[J]. 计算机研究与发展, 2013, 50(6): 1177-1184.

ZHANG Zhenhai, LI Shining, LI Zhigang, et al. Multi-label feature selection algorithm based on information entropy[J]. Journal of Computer Research and Development, 2013, 50(6): 1177-1184.

KALYANMOY D, AMRIT P, SAMEER A, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

刘晓娟, 闫海兰. 基于NSGA2算法的并行机多目标调度问题研究[J]. 物联网技术, 2013, 10(1): 43-47.

LIU Xiaojuan and YAN Hailan. Research on the multi- objective scheduling problem of parallel machine based on NSGA2 algorithm[J]. Internet of Things, 2013, 10(1): 43-47.

孙建龙, 吴锁平, 陈燕超. 基于改进NSGA2算法的配电网分布式电源优化配置[J]. 电力建设, 2014, 35(2): 86-90. doi: 10.3969/j.issn.1000-7229.2014.02.017.

SUN Jianlon, WU Suoping, and CHEN Yanchao. Optimal configuration of distributed generation in distribution network based on improved NSGA2[J]. Electric Power Construction, 2014, 35(2): 86-90. doi: 10.3969/j.issn.1000- 7229.2014.02.017.

张利. NSGA2算法及其在电力系统稳定器参数优化中的应用[D]. [硕士论文], 西南交通大学, 2013: 3-9.

ZHANG Li. NSGA2 Algorithm and its application in optimizing power system stabilizer parameters[D]. [Master dissertation],Southwest Jiaotong University, 2013: 3-9.

NEVILLE J, GALLAGHER B, ELIASSI-RAD T, et al. Correcting evaluation bias of relational classifiers with network cross validation[J]. Intelligent Systems, 2016, 31(1), 24-30. doi: 10.1007/s10115-010-0373-1.

施引文献

资源附件(0)

访问统计