基于NSGA2的網(wǎng)絡(luò)環(huán)境下多標(biāo)簽種子節(jié)點(diǎn)選擇
doi: 10.11999/JEIT161266
-
1.
(合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 合肥 230009) ②(科學(xué)技術(shù)部基礎(chǔ)研究管理中心 北京 100862) ③(路易斯安那州立大學(xué)計(jì)算機(jī)與信息學(xué)院 拉斐特 70503 美國(guó))
基金項(xiàng)目:
國(guó)家973規(guī)劃項(xiàng)目(2013CB329604)，國(guó)家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFB1000901)，國(guó)家自然科學(xué)基金項(xiàng)目(61503114)
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)
-
摘要: 隨著社交網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，網(wǎng)絡(luò)節(jié)點(diǎn)的標(biāo)簽分類也不再單一，變得豐富多樣，這些促使了社交網(wǎng)絡(luò)中的多標(biāo)簽分類問題成為一個(gè)重要的研究領(lǐng)域。以前的研究重點(diǎn)主要集中在提高預(yù)測(cè)網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)簽的精度上，而忽略了得到節(jié)點(diǎn)信息所產(chǎn)生的包含時(shí)間消耗和計(jì)算資源等在內(nèi)的系統(tǒng)開銷問題?？涩F(xiàn)如今隨著網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大且復(fù)雜性不斷增強(qiáng)，之前所忽略的系統(tǒng)開銷問題變得越來越嚴(yán)重，增加了預(yù)測(cè)標(biāo)簽的成本，加重了預(yù)測(cè)網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)簽的難度。該文針對(duì)這一問題提出了基于NSGA2算法的網(wǎng)絡(luò)環(huán)境下多標(biāo)簽種子節(jié)點(diǎn)選擇算法(NAMESEA算法)，目的是在能大大降低預(yù)測(cè)節(jié)點(diǎn)標(biāo)簽所消耗的系統(tǒng)開銷的前提下一定程度上提高預(yù)測(cè)標(biāo)簽的精度。該文將NAMESEA算法與其他多標(biāo)簽預(yù)測(cè)算法在多個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果證明NAMESEA算法大大降低了預(yù)測(cè)節(jié)點(diǎn)標(biāo)簽的系統(tǒng)開銷并且提高了預(yù)測(cè)精度。
-
關(guān)鍵詞:
- 社交網(wǎng)絡(luò) /
- 多標(biāo)簽分類 /
- NSGA2 /
- 系統(tǒng)開銷
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-
Key words:
- Social networks /
- Multi-label classification /
- NSGA2 /
- System overhead
-
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. 吳信東, 趙銀鳳, 李磊. 基于種子節(jié)點(diǎn)選擇的網(wǎng)絡(luò)環(huán)境下多標(biāo)簽分類算法研究[J]. 電子學(xué)報(bào), 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. 許宇光, 潘驚治, 謝惠揚(yáng). 基于最小點(diǎn)覆蓋和反饋點(diǎn)集的社交網(wǎng)絡(luò)影響最大化算法[J]. 電子與信息學(xué)報(bào), 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. 陳季夢(mèng), 陳佳俊, 劉杰, 等. 基于結(jié)構(gòu)相似度的大規(guī)模社交網(wǎng)絡(luò)聚類算法[J]. 電子與信息學(xué)報(bào), 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. 劉世超, 朱福喜, 甘琳. 基于標(biāo)簽傳播概率的重疊社區(qū)發(fā)現(xiàn)算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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. 邢千里, 劉列, 劉奕群, 等. 微博中用戶標(biāo)簽的研究[J]. 軟件學(xué)報(bào), 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. 申超波, 王志海, 孫艷歌.基于標(biāo)簽聚類的多標(biāo)簽分類算法[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ī)游走模型的多標(biāo)簽分類算法[J]. 計(jì)算機(jī)學(xué)報(bào), 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. 張振海, 李士寧, 李志剛, 等. 一類基于信息熵的多標(biāo)簽特征選擇算法[J]. 計(jì)算機(jī)研究與發(fā)展, 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ī)多目標(biāo)調(diào)度問題研究[J]. 物聯(lián)網(wǎng)技術(shù), 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. 孫建龍, 吳鎖平, 陳燕超. 基于改進(jìn)NSGA2算法的配電網(wǎng)分布式電源優(yōu)化配置[J]. 電力建設(shè), 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算法及其在電力系統(tǒng)穩(wěn)定器參數(shù)優(yōu)化中的應(yīng)用[D]. [碩士論文], 西南交通大學(xué), 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. -
計(jì)量
- 文章訪問數(shù): 1353
- HTML全文瀏覽量: 135
- PDF下載量: 346
- 被引次數(shù): 0
下載:
