一种基于相对熵的随机游走相似性度量模型

针对基于随机游走的节点相似性度量模型中存在的大度节点依赖问题,从信息论的角度提出了一种改进的随机游走节点相似性度量方法:基于相对熵的随机游走相似性度量方法RE-model(A random walk similarity measure model based on Relative Entropy).首先根据随机游走模型得到网络中节点的转移概率向量,再计算两个节点转移概率向量的相对熵得到该节点对的相似性.由于转移概率向量给出了从一个特定节点出发经过多步随机游走后到达网络其他所有节点的概率,导致网络中的每个节点在计算相对熵的过程中都被等同看待,并且网络规模的增大会使计算得到的节点间相似性耗时更多且存在较大偏差.根据节点经过多步随机游走后到达网络中影响力较大的节点的转移概率来构造该节点的转移概率分布,计算两个节点的转移概率分布的相对熵以得到网络中节点对之间的差异分数,进而得到网络节点间的相似性矩阵. RE-model度量方法降低了传统随机游走相似性度量对于大度节点的依赖性.通过在真实网络数据集上的实验表明,RE-model算法在对称性、网络传播及社区发现等方面表现良好.     

符号网络中融合聚集系数与符号影响力的链路预测算法

为快速、准确地实现符号社会网络中的链接预测与符号预测双重目标，提出一种融合共同邻居节点的聚集系数与连边符号影响力的链路预测算法。基于结构平衡理论，有效利用节点的度、聚集系数、路径上的中间传输节点、连边符号及其影响力等信息，分别定义了两节点基于一阶共同邻居和二阶共同邻居的相似性，最终得到两节点的总相似性得分，用其绝对值度量两节点建立链接的可能性，通过其符号获得链接的符号预测结果，从而实现符号网络中的链路预测。在6个有代表性的符号网络数据集上进行了实验，以AUC、调整的Precision’、Accuracy等为评价指标，对比了多个符号网络链接预测算法，并进行了可调步长参数的敏感性分析。实验结果表明，所提算法在符号网络链接预测与符号预测两方面均达到了较好的性能，无论是稀疏网络还是负链接预测，准确性均高于其他算法。     

基于离散时间量子漫步的链路预测算法

量子漫步算法能模拟游走粒子在图上的量子相干演化,粒子的运动状态由量子态的相干叠加而成.与经典随机游走算法相比,量子漫步算法具有寻找目标节点时间少和源节点扩散至其他节点时间少的优点.提出一种基于离散时间量子漫步的链路预测(link predictionbased on discrete time quantum walk,简称LP-DTQW)算法.研究结果表明：相对于其他7种算法,LP-DTQW算法有更高的预测精度;LP-DTQW算法的时间复杂度远低于经典RWR(random walk with restart)链路预测算法的时间复杂度.因此,LP-DTQW算法具有更强的预测性能.     

时态网络节点相似性度量及链路预测算法

详细分析和阐述了时态网络中的链路预测问题，将时态网络按时间顺序划分为具有相同时间间隔的多层网络快照序列.针对基于共同邻居的相似性指标对网络链路刻画粒度较粗糙的问题，提出了基于邻居节点聚类系数的相似性度量指标NCC和NCCP，并基于此提出时态网络链路预测算法.通过在真实数据集上的对比实验验证了利用邻居节点的聚类信息可以提高预测精度.利用真实邮件数据集验证了所提出的链路预测算法预测效果的优越性，并且实验结果证明越接近预测时间的网络结构对预测结果影响越大.     

基于图注意力和特征融合的链路预测方法

链路预测是一种还原网络缺失信息的方法，通过当前已观察到的链路，预测实际存在但未被观察到的链路或可能出现的新链路.当前链路预测主要是基于图神经网络的深度学习方法，相比基于规则的启发式方法，前者可有效利用网络拓扑结构信息，较大地提升了网络链路预测性能，并可应用到类型更广泛的网络中.但是现有基于图神经网络的方法，仅利用网络中节点相对位置信息，忽视了节点基本属性和链路的邻居信息，且无法区分不同节点对链路形成的重要程度.为此，本文提出一种基于图注意力网络和特征融合的链路预测方法.通过增加节点的度、链路的共同邻居数量和共同邻居最大度等特征，丰富了网络的输入特征信息.本文首先提取以目标节点对为中心的子图，然后将其转化为对应的线图，线图中的节点和原图中的链路一一对应，从而将原图节点和链路信息融合到线图的节点中，提升了特征融合的有效性和可解释性.同时本文使用图注意力机制学习节点的权重，增强了特征融合的灵活性.实验表明，本文所提出的方法，在多个不同领域数据集上的AUC和AP均超过90%,在已观测链路缺失较多时，预测性能保持80%以上，且均优于现有最新方法.     

融合多因素的多实体政策网络链路预测算法

政策文本为社会的发展提供了权威性和原则性的方向和指导,但由于政策文本间关系错综复杂、政策实体间潜在连接关系隐性等,导致政策信息准确获取困难、理解不全面等.针对上述特点以及现有研究大多集中于单一类型政策实体及关系分析,难以全面准确地刻画政策间多类实体潜在关系的不足,提出了一种融合节点相似和属性偏好的多实体政策网络链路预测算法LP-NA.LP-NA综合考虑了节点之间的相似性、节点属性偏好对预测概率的贡献和预测偏差对链接预测的影响,采用反映局部信息的链接聚类系数和全局信息的接近中心性计算节点相似度,构建原始权重矩阵,并将政策网络的节点属性偏好和预测偏离值加入矩阵分解框架中,对网络中已知连边信息进行综合计算,提升了实体间链路预测精度.在7个真实多实体政策网络数据集上的实验结果表明：与现有算法相比,提出的LP-NA算法将AUC最大分别提升了4.76%、4.20%、2.81%、3.08%、3.25%、4.59%、3.03%.     

基于热传导的随机游走链路预测算法的分析与研究

通过观察现有链路预测算法在社交网络推荐系统中的表现,我们发现一些预测算法不能很好的满足特定网络的需求.受现有链路预测算法的启发,本文提出了一种基于热传导的随机游走链路预测算法,算法中加入了基础节点,使得算法效率更高.实验结果表明,基于热传导的随机游走链路预测算法在社交网络推荐系统中的表现优于基于节点相似性的链路预测算法.     

基于聚类系数和节点中心性的链路预测算法

目前复杂网络领域受到越来越多人的广泛关注.其中链路预测是复杂网络研究中的一个热门的分支,被作为预测缺失链路和识别虚假链路的有效手段.传统基于相似性的复杂网络链路预测主要考虑每个节点的某个相似性指标,而该文提出一种基于聚类系数和节点中心性(CCNC)的链路预测算法,将度、聚类系数和节点中心性3个相似度指标结合,引入到复杂...     

基于改进TADW的链路预测算法

针对经典的节点相似性链路预测算法只考虑网络拓扑结构或者节点属性信息的问题,使用词嵌入模型Word2vec学习得到节点文本属性信息的表示,进而改进TADW(text-associated deep walk)算法,弥补其语义信息表示能力的不足.基于改进的TADW图嵌入方法提出一种融合网络拓扑结构和节点属性信息的相似性指标,并基于此相似性指标提出链路预测算法.在三个真实数据集上的实验结果表明所提出算法可以提高预测精度,并具有更好的鲁棒性,同时使用图嵌入的方法有效解决了网络数据的稀疏性问题.     

基于用户相似度的随机游走社交网络事件推荐算法

针对基于社交网络的事件推荐覆盖性和准确性不够高的问题,提出了基于用户相似度Si-user Walker算法.该算法利用基于事件的社交网络特征,将线上用户群组数据抽象为图,以重启随机游走算法为基础,改变了传统的完全基于图的拓扑结构进行随机游走的策略.根据地理位置划分事件类型,提出了新的用户相似度计算方法,然后根据用户相似度矩阵作为随机游走的转移概率,既保留了图的传递性,又保证了图节点游走的真实性.与其他推荐算法在真实的数据集上实验表明,该算法在均方根误差、准确率及覆盖率上均得到提升.     

基于近邻模型与概率矩阵分解的高校选课推荐算法

为研究高校教务信息管理系统中学生自主在线选课的个性化推荐问题,采用基于近邻模型与概率矩阵分解相融合的改进算法.通过衡量学生(选课)之间的相似关系寻找相似学生(选课),再将与学生(选课)相似性最大的邻居集合应用到基于概率矩阵分解的协同过滤推荐算法中,最终依据预测评分值和限制条件给出Top-K推荐结果排序.原型系统测试实验结果表明:改进算法更适用于高校选课推荐应用,并能够有效地解决数据稀疏问题.     

一种改进的代价敏感型链路预测算法

为解决因网络数据分布不均匀性而造成的链路预测问题,提出一种改进的代价敏感型链路预测算法(Link Boost).设计一种有监督链路预测可变代价损失函数,该函数对低节点度有链路节点对出现分类错误时的惩罚大于高节点度有链路节点对,解决了节点度的分布偏差.考虑到以损失函数优化为目标的链路预测算法将导致社区内预测链路数量大于社区间的链路数量,进而设计一种Boosting算法来实现损失函数最小化.通过将网络分为多个分区,并对各个分区构建的弱学习器进行融合,提高了算法的可伸缩性.利用4个真实网络数据集进行性能评估.研究结果表明:Link Boost算法的性能与许多当前算法的性能相当或者优于当前算法.     

基于图嵌入法的时序网络链路预测研究

时序网络因为其复杂的动态结构和非线性拓扑特征,一直都是复杂网络和链路预测研究的重点.因为网络结构会动态变化从而导致常用的基于静态网络的方法不再高效适用.本文基于图嵌入方法,提出了一种适用于时序网络的链路预测算法,其核心是改进链路预测中粒子的随机游走过程,使其基于网络结构特征进行有偏向转移.其次,考虑到时序网络中历史信息的影响,在有偏向转移的基础上定义一种粒子的全局转移概率,这种转移概率重点计算最近时刻的信息同时也会考虑历史信息.经过实验例证,本文提出的方法较传统基准指标有较大的提升.     

基于综合游走策略的边嵌入链路预测算法

针对网络分析方法中研究的图数据默认使用节点图,只能得到节点的向量表示,不能直接将边表示成向量的问题,设计了一种基于有偏+无偏的图嵌入算法Line2Vec,并在此基础上提出基于边嵌入的链路预测框架(Line2Vec-L).首先,基于综合游走策略重新定义采样域节点的采样概率,并结合Word2Vec模型得到信息未被稀释、表示性强的节点图的边嵌入向量;然后,结合关联矩阵得到不存在边或未知边的向量表示,并将得到的边向量用于链路预测.实验结果表明Line2Vec在边向量表示上的有效性,并验证了Line2Vec-L的AUC值更高,由此说明采用Line2Vec可得到表示性更强的边向量,有助于提升链路预测的性能.     

异质网络中融合多类信息的链路情感倾向预测

信息网络中基于节点间情感关系分析的链路情感倾向预测在商业营销、内容推荐等领域应用广泛，是网络分析的一个研究重点.传统的链路情感倾向预测方法对于数据信息的挖掘不够充分，忽略了对数据深层语义以及节点属性等信息的利用，预测准确度有待提升.针对以上问题，提出了异质网络中融合多种类型信息的链路情感倾向预测模型.模型首先引入预测基值作为特定节点间情感关系的粗略评估，然后结合节点的相似关系以及节点的属性等信息完成预测.其中，在捕获网络中具有相似情感倾向的节点用于预测任务时，提出了一种基于限制路径类型元路径的遍历游走方法.在5个公共数据集上的实验结果验证了所提模型的有效性及对于稀疏矩阵、冷启动问题的处理能力，并揭示了模型各组成部分在预测过程中的作用.     

利用链路预测推断网络演化机制

直接建立演化模型推测影响网络演化的因素是目前研究网络演化制的常用方法,但由于可供比较的结构特征量太多,不同的模型之间难以进行定量化的比较.链路预测是指利用网络的结构或者节点的属性息预测未产生连接的两个节点间产生连接的可能性.其本质是挖掘网络产生连边的原因和驱动力,这同时也是网络演化模型所关的问.实际上,一个演化模型原则上都可以对应于一种链路预测的算法.因此,助链路预测的理论框和评方法可以定量化地对不同演化模型所对应的链路预测算法进行评,从而间接地对演化模型的表现进行定量比较.本文首先绍于节点接近性的链路预测方法,然后讨论利用链路预测推测网络演化制的本框.在以中城市航空网络为例的实证分析中发现,当单独利用结构(共同邻居数目)和节点属性(地理位、人口、GDP和第三产业产值)作为定义接近性的因素时,于共同邻居的算法预测准确度最高,暗示网络演化主要受结构因素影响,其次才是外在因素.而将四种于节点属性的算法与于结构的算法耦合进行计算时,共同邻居配合第三产业产值效最好,与偏相关分析和因分析的结论一.本文为研究网络演化模型供了全新的视角和分析工具.     

MWSN中基于马尔可夫链的节点移动预测算法

在以往的移动无线传感器网络(mobile wireless sensor network,MWSN)中,热点分配问题没有得到很好的解决,网络利用率较低.通过预测移动节点的轨迹可以优化网络结构,提出结合加速度进行轨迹预测的算法MTPA:首先对节点的运动状态进行建模;其次建立了一步运动状态概率转移矩阵;最后以马尔可夫链为基础设计多步概率转移矩阵计算算法.为了验证算法性能,在STM32F407平台上进行了实验,结果表明,MTPA算法相比于传统的匀速预测算法与频率统计算法,预测准确度具有一定的优势,相关研究成果可以为MWSN提供基础.     

带权疾病网络上的潜在共病关系预测

网络分析法将潜在的共病关系预测转化为复杂网络上的链路预测问题,而现有的基于相似性度量的链路预测方法大多仅单一地考虑某一方面的网络特征,大大影响了预测的准确性.使用3个不同来源的真实医疗数据集分别构建了相应的带权疾病网络,并通过对不同网络结构差异性的比较,分析了现有的网络相似性度量指标的局限性.在此基础上,提出了一种新的基于有监督分类的链路预测方法,综合多种局部和全局相似性指标作为输入特征向量,更为精确地评估节点间的相似性,从而实现潜在共病关系的有效预测.实验结果表明,该方法能有效提高共病网络中链路预测的准确性,并且对于不同共病网络和分类算法均具有较好的稳定性和适用性.     

基于马尔科夫链模型的网络链路权重评价方法

网络链路权重评价是网络运维管理的重要依据?将马尔科夫链的转移概率引入到网络链路权重评价中,从概率的角度来衡量相邻节点的可达性;充分考虑链路?节点的故障性,将网络中任意两相邻节点的通信过程近似为马尔科夫过程,基于此,提出了基于马尔科夫链模型的网络链路权重评价方法?根据网络的关联矩阵得到1步概率转移矩阵,进而求得网络的多步马尔科夫转移概率矩阵,直至所有节点概率可达,通过累加相邻节点间概率来衡量链路可达性?通过算例分别分析了串联网络?桥式网络和复杂网络的链路权重评价问题?分析表明,该方法不仅能准确评价网络链路的权重,而且还解决了删边或缩边方法难以分析串联网络的问题,具有计算量小?易编程实现的特点?     

基于多领域复杂网络拓扑结构的节点重要度评价方法

节点的重要度评价对复杂网络上节点的传播影响力具有重要的理论意义和应用价值,但传统的基于网络位置的方法并未考虑多维指标特征对网络节点重要度的影响,导致在大型网络的节点重要度评价中,一般节点的排序结果精度不高.为此在深入剖析经典的混合度分解算法以及传统重要性排序算法缺陷的基础上,结合网络节点的全局特征和局部特征对节点进行重要度影响分析,并将三度影响力原则融入节点的局部特征,提出一种适用于无向网络的基于多领域复杂网络拓扑结构下的节点重要度评价方法,即基于聚集系数和邻居特征的混合分解方法(CNMD).在社交网络、电子邮件网络、协作网络等10个领域数据集上的实验结果表明,相比于MDD、Eksd和MCDWE等算法,CNMD方法排序结果的分辨率分别达到了92.44%、99.99%、98.68%等,在10个领域数据集上的平均分辨率为98.73%,最高分辨率为99.99%,最低分辨率为92.44%,明显优于对比算法,可以更有效地应用于大型复杂网络中节点重要度的快速评价与计算.