基于网络嵌入与转移相似性的链路预测研究

发布时间：2020-07-12 04:33

【摘要】：随着信息技术的飞速发展,复杂系统的大量涌现,网络科学作为一门新生学科也得到了快速发展。链路预测作为该领域中的一个重要课题,可以根据已有网络拓扑结构等信息,来发现网络中存在但未知的连边和预测不存在但将来可能形成的连边。链路预测在实践中,可以在社交网络中用来推荐好友、在基因调控中用来发现未知的调控关系;在理论上,则有助于揭示网络的内部结构特征,促进对复杂系统演化机制的理解。目前的链路预测算法主要是根据节点属性或者网络拓扑结构来预测连边,前者在实践中存在节点属性信息难以获取、质量难以保证等问题,而后者仅需知道网络的拓扑结构,但也存在预测精度不高的问题。本文研究属于后者,即仅根据网络拓扑结构来进行链路预测。本文首先在高阶近邻保持嵌入(High Order Proximity preserved Embedding,HOPE)算法的基础上,提出了一种邻接嵌入(Adjacency Embedding,AE)算法,将网络中的节点用低维、实值、稠密的向量进行表征,通过在低维空间中计算这些表征向量之间的距离来推断节点的相似性,从而预测其间产生连边的可能性。通过对10个真实网络上的实验分析可以得出,相对于HOPE算法,AE算法在保证预测精度的同时,减小了时间复杂度。其次,基于节点之间相似性应当可以传递的思想,本文提出基于AE算法的转移相似性(Transferring Similarity Based on Adjacency Embedding,TSBAE)算法,结合各节点之间的潜在网络结构相似性,克服了 HOPE算法以及AE算法中由于数据稀疏性导致的相距较远的节点之间相似性预测不准确的问题。结果表明,无论是在无向网络上,还是在有向网络上,TSBAE算法都比基准算法、AE算法预测精度高。
【学位授予单位】：湖南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：

无向图,示意图,网络表示,加权图

络结构的研究。本章将会介绍复杂网络的网络表示、链路预测问题、复杂网络逡逑拓扑性质、评价指标以及本文实验部分用作对比分析的基准算法。逡逑．１网络表示逡逑根据连边是否有权重，可以将图分为加权图和无权图。在加权图中，每一条逡逑都有一个权值，而无权图的连边不存在权值。本文进行链路预测时，只考虑无逡逑网络。根据连边是否有方向，可以将图分为有向图和无向图。逡逑在无向无权网络中，网络可以由表示，其中ｒ为节点集，￡为连边逡逑，其五ＧＧＦ）。节点对（0和节点对表示同一条连边，连边是逡逑有方向的，边数Ｍ的最大取值是７Ｖ（ＡＭ）／２。简单无权无向网络满足以下条件：逡逑（１）节点自己和自己不能连接，即网络中不存在如的边；逡逑（２邋）任意两个节点之间最多只能有一条连边；逡逑（３）任意两个节点之间的连边没有方向性，即当时，五；逡逑（４）连边之间没有权重的概念，只代表节点之间关系的存在性。逡逑

节点,示例,相似性,实线

逦（２．２）逡逑：ｅ（ｒ（．ｒ）0ｒ（＞＊））邋１0§欠：逡逑式中ｒ（ｘ）、ｒ00分别表示节点Ｘ和的邻居的集合，应用ａ邋ａ方法计算相似性的时逡逑候，需要考虑共同邻居的度的影响，网络中节点Ｚ的度为屹。如图２．３得到节点１逡逑的度为３，节点３的度为４，因此可以得到节点２和节点５的相似性为：逡逑_灒担剑保▆0口３）＋１／（／叹４户３．７５６。同理，考虑节点４和节点５的ＡＡ相似性时，也需逡逑要考虑其共同邻居节点３的度，因此可以得呀口３户２．０９６。由此可得，逡逑根据ＡＡ相似性的预测方法，节点２和节点５之间产生连接的可能性大于节点４逡逑和节点５之间产生连接的可能性。逡逑１０逡逑

算法,相似性,有向图,源向量

＜ｗ邋＾逡逑图３．２邋ＨＯＰＥ算法示例图逡逑图３．２是ＨＯＰＥ算法学习有向图示例，左边是－个有向图，右边是左图的嵌入逡逑向量空间。在左边的有向图中，实线农示观察到的有向边，虚线丨：的数字足Ｋａｔｚ逡逑相似性值。例如，根据非对称的传递性，对Ｖ；—１（１两条路轻，图逡逑中可能存在连ａｖ，—％。根据公式（３．３），计算ｖｊｌｊｖ＾Ｋａｔｚ相似性，即０．０２，邋ｖ＃ｊｖ，Ｊ逡逑Ｋａｔｚ相似性为０．０１。另一方面，因为ｖ６—ｖ，在相反的方向，从ｖ，ｖ＃ｊＫａｔｚ相似性很逡逑小，即０。在嵌入空间中，箭头表不顶点的嵌入向量，其中向量Ｗ和ｗ丨分别表不ｖ，？的逡逑源向量和目标向量。用邋＜和《；之间的内积（也就是0〃）作为从ｖ，．到．的近似距离，其逡逑２１逡逑

【相似文献】