网络结构偏好对链路预测的影响

文摘

在复杂网络链路预测预测的可能性联系一代尚未连接的两个节点之间的网络,基于已知网络结构和属性。它可以应用在各个领域,比如朋友推荐在社交网络和预测蛋白质相互作用的生物。然而,在《社交网络》,链接预测可能提高隐私和安全的担忧,因为,通过链路预测算法,罪犯可以预测一个帐户的用户的朋友,甚至可能进一步发现私人信息,比如地址和银行账户。因此,迫切需要开发一个策略来防止被链接预测算法识别和保护隐私,利用摄动网络结构以较低的成本,包括修改和添加边缘。本文主要关注网络结构偏好扰动的影响通过删除链接预测。根据大量的实验的各种真实网络,边缘large-small度节点和结合度节点之间最显著影响链接预测的质量。

1。介绍

复杂网络中扮演重要角色的建模和分析复杂系统如社会系统、生物系统、信息系统(1]。一般来说,个人,如人类、生物元素,和电脑,节点代表,而链接表示节点之间的关系或相互作用[2]。复杂网络理论提供新的见解连接在现实世界中。相关的研究不仅关注单层网络,如聚类(3),链接预测(4,和社区发现5,6)但也多层网络(7级联(等),8,9)、沟通(10- - - - - -13)、同步(14),和游戏15- - - - - -17]。

链接预测在一个复杂的网络包括预测未知或链接在一个给定的网络。基于公共网络的结构和属性,链接预测的目的是预测两个节点之间的链接生成的可能性,而尚未连接(18]。对于一个给定的无向网络,如图1网络中,实线表示已知的边缘,而虚线表示未知的边缘或在未来。我们需要做的就是预测未知的边缘用虚线准确通过已知的节点和边。作为数据挖掘的研究方向之一,链接预测可以应用于各个领域。例如,在社会网络中,链路预测可以推荐新朋友通过预测用户是否熟人离线两个陌生人在线。在生物学上,预测蛋白质相互作用将大大降低实验成本。除此之外,研究人员应用链接预测节点的概念和方法分类,例如确定一篇文章的类型在学术网络(19]。

研究人员做出了相当大的努力来提高链路预测的准确性。许多链接预测算法是基于节点之间的相似性,认为类似的两个节点越多,越有可能它们之间有联系。描述节点之间相似度的指数大致可以分为本地索引,全球指数,拟局部索引。的本地索引中最常用的方法是基于节点相似性,由于它的简单性和适应性大大大型网络。还有其他的链接预测算法可以基于最大似然估计,和他们有更好的性能在处理网络与不同的层次结构,如草原食物链(20.]。一些算法也可以采用概率模型链接预测,在信息处理覆盖不仅网络结构,而且节点的属性。这些算法具有较高的预测精度,但与此同时,更大的计算复杂性(21]。

在生物网络链接预测通常被证明有用。然而在社交网络,他们可能提高隐私和安全的担忧,我们的数据是有价值的不仅为企业和公共机构也为越来越多的网络犯罪进行网络分析的恶意目的。通过链路预测算法,网络罪犯可以准确地预测社会账户用户的朋友甚至是该帐户的所有者根据他或她的关系。如果他们进一步挖掘,罪犯可能会发现这个名字,年龄,地址,银行账户和其他私人信息社会账户对应的实体。

考虑以上提到的,迫在眉睫的是提高隐私保护。然而,目前,缺乏集中研究如何防止链路预测算法的识别利用隐藏,通过网络结构改变,或添加边缘干扰小成本。基于邻接矩阵的摄动,陆et al。22]研究了结构一致性的影响在链接可预测性。Waniek et al。23)研究如何通过重新连接隐藏敏感关系网络策略,提出了一种启发式方法在实现它。吴et al。24)提出了一个活跃的学习算法,应用摄动最符号链接网络,调整结构图的可预测性。

基于之前的研究,本文主要关注网络结构偏好的影响干扰通过删除链接预测。根据大量的实验的各种真实网络,边缘large-small度节点和结合度节点之间最显著影响链接预测的性能。在实际网络节点之间连接的选择并不统一,但有一个明显的偏好,从而导致网络中节点之间的相关性。基于此连接节点之间的相关性,提出了同质性和异质性的概念区分的连接节点之间的偏好。因此,复杂网络节点的异构性是衡量节点均匀分布的。如果节点倾向于连接相似的节点,它们将形成均匀网络;如果高的节点和连接节点有一定的概率低,他们将形成异构网络。

2。模型演示

在这一节中,本文中使用的一些基本术语将首次引入,根据官方的定义。然后,我们将网络结构偏好扰动的方法。最后,将该方法的伪代码。

2.1。定义

一个复杂的网络:给定生物或社交网络可以建模为一个图表, ,在这表示网络中节点的集合,表示的边缘表示网络的相邻矩阵。当有一个链接 节点之间和 ,矩阵的元素满足 ;否则,他们满足 。我们可以使用源和目标之间的关系来描述节点,从而将网络划分为直接的和间接的网络。指导网络的链接,通过电弧的名字,是建立从源节点到目标节点。在无向网络中,源节点和目标节点之间是没有区别的一个链接,通过边缘的名字。本文将主要集中在无向网络,可进一步应用于定向网络方便。

链接预测:在一个给定的网络 , 表示节点和数量表示边的数量。因此,节点对的总数 。如果通用设置表示网络中所有节点对的集合,链接预测工作如下:任何一对节点,用 ,不属于网络,将被分配一个特定的分数通过某种算法。然后,基于分数分配给双节点,最大的对预测将被选择作为边缘。

网络结构偏好扰动:在一个给定的网络 ,网络结构偏好扰动的目的是执行一个或多个操作中添加、更改和删除以更低的成本向网络边缘的基于边的集合 。这些操作的目的是,当一个新的网络 最终,形成边缘丢失或在吗通过上面介绍的操作几乎可以预见。

2.2。微扰法

网络结构偏好微扰的方法主要是由一个或多个操作中添加、更改和删除网络的边缘。这篇文章将集中删除,试图识别特定的边缘质量显著影响链接预测的影响。对于一个给定的网络 ,边的集合可分为一组训练吗和测试集 。网络结构扰动主要发生在列车的偏好。扰动后,边缘预测可以通过一种算法训练网络的链接预测。链接预测的性能可以通过比较计算边缘和测试集预测。在以下段落是指给定的网络培训网络。

当一个培训网络已经从最初的一个划分,我们开始应用摄动。用任何优势 ,其删除值可以通过以下公式计算:

在这个公式,和分别表示节点的程度和 。 用于控制边缘的偏好选择。当被指定为一个特定的值,每条边的权重选择的计算。例如,当略大于0,大型和小型节点和介质和介质之间的连接节点有一个更大的重量,这意味着它更容易被选中。是一个可调参数。公式(1)确保删除所有的边的价值之和等于1。

获取每条边的缺失值之后,我们建立一个参数的比例 ,为了随机挑选边缘的数量 和删除它们。值得注意的是某些节点的程度后的边缘可能会改变边缘已被删除,因此,每个节点的删除值, ,将被改变。在理想的情况下,删除价值剩余的边缘应该重新计算每次删除一条边。然而,微扰算法的时间复杂度将是巨大的。降低时间复杂度,比例间隔设置的参数的名称 ,这意味着删除值的计算只是每后重做 边被删除。

该方法的伪代码如下。(参见算法1)。

3所示。实验

3.1。实验装置

我们已经尝试过在四个真实网络的统计数据如表所示1。在实验中,使用四个链接预测算法,包括RA (29日],AA [30.],CN”[31日),和爸爸32]。对于一个随机给定的节点 ,与表示其相邻节点的集合,这四种算法的计算公式可以表示如下:

资源分配(RA)

Adamic-Adar (AA)指数

常见的邻居(CN)

优惠附件(PA)

我们这里选择精确的索引链接预测的性能。对于一个给定的边缘没有被观察到,精度定义为成功的比率预测边缘l预测的边缘。假设是成功地预测了边缘的数量在前预测的边缘;然后,精密的计算公式可以表示如下:

对于一个给定的网络,训练集和测试集将除以的比率 。为了测试的性能预测,扰动将被应用在火车上设置不同和 。然后,预测将会通过链接的四个算法预测,结果将与测试集,每个实验会重复100次。

3.2。实验结果

首先,实验假设= 0.01,0.1,0.2,0.3,和0.4,分别 。通过四个算法精度计算四个数据集将受到考验,条件下−20 - 20,不等间隔的1。如图2结果表明,当是略大于0,精度达到的最小值,标志着网络扰动的最佳效果。结果所示例(a), (e),(我)从图3表明large-small度节点和结合度节点之间的边有最大影响链接预测的性能。

然后,−将−20日10 0,10,20,分别和 。通过四个算法精度计算四个数据集的条件下,将被测试范围从0.01到0.4,0.01的区间。如图4,在大多数情况下,精度降低f增加对所有算法的四种方法。因为越大是,删除边会比越大,仍然在网络的边缘越来越少,从而减少的质量预测的不同的链路预测算法。然而,在某些情况下在代谢和神经网络精度增加增加,这可能是由于新陈代谢和神经网络有较高的节点的异质性程度。

为了更好地证明了影响网络结构偏好扰动对链路预测,我们也通过四个测试精度计算算法在四个数据集,条件下−20 - 20,不等间隔为1,范围从0.01到0.4,0.01的区间 。实验结果如图所示5,曲线在水平平面是孤立的。

4所示。结论

在本文中,网络结构偏好扰动的影响通过删除链接预测进行了分析。通过使用一个交互式的准则来确定节点度,我们首先分配一个微扰值通过计算每条边在一个给定的网络。然后,我们根据扰动,应用摄动边通过删除选中的值。这个过程会重复,直到一定比例的边缘经历扰动。之后,我们做链接预测网络扰动前后,用四种方法包括RA, AA, CN, PA,而不同的影响类型的连接和删除的比例对链路预测的性能。

巨大的各种真实的网络实验表明,边缘large-small程度结合学位之间的节点和节点之间有最显著的影响链接预测的性能。通过删除网络中的特定链接,我们可以抵御链接预测对隐私保护的影响。上述策略不仅可以保护隐私领域的社交网络也值得推广和应用在其他领域。例如,在计算机通信拓扑的设计,以减少大型和小型节点之间的连接,媒介和媒介节点可以抵御拓扑估计,以更好地保护我们自己的网络;在反恐领域,我们应该更加注意领袖之间的连接节点和叶子节点,这常常意味着恐怖的脆弱性团队沟通连接。

数据可用性

数据可以要求获得相应的作者。

的利益冲突

作者宣称没有利益冲突。

确认

这部分工作是由中国国家自然科学基金(批准号61903266),中国博士后科学基金(批准号2018 m631073),特别中国博士后科学基金会(批准号2019 t120829),基础研究基金中央大学和四川科技项目(排名20 yyjc4001)。

引用

1. r·艾伯特和A.-L。巴斯”统计力学的复杂网络,“现代物理学的评论,卷74,不。1,47 - 97、2002页。视图:出版商的网站|谷歌学术搜索
2. m·纽曼网络:介绍,牛津大学出版社,纽约,纽约,美国,2010年。
3. c .崔韩x l . Wang j .马和美国,“连接多个网络身份在刑事调查:一个光谱co-clustering框架,“IEEE取证和安全信息,12卷,不。9日,第2255 - 2242页,2017年。视图:出版商的网站|谷歌学术搜索
4. 董k .气阴,y, h .董”链接预测在动态网络中基于节点之间的吸引力,“以知识为基础的系统,181卷,2019年。视图:谷歌学术搜索
5. g .阴k气、y盾和h .侗族“社会进化的一种方法基于引力关系重构的动态网络,”物理信,卷381,不。16,1349 - 1355年,2017页。视图:出版商的网站|谷歌学术搜索
6. 张x, z赵,c . Li f . Chiclana和e·h·Viedma“增量方法检测动态演进的社会网络中的社区,”以知识为基础的系统卷,163年,第415 - 404页,2019年。视图:出版商的网站|谷歌学术搜索
7. r, s .江x Chen h . Wang w . Wang和w·王,“层间链接预测在多元社会网络:惩罚算法迭代的学位,”以知识为基础的系统,第194卷,第105598页,2020年。视图:出版商的网站|谷歌学术搜索
8. j .高诉Buldyrev, h·e·斯坦利和s . Havlin”网络由相互依存的网络”,自然物理,8卷,不。1,40-48,2011页。视图:出版商的网站|谷歌学术搜索
9. j .高诉Buldyrev, s . Havlin h·e·斯坦利,“网络的网络健壮性,”物理评论快报,卷107,不。19日,2011年。视图:出版商的网站|谷歌学术搜索
10. c . Granell s戈麦斯,a .竞技场”动力相互作用意识和流行病传播的多路复用网络,”物理评论快报,卷111,不。12,128701页,2013年。视图:出版商的网站|谷歌学术搜索
11. h . m . w . Wang Tang, y Younghae做研究。赖,g·李,“不对称互动传播动力学复杂分层网络,”科学报告,4卷,不。1,p。5097年,2014。视图:出版商的网站|谷歌学术搜索
12. w . Wang Q.-H。刘,S.-M。Cai, m, l·a·布劳恩斯坦和h·e·斯坦利“抑制疾病传播通过使用多路复用网络信息扩散,”科学报告》第六卷,没有。1,文章ID 29259, 2016。视图:出版商的网站|谷歌学术搜索
13. w . Wang Q.-H。刘,j .梁、胡y和t .周“共同进化在复杂网络传播,”康奈尔大学,伊萨卡岛,纽约,美国物理报告。视图:谷歌学术搜索
14. 张x, s . Boccaletti美国关,z . Liu“爆炸性同步自适应和多层网络,”物理评论快报,卷114,不。第三条ID 038701, 2015。视图:出版商的网站|谷歌学术搜索
15. z, a Szolnoki m . Perc,“最佳网络之间相互依存的进化合作,”科学报告,3卷,不。1,p。2470年,2013。视图:出版商的网站|谷歌学术搜索
16. z, a Szolnoki m . Perc,“相互依存网络进化游戏、互惠”科学报告,3卷,1183页,2013年。视图:出版商的网站|谷歌学术搜索
17. z, a Szolnoki m . Perc,“自组织优化相互依赖的网络的共同进化,”新物理学杂志,16卷,不。第三条ID 033041, 2014。视图:出版商的网站|谷歌学术搜索
18. 39卷,没有。5,651 - 661年,2010页。
19. b·加拉格尔·h·通、t . Eliassi-Rad和c·凯利斯”使用鬼边缘稀疏的分类标签网络”第14届ACM SIGKDD学报》国际会议上知识发现和数据挖掘,页256 - 264,拉斯维加斯,内华达州,美国,2008年8月。视图:谷歌学术搜索
20. a . Clauset c·摩尔,m·e·j·纽曼”层次结构和失踪链接网络的预测,”自然,卷453,不。7191年,第101 - 98页,2008年。视图:出版商的网站|谷歌学术搜索
21. b . Taskar M.-F。黄、p . Abbeel和d·科勒”在关系数据链接预测,”先进的神经信息处理系统,第666 - 659页,2004年。视图:谷歌学术搜索
22. t . l . Lu周,研究。张,h·e·斯坦利“链接复杂网络的可预测性,”美国国家科学院院刊》上,卷112,不。8,2325 - 2330年,2015页。视图:出版商的网站|谷歌学术搜索
23. m . Waniek k .周y Vorobeychik, e·莫罗t p的旧事和t . Rahwan”如何从链路预测算法,隐藏的关系”科学报告,9卷,不。1、1 - 10,2019页。视图:出版商的网站|谷歌学术搜索
24. g . t . Wu Ming, x西安,乔,w . Wang和g .徐”结构可预测性优化推理攻击在数据发布中,“IEEE访问7卷,第92136 - 92119页,2019年。视图:出版商的网站|谷歌学术搜索
25. 下午格雷斯和l . Danon群落结构在爵士,”复杂系统的进展,卷06,不。4、565 - 573年,2003页。视图:出版商的网站|谷歌学术搜索
26. y Takahata,历时变化的主导地位关系的成年女性日本Arashiyama B组的猴子,猴子Arashiyama,纽约州立大学出版社,纽约,纽约,美国,1991年。
27. j .杜赫,a .竞技场。”在使用极值优化复杂网络社区探测物理评论E,卷72,不。2、文章ID 027104, 2005。视图:出版商的网站|谷歌学术搜索
28. d·j·瓦和s . h .““集体动力学的“小世界”网络”,自然,卷393,不。6684年,第442 - 440页,1998年。视图:出版商的网站|谷歌学术搜索
29. 问:你,Y.-D。金,t·周B.-H。王,B.-Q。阴”,幂律从加权网络资源分配动态强度的相关性,”物理评论E,卷75,不。2、文章ID 021102, 2007。视图:出版商的网站|谷歌学术搜索
30. 达洛杉矶亚当和大肠”,在网络上的朋友和邻居,”社交网络,25卷,不。3、211 - 230年,2003页。视图:出版商的网站|谷歌学术搜索
31. m·e·纽曼,“集群和优先连接在日益增长的网络。”物理评论E,卷64,不。2、文章ID 025102, 2001。视图:出版商的网站|谷歌学术搜索
32. l . Lu和l . Lu”在复杂网络链路预测:一项调查,”自然史答:统计力学及其应用,卷390,不。6,1150 - 1170年,2011页。视图:出版商的网站|谷歌学术搜索
33. m·e·纽曼,“选型混合网络,”物理评论快报,卷89,不。2002年20篇文章ID 208701。视图:出版商的网站|谷歌学术搜索

版权

版权©2020年永诚王等。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。