计算机科学 ›› 2020, Vol. 47 ›› Issue (4): 233-237.doi: 10.11896/jsjkx.190600151

• 计算机网络 • 上一篇    下一篇

有向加权网络中的改进SDNE算法

马扬, 程光权, 梁星星, 李妍, 杨雨灵, 刘忠   

  1. 国防科技大学系统工程学院 长沙410073
  • 收稿日期:2019-06-26 出版日期:2020-04-15 发布日期:2020-04-15
  • 通讯作者: 程光权(yang_ma_cn@163.com)
  • 基金资助:
    国家自然科学基金(61201328,71471175)

Improved SDNE in Weighted Directed Network

MA Yang, CHENG Guang-quan, LIANG Xing-xing, LI Yan, YANG Yu-ling, LIU Zhong   

  1. College of Systems Engineering,National University of Defense Technology,Changsha 410073,China
  • Received:2019-06-26 Online:2020-04-15 Published:2020-04-15
  • Contact: CHENG Guang-quan,born in 1982,Ph.D,is a member of China Computer Federation (CCF).His main research interests include network analysis and machine learning.
  • About author:MA Yang,born in 1993,postgraduate.His main research interests include link prediction and graph neural networks.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China (61201328,71471175).

摘要: 网络化的数据形式能够表示实体以及实体和实体之间的联系,网络结构在现实世界中普遍存在。研究网络中节点和边的关系具有重要意义。网络表示技术将网络的结构信息转换为节点向量,能够降低图表示的复杂度,同时能够有效运用到分类、网络重构和链路预测等任务中,具有很广泛的应用前景。近年提出的SDNE(Structural Deep Network Embedding)算法在图自编码领域取得了突出成果,文中针对网络表示算法SDNE在有权、有向网络中的局限性,从网络结构和衡量指标两个角度入手,提出了新的基于图自编码的网络表示模型,在原有节点向量的基础上引入了接收向量和发出向量的概念,优化了自编码器的解码部分,进而优化了神经网络的结构,减少了网络的参数以加快收敛速度;提出了基于节点度的衡量指标,将网络的加权特性反映在网络表示的结果中。在3个有向加权数据集中的实验证明,在进行网络重构和链路预测任务时,所提方法能够取得比传统方法和SDNE原始方法更好的结果。

关键词: 复杂网络, 网络表示, 网络重构, 链路预测, 自编码

Abstract: The data form of network can express the entity and the relation between entity and entity.Network structure is common in the real world.It is great significance to study the relationship between nodes and edges in networks.Network representation technology transforms the structure information of network into node vector,which can reduce the complexity of graph representation,and can be effectively applied to tasks such as classification,network reconstruction and link prediction.The SDNE (structural deep network embedding) algorithm proposed in recent years has made outstanding achievements in the field of graph auto-encoder.In view of the limitations of SDNE in weighted and directed networks,this paper proposed a new network representation model based on graph auto-encoder from the perspectives of network structure and measurement index.The concepts of receiving and sending vector are introduced to optimize the decoding part of the neural network,which reduce the para-meters of the network to speed up the convergence speed.This paper proposed a measurement index based on the node degree,and reflected the weighted characteristics of the network in the results of the network representation.Experiments on three directed weighted datasets show that the proposed method can achieve better results than the traditional method and the original SDNE method in network reconstruction and link prediction tasks.

Key words: Complex network, Network representation, Network reconstruction, Link prediction, Auto-encoder

中图分类号: 

  • TP311
[1]LV L Y.Link Prediction on Complex Networks[J].Journal of University of Electronic Science and Technology of China,2010,39(5):651-661.
[2]LV L,ZHOU T.Link prediction in complex networks:A survey[J].Physica A Statistical Mechanics & Its Applications,2010,390(6):1150-1170.
[3]MA Y,LIANG X,HUANG J,et al.Intercity TransportationConstruction Based on Link Prediction[C]//2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI).IEEE,2017.
[4]KLIMT B.The Enron corpus:A new dataset for email classification research[C]//Proc.15th European Conf.MachineLear-ning.2004.
[5]TU C C,YANG C,LIU Z Y,et al.Network representationlearning:an overview[J].Scientia Sinical Informationis,2017(8):32-48.
[6]HAMILTON W L,YING R,LESKOVEC J.RepresentationLearning on Graphs:Methods and Applications[J].arxiv:1709.05584.
[7]GOYAL P,FERRARA E.Graph Embedding Techniques,Applications,and Performance:A Survey[J].arXiv:1705.02801.
[8]BELKIN M.Laplacian eigenmaps and spectral techniques forembedding and clustering[J].Advances in neural information processing systems,2002,14(6):585-591.
[9]ADITYA GROVER J L.node2vec:Scalable Feature Learningfor Networks[J].arXiv:1607.00653.
[10]GOLDBERG Y.A Primer on Neural Network Models for Natural Language Processing[J].arXiv:1510.00726,2015.
[11]WANG D,PENG C,ZHU W.Structural Deep Network Embedding[C]//Acm Sigkdd International Conference on Knowledge Discovery & Data Mining.2016.
[12]SAMI A,PEROZZI B,AL-RFOU R.Learning Edge Representations via Low-Rank Asymmetric Projections[C]//Proceedings of the 2017 ACM on Conference on Information and Knowledge Management-(CIKM 17).2017:1787-1796.
[13]GOYAL P,KAMRA N,HE X,et al.DynGEM:Deep Embedding Method for Dynamic Graphs[J].arXiv:1805.11273.
[14]SUTSKEVER I,VINYALS O,LE Q V.Sequence to Sequence Learning with Neural Networks[J].arXiv:1511.04868.
[15]KIM J,PARK H,LEE J E,et al.SIDE:Representation Learning in Signed Directed Networks[C]//the 2018 World Wide Web Conference.2018.
[16]CHEN H,PEROZZI B,AL-RFOU R,et al.A Tutorial on Network Embeddings[J].arXiv:1808.02590.
[17]CUNCHAO T,XIANGKAI Z,HAO W,et al.A Unified Framework for Community Detection and Network Representation Learning[J].IEEE Transactions on Knowledge and Data Engineering,2019,31(6):1051-1065.
[18]GOYAL P,HOSSEINMARDI H,FERRARA E,et al.Capturing Edge Attributes via Network Embedding[J].IEEE Tran-sactions on Computational Social Systems,2018,5(4):907-917.
[1] 丁钰, 魏浩, 潘志松, 刘鑫. 网络表示学习算法综述[J]. 计算机科学, 2020, 47(9): 52-59.
[2] 杨超, 刘志. 基于TASEP模型的复杂网络级联故障研究[J]. 计算机科学, 2020, 47(9): 265-269.
[3] 张梦月, 胡军, 严冠, 李慧嘉. 基于可见性图网络的中国专利申请关注度分析[J]. 计算机科学, 2020, 47(8): 189-194.
[4] 张清琪, 刘漫丹. 复杂网络社区发现的多目标五行环优化算法[J]. 计算机科学, 2020, 47(8): 284-290.
[5] 王慧, 乐孜纯, 龚轩, 武玉坤, 左浩. 基于特征分类的链路预测方法综述[J]. 计算机科学, 2020, 47(8): 302-312.
[6] 蒋宗礼, 李苗苗, 张津丽. 基于融合元路径图卷积的异质网络表示学习[J]. 计算机科学, 2020, 47(7): 231-235.
[7] 黄易, 申国伟, 赵文波, 郭春. 一种基于漏洞威胁模式的网络表示学习算法[J]. 计算机科学, 2020, 47(7): 292-298.
[8] 董明刚, 弓佳明, 敬超. 基于谱聚类的多目标进化社区发现算法研究[J]. 计算机科学, 2020, 47(6A): 461-466.
[9] 富坤, 仇倩, 赵晓梦, 高金辉. 基于节点演化分阶段优化的事件检测方法[J]. 计算机科学, 2020, 47(5): 96-102.
[10] 汪航, 陈晓, 田晟兆, 陈端兵. 基于小样本学习的SAR图像识别[J]. 计算机科学, 2020, 47(5): 124-128.
[11] 袁榕, 宋玉蓉, 孟繁荣. 一种基于加权网络拓扑权重的链路预测方法[J]. 计算机科学, 2020, 47(5): 265-270.
[12] 李刚, 王超, 韩德鹏, 刘强伟, 李莹. 基于深度主成分相关自编码器的多模态影像遗传数据研究[J]. 计算机科学, 2020, 47(4): 60-66.
[13] 李鑫超, 李培峰, 朱巧明. 一种基于改进向量投影距离的知识图谱表示方法[J]. 计算机科学, 2020, 47(4): 189-193.
[14] 孙志强, 万良, 丁红卫. 基于深度自编码网络的Android恶意软件检测方法[J]. 计算机科学, 2020, 47(4): 298-304.
[15] 罗月,童卞,景帅,张蒙,饶永明,闫峰. 基于卷积去噪自编码器的芯片表面弱缺陷检测方法[J]. 计算机科学, 2020, 47(2): 118-125.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .