一种基于节点相似性的链接预测算法

基于热传导的随机游走链路预测算法的分析与研究
卢文;雒海东;汪生宝
【期刊名称】《青海师范大学学报（自然科学版）》
【年(卷),期】2018(034)004
【摘要】通过观察现有链路预测算法在社交网络推荐系统中的表现,我们发现一些预测算法不能很好的满足特定网络的需求.受现有链路预测算法的启发,本文提出了一种基于热传导的随机游走链路预测算法,算法中加入了基础节点,使得算法效率更高.实验结果表明,基于热传导的随机游走链路预测算法在社交网络推荐系统中的表现优于基于节点相似性的链路预测算法.
【总页数】3页(P1-3)
【作者】卢文;雒海东;汪生宝
【作者单位】青海师范大学计算机学院,青海西宁810016;青海省藏文信息处理与机器翻译重点实验室,青海西宁810008;藏文信息处理教育部重点实验室,青海西宁810008;陕西师范大学计算机学院,陕西西安710119;青海师范大学实验设备中心,青海西宁810016;青海师范大学教务处,青海西宁810016
【正文语种】中文
【中图分类】TP312
【相关文献】
1.基于网络表示学习与随机游走的链路预测算法 [J], 刘思;刘海;陈启买;贺超波
2.基于随机游走的蛋白质功能预测算法设计与实现 [J], 马吉权;贾翠翠;张军杰;
3.基于有偏向的重启随机游走链路预测算法 [J], 吕亚楠;韩华;贾承丰;瞿倩倩
4.基于局部信息节点相似性链路预测算法的分析与研究 [J], 卢文;;;;
5.一种基于MH改进的重启随机游走链路预测算法 [J], 吕亮;何敏;易灿
因版权原因，仅展示原文概要，查看原文内容请购买。

链路预测算法在社交网络分析中的应用研究一、绪论现代社交网络提供了全新的交流和信息传播方式，而且随着移动式互联网的普及和发展，也更加便捷和高效。

从一个个体到组织和社会，社交网络在人们的生活和工作中具有重要意义。

因此，对社交网络中的关系和相互作用进行分析，已成为了不可避免的研究任务。

随着社交网络的迅速发展，人们需要一些高效的算法来分析这些网络。

其中，链路预测算法就是其中之一，它可以用来预测社交网络中未来的链接。

链路预测算法作为一种基于社交网络分析的方法，已成为当前热门的研究领域。

二、链路预测算法的理论基础社交网络分析中的链路预测算法，本质上是一个预测未来社交网络中连接的算法。

这个算法基于不同的方法，例如相似性和共现性，来预测未来可能的链接。

链路预测的理论基础之一是“三角形理论”，即在社交网络中，连接具有“三角形”性质的节点（即某个节点的朋友和朋友的朋友之间的链接）的概率较大。

这个理论通过测算节点之间的距离和“三角形”的数量，来预测两个节点之间的链接。

这个方法因为简单而且有效，所以成为当前链路预测研究的重要方法之一。

三、链路预测算法的应用链路预测算法因为其高效和预测准确性，被广泛应用在社交网络分析中。

下面具体探讨链路预测算法的应用。

（一）社交推荐社交推荐是指基于用户的社交网络信息，来向用户推荐新的用户或者项目。

社交推荐中，链路预测算法可以通过分析用户和他们的社交网络信息，预测新的社交链接。

这个算法可以为用户的新交友提供帮助，同时也可以向用户提供更优质的信息和服务。

（二）社交关系管理社交关系管理指的是在社交网络中，个人和企业建立联系以促进合作、营销等方面的一种系统化管理。

链路预测算法可以在这个过程中，通过分析社交网络中的节点和他们的链接，来预测未来可能的合作和需求。

这个算法可以帮助企业或个人做出更加精准的决策，并加强他们之间的沟通和协作。

（三）社交网络安全社交网络安全是指保护社交网络免受恶意攻击和信息滥用的过程。

移动社交网络中基于共同邻居网络中心度的链路预测方法郑巍;潘倩;邓宇凡
【期刊名称】《计算机应用研究》
【年(卷),期】2016(033)009
【摘要】移动社交网络中的链路预测是指通过已知的网络节点以及移动社交网络结构等信息预测网络中尚未产生连边的两个节点之间产生链接的可能性.基于网络中心度的思想,提出一种适用于移动社交网络的链路预测算法.该算法利用节点网络中心度和共同邻居数来计算两个节点的相似性指标,两个节点的共同邻居数越多、共同邻居的网络中心度越高,则两个节点的相似度越高.另外,由于移动社交网络的动态性特征,还将考虑时间因素对预测结果的影响.将该方法与其他四种常用的链路预测方法进行比较,实验结果显示所提方法要优于其他方法.
【总页数】4页(P2743-2746)
【作者】郑巍;潘倩;邓宇凡
【作者单位】南昌航空大学软件学院,南昌330063;南昌航空大学软件学院,南昌330063;南昌航空大学软件学院,南昌330063
【正文语种】中文
【中图分类】TP393.06
【相关文献】
1.移动社交网络中链路预测方法分析 [J], 郑巍;潘倩
2.基于广义共同邻居的有向网络链路预测方法 [J], 赵学磊;季新生;刘树新;赵宇
3.基于广义共同邻居的有向网络链路预测方法 [J], 赵学磊;季新生;刘树新;赵宇
4.基于共同邻居的小度节点有利链路预测算法 [J], 汤永新;齐敬英
5.基于共同邻居邻域拓扑稠密性加权的链路预测方法 [J], 李星;朱宇航;柏溢;李劲松
因版权原因，仅展示原文概要，查看原文内容请购买。

第 23卷第 1期2024年 1月Vol.23 No.1Jan.2024软件导刊Software Guide基于节点相似性的二阶链路预测方法刘臣，王嘉宾（上海理工大学管理学院，上海 200093）摘要：复杂网络中基于节点相似性的链路预测算法通常根据两个节点之间的相似度，预测节点对之间是否存在链路。

提出基于节点相似性的二阶链路预测方法，判别节点对之间是否存在未连接的节点，并补全节点对之间的二阶链路。

同时，提出二阶链路预测指标，计算已知节点与其他并不存在链路的节点之间的相似性，并构建二阶可达网络保留原始网络中的二阶链路信息。

实验结果表明，该方法能够在真实的网络数据中找到节点对之间的缺失节点，并补全可能存在的二阶链路。

不同的链路预测指标在4个不同网络中的性能表现有所不同，所有实验中的最佳精确率达83.7%。

关键词：复杂网络；二阶链路预测；可达网络；相似性指标；公共近邻DOI：10.11907/rjdk.222457开放科学（资源服务）标识码（OSID）：中图分类号：TP391；O157.5 文献标识码：A文章编号：1672-7800（2024）001-0097-06Second-order Link Prediction Method Based on Node SimilarityLIU Chen， WANG Jiabin（Business School， University of Shanghai for Science and Technology， Shanghai 200093， China）Abstract：Link prediction algorithm based on node similarity usually predicts whether there is a link between node pairs according to the simi⁃larity between two nodes. A second-order link prediction method is proposed to determine if there is an unconnected node between node pairs，and then complete the second-order links between node pairs. The second-order link prediction index is used to calculate the similarity be⁃tween known nodes and other nodes that do not have links， and the second-order reachable network is constructed to retain the second-order links in the original network. The experimental results show that the missing nodes between node pairs can be identified in real network data and their second-order links can be completed. The performance of different link prediction indices varies across four different networks， and the best precision rate reaches 83.7% in all experiments.Key Words：complex network； second-order link prediction； reachable network； similarity index； common neighbor0 引言现实世界中的很多复杂系统，如社交关系、交通运输、生物系统、信息系统等，都可以建模为网络。

基于链路预测的复杂网络瓦解建模与分析随着社会网络的发展，人们越来越关注复杂系统的瓦解问题。

瓦解是指在一个大型网络系统中，当一些节点失去链接时，整个系统会发生系统性崩溃的现象。

为了解决这个问题，越来越多的研究者开始使用基于链路预测的方法来对复杂网络的瓦解进行建模和分析。

链路预测是指通过已知节点之间的连接关系，推断出未知节点之间连接概率的方法。

链路预测可以用于复杂网络的预测、建模和分析，有助于揭示网络结构、识别网络异常事件和预测网络演化。

在使用链路预测进行瓦解建模和分析时，需要考虑以下问题：1.节点与节点之间的相似性在复杂网络中，节点与节点之间存在相似性。

基于节点相似度，可以通过计算节点之间的聚类系数、度分布等指标来预测新节点的出现和两个节点之间的连接概率。

2.节点与环节之间的相似性除了节点之间的相似性外，还需要考虑节点和环节之间的相似性。

环节是指连接网络中不连接任何节点或者仅连接一部分节点的链接。

通过计算节点与环节之间的相似度，并使用相应的算法预测环节的出现，可以预测新节点的出现和节点之间的连接概率。

3.网络结构网络结构也是影响链路预测精度的重要因素。

网络结构通常可以分为无序网络、小世界网络和无标度网络。

在不同类型的网络中，链路预测的方法和精度也不同。

基于链路预测的复杂网络瓦解建模和分析方法通常可以分为以下几个步骤：1.网络数据收集根据实际需求，收集数据并构建网络模型。

2.网络特征提取通过计算网络进行链路预测需要的特征，例如节点度中心性、节点介数中心性、节点紧密中心性等。

3.预测新节点和环节出现概率通过使用相应的算法预测新节点和环节的出现概率。

4.预测节点之间连接概率通过使用相应的算法预测节点之间的连接概率。

5.评估链路预测模型的精度使用一些评估指标来评估链路预测模型的精度，例如准确率、精确率、召回率等。

链路预测是目前研究复杂网络瓦解问题的重要方法之一。

通过基于链路预测的复杂网络瓦解建模和分析方法可以预测网络的瓦解情况，为保障网络的安全和稳定性提供重要的参考依据。

摘要随着社交网络应用普及，现实世界的人与人之间的关系可以抽象为社交网络中用户之间的链接。

链接预测的目标是根据社交网络中现有的用户关系和用户自身包含的属性，预测用户之间是否会生成新链接。

因此，通过预测社交网络新链接可以发现用户与用户之间可能产生的新关系。

这方面的研究具有重要的意义。

本文使用监督方法进行社交网络链接预测。

监督链接预测通常使用节点之间的接近度构成分类链接的特征。

然而，现有的监督链接预测方法仅仅说明它所使用的节点之间接近度，而没有给出选择这些接近度的理由。

因此，本文提出了一种方法用来评价节点间的接近度对预测结果的影响，并以此为根据进行接近度的选择。

此外，现有的链接预测方法仅仅考虑节点之间的拓扑结构接近度构成分类链接的特征，而忽视了社交网络中包含的节点属性信息。

因此，本文在基本的时间序列和流数据链接预测方法的基础上，提出了既考虑节点之间的拓扑结构接近度，又考虑节点之间的属性相似度(率)的链接预测方法。

最后，目前链接预测的绝大多数工作只进行了方法准确率的比较，需要对链接预测的结果以可视化的方式进行展示。

本文使用Python搭建了可视化的仿真系统，在共同作者数据集和微博转发数据集上对提出的方法进行了实验与测试。

结果表明，本文提出的考虑节点自身属性的链接预测方法和未考虑的方法相比，具有更高的准确率，并且该系统能在给定用户的情况下提供可能与他产生关系的用户。

关键词：动态链接预测，接近度，社交网络，相似度，用户属性IAbstractWith the popularity of social network apps, the relationship between people in the real world can be abstracted as a link between users in a social network. The goal of link prediction is to predict whether new links will be formed between users based on the existing relationships of users and their attributes. Therefore, predicting new links between nodes in social networks can be considered as predicting new relationship between people. This research is of great significance.This thesis uses supervised methods for link prediction in social networks. Supervised link prediction methods use proximity between nodes to form the features for classifying links. However, existing supervised link prediction methods only illustrate the metrics that evaluate the links and do not offer the reason for selecting these metrics. Therefore, this thesis proposes a method to evaluate the influence of metrics between nodes on prediction result and use this as a basis for metric selection. Besides, the existing link prediction methods only consider the topology metric between node pairs to compose the feature of the link, but ignore the node attribute information contained in social networks. Therefore, this thesis proposes a link prediction method that considers both topology proximities and the attribute similarities between nodes based on the basic time series and stream link prediction methods. Finally, existing works only compares the accuracy of methods, and the results of link prediction can be displayed in a visible way.The Python is used to build a visualized simulation system. The proposed method is experimented and tested based on co-author dataset and microblog dataset. The result shows that the proposed method that considers attributes of nodes has higher accuracy than the method without such consideration and the visualized system can recommend the possible friend to a given user. Key words: Dynamic link prediction, Proximity, Social networks, Similarity, User attributes目录第一章绪论 (1)1.1 研究背景与意义 (1)1.2 研究现状 (2)1.2.1 传统链接预测 (2)1.2.2 动态链接预测 (3)1.3 论文的主要工作 (3)第二章相关技术研究 (5)2.1 静态链接预测 (5)2.1.1 非监督方法 (5)2.1.2 监督方法 (8)2.2 动态链接预测 (9)2.2.1 基于时间序列的动态链接预测 (10)2.2.2 基于流数据的动态链接预测 (13)2.3 准确率评价指标 (16)2.4 本章小结 (17)第三章动态链接预测方法的研究 (18)3.1动态链接预测问题及方法概述 (18)3.2 节点间接近度分析 (18)3.2.1拓扑结构 (21)3.2.2 节点属性 (21)3.2.3 接近度选择 (22)3.2.4 接近度选择的评测 (25)3.3基于节点属性的动态链接预测 (29)3.3.1 时间序列链接预测 (30)3.3.2流数据链接预测 (33)3.4本章小结 (40)第四章动态链接预测仿真系统设计与实现 (41)4.1 仿真系统功能框图 (41)4.2数据采集模块 (42)4.3数据处理模块 (43)4.4链接预测模块 (44)4.5可视化模块 (46)4.5出现的问题及其解决方案 (47)4.6本章小结 (47)第五章动态链接预测仿真系统的测试与性能分析 (48)5.1 动态链接预测仿真系统的测试 (48)5.1.1 测试流程 (48)5.1.2 统计分析 (51)5.2 性能分析 (52)5.2.1 实验步骤 (52)5.2.2 ROC曲线分析 (53)5.3 本章小节 (60)第六章总结 (61)参考文献 (62)附录1 攻读硕士学位期间撰写的论文 (65)附录2 攻读硕士学位期间参加的科研项目 (66)致谢 (67)第一章绪论1.1 研究背景与意义互联网的日益普及给人们之间相互联系带来了极大的便利。

复杂网络中的链路预测算法研究与应用随着信息时代的到来，社交网络、生物网络、交通网络等复杂网络的规模和复杂性不断增加。

在这些网络中，链路（边）的预测成为一项重要的任务，旨在通过已有的网络结构信息，预测未来可能存在的链路，从而洞察网络的演化规律、探索网络的隐含关系。

一、链路预测算法的研究进展近年来，学术界和工业界都对链路预测算法进行了广泛的研究和探索。

传统的链路预测算法主要基于相似性原理，通过计算节点对之间的相似性指标（如共同邻居、Jaccard系数、Adamic/Adar指数等），来衡量节点对之间可能存在的链接。

然而，由于复杂网络的特殊性，传统的相似性原理算法在链路预测任务中存在诸多问题，例如无法处理高度稀疏网络、忽视了节点之间的联系强度等。

为了克服传统算法的局限性，研究者们提出了各种新的链路预测算法。

其中一类常见的方法是基于机器学习的算法，如支持向量机（SVM）、神经网络（NN）、随机森林（RF）等。

这些算法通过学习已知链路属性与节点特征之间的关系，在预测未知链路时进行推断。

此外，还有一些基于社区结构、网络结构等特征的算法被提出，如基于社区信息的算法、基于路径的算法等。

二、链路预测算法的应用领域链路预测算法在各个领域都有广泛的应用。

以下是几个典型的应用领域：1. 社交网络：社交网络中的链路预测可以帮助我们发现可能有潜在关系的人物，为社交平台的推荐系统提供更准确、个性化的推荐结果。

例如，在微博平台上，可以通过预测两个用户之间是否存在链接，提供更精准的用户推荐、好友推荐等服务。

2. 生物网络：在生物网络中，链路预测可以帮助我们理解蛋白质相互作用网络、基因调控网络等生物过程中的关键因素和相互关系。

通过预测蛋白质之间的相互作用，有助于研究疾病的发生机制、药物研发等领域。

3. 交通网络：链路预测在交通网络中的应用可用于预测城市道路的流量、拥堵情况和交通状况。

基于链路预测的交通优化算法可以帮助城市规划者和交通管理部门制定更合理的交通规划和交通流管理策略，提高城市交通效率和安全性。

网络拓扑知识：基于网络拓扑的链路预测算法近年来，随着网络规模的不断扩大和各种网络应用的快速发展，网络拓扑的研究日益受到关注。

网络拓扑是指一个网络的结构和连接方式，它对网络的性能和功能有着重要影响。

因此，研究网络拓扑的基础和特性对于优化网络性能、提高网络效率、预防网络安全风险具有重要意义。

链路预测算法就是一种基于网络拓扑的预测算法，主要用于预测一个网络中两个节点之间是否存在连通关系。

链路预测算法在许多领域都有着广泛的应用，如社交网络、信任网络、生物信息等。

在实际应用中，如何预测两个节点之间是否存在连通关系，以及如何准确地预测链路的存在性，一直是一个具有挑战性的问题，而链路预测算法正是为解决这个问题而被提出的。

链路预测算法的主要目的是利用已有的网络拓扑结构，预测不同节点间添加新边的可能性，从而可以用于社交网络中预测关系的建立和信任网络中的可信度判断等应用场景中。

而在预测这种连通关系的过程中，一些基本原理和技术是需要用到的。

首先，在链路预测算法中，必须找到一种合适的拓扑表示方式，以将网络形态呈现出来，这是进行任何预测算法之前的先决条件。

这一步通常会使用矩阵或者图等方式来表示已有网络结构中的节点与边。

其次，链路预测算法中要使用的一些核心原理和技术包括了：1.基于相似性的链路预测算法基于相似性的链路预测算法，主要是通过节点之间的相似度计算来判断节点之间是否存在连通关系，并在此基础上预测链路的存在性。

这种算法可以使用一些度量标准，例如余弦相似度或者皮尔逊相关系数等来计算节点之间的相似度，从而实现基于相似度的链路预测。

2.基于统计模型的链路预测算法基于统计模型的链路预测算法是一种通过对已有网络结构进行数学建模，利用概率统计原理进行链路预测的算法。

这种方法可以用网络拓扑的性质来估计链路的存在概率，并且可以应用于不同类型和规模的网络中。

3.基于机器学习的链路预测算法基于机器学习的链路预测算法是建立在已有网络结构中的各种节点和边的属性上进行预测的算法。

基于PSO优化算法的链路预测AA指标适用网络问题研究孟晓宇路兰【摘要】链路预测相似性指标是一类根据复杂网络结构计算节点相似性从而预测节点间关系的算法。

鉴于目前的链路预测相似性算法适用的网络参数无迹可寻。

本文选取测评小世界网络最优的AA指标，运用粒子群优化算法探究其网络最佳适用参数。

结果表明网络密度较小的小世界网络采用AA指标测评时精确度较好。

【关键词】复杂网络;链路预测;相似性算法;粒子群优化算法O157.5 ： A ： 2095-2457（2019）02-0117-002【Abstract】link prediction similarity index is a kind of algorithm which calculates node similarity according to complex network structure and predicts the relationship between nodes.In view of the fact that the network parameters applicable to the current link prediction similarity algorithm are traceless.In this paper，we select the best AA indices for evaluating scale-free networks，small-world networks，and use particle swarm optimization to explore the optimal parameters for their networks.The results show that AA index is used for small-world networks with low network density.【Key words】Complex network; link prediction; Similarity Algorithms; Particle Swarm Optimization0 引言复杂网络由许多节点及节点之间相连接的边构成，用来刻画自然和社会中大量的复杂系统。