差分化节点特征对复杂网络链接预测的分类性能分析

J4 ›› 2015, Vol. 37 ›› Issue (01): 173-178.

差分化节点特征对复杂网络链接预测的分类性能分析

伍杰华1，2，朱岸青1，3 ，蔡雪莲1，张小兰1

(1.广东工贸职业技术学院计算机工程系,广东广州 510510;2.华南理工大学信息科学与技术学院,广东广州 510641;
3.暨南大学信息科学与技术学院,广东广州 510632)

收稿日期:2013-04-15 修回日期:2013-08-07 出版日期:2015-01-25 发布日期:2015-01-25
基金资助:
国家自然科学基金资助项目（61003045）；广东省教育部产学研结合项目（2012B091100043）

Classification performance analysis on link prediction
via diverse node features in complex network

WU Jiehua1，2，ZHU Anqing1，3 ，CAI Xuelian1，ZHANG Xiaolan1

(1.Department of Computer Science and Engineering,Guangdong College of Industry and Commerce,Guangzhou 510510;
2.College of Information Science and Technology,South China University of Technology University,Guangzhou 510641;
3.College of Information Science and Technology,Jinan University,Guangzhou 510632,China)

Received:2013-04-15 Revised:2013-08-07 Online:2015-01-25 Published:2015-01-25

摘要/Abstract

摘要：

链接预测属于复杂网络分析的研究分支，它根据网络历史结构信息预测未来节点间会产生链接的可能性，从而挖掘网络的传播和演化方式。通过引入差分化节点的贡献权重并结合经典的节点和共邻节点网络拓扑结构特征，分别应用七类有监督学习分类模型对社交、生物、交通等不同领域的八个真实复杂网络数据集进行实验，并采用Precision和ROC曲线对实验结果进行分析与评价。实验表明，引入基于差分化节点的贡献特征能够在深入挖掘网络结构信息的基础上比其余特征有更优的预测精确度，同时差异化的分类模型和特征选择对链接预测性能有相异的影响。

关键词: 链接预测, 复杂网络, 特征选择, 分类, 共邻节点

Abstract:

Link prediction is a branch of complex network analysis. It predicts future linkage between nodes according to historical network structure information in order to reveal the network evolution and diffusion. This paper introduces a novel feature based on differentiated node contribution and provides seven supervised learning frameworks to carry the classification task via our introduced features and two categories of classic topological features which include node information and common neighbors’ property. The experimental results on eight realworld networks demonstrate interesting finding on the prediction influence by different classification models and topological diverse features via precision and ROC curve. In addition, we prove that our newly introduced features outperform the classic ones, which can mine the latent network information and enhance accuracy of link prediction.

Key words: link prediction;complex network;feature selection;classification;common neighbors

伍杰华1，2，朱岸青1，3 ，蔡雪莲1，张小兰1. 差分化节点特征对复杂网络链接预测的分类性能分析[J]. J4, 2015, 37(01): 173-178.

WU Jiehua1，2，ZHU Anqing1，3 ，CAI Xuelian1，ZHANG Xiaolan1. Classification performance analysis on link prediction
via diverse node features in complex network [J]. J4, 2015, 37(01): 173-178.

参考文献

［1］Samuel L.Social networks:A developing paradigm［M］. New York:Academic Press, 1977.
［2］Wasserman S,Faust K.Social network analysis:Methods and applications［M］. Cambridge:Cambridge University Press, 1994.
［3］Leskovec J,Huttenlocher D,Kleinberg J.Predicting positive and negative links in online social networks［C］∥Proc of the 19th International Conference on World Wide Web, 2010:641650.
［4］LibenNowell D,Kleinberg J.The link prediction problem for social networks［J］. Journal of the American Society for Information Science and Technology, 2007, 58(7):10191031.
［5］Al Hasan M, Chaoji V, Salem S, et al. Link prediction using supervised learning［C］∥Proc of Workshop on Link Analysis, Counterterrorism and Security,2006:1.
［6］Donghyuk S, Si Si, Dhillon I S. Multiscale link prediction［EB/OL］.［20120408］.http:arxiv.org/abs/1206.1891.
［7］ValverdeRebaza J C,de Andrade Lopes A.Link prediction in complex networksbased on cluster information［C］∥Proc of SBIA’12, 2012:92101.
［8］Popescul A,Ungar L H.Statistical relational learning for link prediction［C］∥Proc of IJCAI Workshop on Learning Statistical Models from Relational Data, 2003:1.
［9］Miller K, Griffiths T, Jordan M. Nonparametric latent feature models for link prediction［C］∥Proc of Advances in Neural Information Processing Systems, 2009:12761284.
［10］Zhu J. Maxmargin nonparametric latent feature models for link prediction［EB/OL］.［20121210］.http:arxiv.rog/abs/1206.4659.
［11］Cao B, Liu N N, Yang Q. Transfer learning for collective link prediction in multiple heterogenous domains［C］∥Proc of the 27th International Conference on Machine Learning,2010:159166.
［12］Liu Z, Zhang Q M, Lü L,et al. Link prediction in complex networks:A local nave Bayes model［J］. EPL (Europhysics Letters), 2011,96(4):48007.
［13］Barabási A L,Réka A.Emergence of scaling in random networks［J］. Science, 1999,286:509512.
［14］Feng X, Zhao J C, Xu K. Link prediction in complex networks:A clustering perspective［J］. The European Physical Journal B, 2012, 85(1):19.
［15］http://www.levmuchnik.

[1]	柴燕涛，董德尊，张鹤颖，朱成阳，廖湘科. 基于SDN架构的高性能网络拥塞避免策略[J]. J4, 20160101, 38(01): 1-10.
[2]	谷文俊, 张晟恺, 邱晓梦, 李亚康, 宋伟. 基于双模态的小角散射图像结构表征技术研究[J]. 计算机工程与科学, 2023, 45(08): 1443-1452.
[3]	赵瑞平, 降爱莲. 基于自编码器和局部嵌入的无监督特征选择[J]. 计算机工程与科学, 2023, 45(07): 1282-1291.
[4]	梁毅, 吐尔地·托合提, 艾斯卡尔·艾木都拉, . 多层CNN特征融合及多分类器混合预测的多模态虚假信息检测#br#[J]. 计算机工程与科学, 2023, 45(06): 1087-1096.
[5]	许浪, 李代伟, 张海清, 唐聃, 何磊, 于曦. 基于神经网络的医疗文本分类研究[J]. 计算机工程与科学, 2023, 45(06): 1116-1122.
[6]	梅侠峰, 吴晓鸰, 黄泽民, 凌捷. 融合RoBERTa的多尺度语义协同专利文本分类模型[J]. 计算机工程与科学, 2023, 45(05): 903-910.
[7]	胡慧君, 杨雨烟, 易洋, 刘茂福. 基于细粒度信息感知BERT-EEP的情绪分类方法[J]. 计算机工程与科学, 2023, 45(04): 751-760.
[8]	赵亚丽, 余正涛, 郭军军, 高盛祥, 相艳, . 基于情感语义对抗的跨语言情感分类模型[J]. 计算机工程与科学, 2023, 45(02): 338-345.
[9]	顾楚梅, 曹建军, 王保卫, 徐雨芯, . 基于蚁群参数优化的LightGBM辐射源个体识别[J]. 计算机工程与科学, 2023, 45(01): 85-94.
[10]	张睿萍, 宁芊, 雷印杰, 陈炳才. 基于改进Mask R-CNN的生活垃圾检测[J]. 计算机工程与科学, 2022, 44(11): 2003-2009.
[11]	胡艳芳, 熊文, 高炜. 基于 Spark 平台的网络游戏用户流失预测方法[J]. 计算机工程与科学, 2022, 44(10): 1730-1737.
[12]	文武, 万玉辉, 文志云, . 基于正余弦算法的文本特征选择[J]. 计算机工程与科学, 2022, 44(08): 1467-1473.
[13]	庞兴龙, 朱国胜, 杨少龙, 李修远. 一种基于聚类与噪声的网络流量分类方法[J]. 计算机工程与科学, 2022, 44(07): 1207-1215.
[14]	吴亦奇, 韩放, 张德军, 何发智, 陈壹林. 基于特征通道和空间位置注意力的三维点云特征学习网络[J]. 计算机工程与科学, 2022, 44(07): 1239-1246.
[15]	王栋, 杨珂, 玄佳兴, 韩雨桐, 赵丽花, 王旭仁. 基于半监督生成对抗网络的恶意代码家族分类实现[J]. 计算机工程与科学, 2022, 44(05): 826-833.