基于子图演化与改进蚁群优化算法的社交网络链路预测方法
发布时间：2021-08-27 11:10
基于改进蚁群优化算法与子图演化,提出了一种新型非监督社交网络链路预测（SE-ACO）方法。该方法首先在社交网络图中确定特殊子图;然后研究子图演化以预测图中的新链接,并用蚁群优化算法定位特殊子图;最后针对所提方法使用不同网络拓扑环境与数据集进行检验。结果表明,与其他无监督社交网络预测算法相比,所提SE-ACO方法在多数数据集上的评估结果较好,且运行时间较短,这表明图形结构在链路预测算法中起重要作用。
【文章来源】：通信学报. 2020,41(12)北大核心EICSCD
【文章页数】：15 页
【部分图文】：
公开标准数据集中基于ROC曲线下面积的几种算法的比较结果
单个关系无向网络中某节点和某社群间可能的相关性如图1所示。图1中第一层显示了节点和社群的最简单关系，该层中单个关系无向网络中仅存在一个链接，如时刻t的快照所示。时刻t的快照表示一种网络结构，链路预测算法用该结构预测下个快照中的新链接。如前所述，每2个实体间至少应有一个链接，这样才能预测下个快照中的链接。图1中的2个实体分别为左侧的源节点和右侧的目标社群。第一层中未保留链接来预测网络中的下一快照。第二层的目标社群由2个节点组成，该层中时刻t的快照表示源节点与社群间的关联，时刻t+1的快照表示可创建的可能链接（虚线）。由于所有链接和节点的权重相同，因此图1中未描绘其他可能的同构交互。第二层中有4种不同的关系，因此存在4种不同的可能链接。第四层是本文关注点的重点，其群体结构为三角关系，左右两部分分别有2个可能的链接。本文将讲述如何根据第四层的子图结构来预测链接。而第三层中为最常见的社交网络结构，在此不做赘述。图1所示四大层次并不是如今算力所能解决的，还可以考虑更多节点、更复杂的群体结构，但由于找出这些的群体成本更高，因此本文未考虑更复杂的层次，仅示例社交网络中两实体间更复杂的交互层次交互关系，如图2所示。图1中的第四层定义了本文所述方法，具有一个节点和一个三角关系，且三角关系中至少存在一条公共边。第四层有2个子图(a)和(b)。由于子图(b)的结构属性多于子图(a)，而结构属性越多，预测出正确链接的机会就越大，故子图(b)价值更大。为证明这一观点，本文对比了根据子图(a)与子图(b)所预测的链接的准确性。首先从社交网络样本中提取出子图(a)和子图(b)，然后考察了作为潜在链接的所有潜在链接（即图1中的虚线），最后根据精度度量对比了这2个子图所预测出的链接质量。对比结果显示本文观点是正确的，即如果使用更多的结构属性，可以更正确地预测链接。Huang[31]的实验也证实了该结论，具体遍历与循环数计算方式参考文献[31]。因此，根据黄璐等[32]提出的概率模型，子图(b)中仅有一条边不存在的概率要大于子图(a)中2个链接都不存在的概率。本文对图1的其他层也进行了同样的实验，并将其结果与第四层结果进行了对比，发现第四层中的子图结构更有利于社交网络情景中的链路预测，故本文用第四层的子图结构来进行社交网络链路预测。
图1中的第四层定义了本文所述方法，具有一个节点和一个三角关系，且三角关系中至少存在一条公共边。第四层有2个子图(a)和(b)。由于子图(b)的结构属性多于子图(a)，而结构属性越多，预测出正确链接的机会就越大，故子图(b)价值更大。为证明这一观点，本文对比了根据子图(a)与子图(b)所预测的链接的准确性。首先从社交网络样本中提取出子图(a)和子图(b)，然后考察了作为潜在链接的所有潜在链接（即图1中的虚线），最后根据精度度量对比了这2个子图所预测出的链接质量。对比结果显示本文观点是正确的，即如果使用更多的结构属性，可以更正确地预测链接。Huang[31]的实验也证实了该结论，具体遍历与循环数计算方式参考文献[31]。因此，根据黄璐等[32]提出的概率模型，子图(b)中仅有一条边不存在的概率要大于子图(a)中2个链接都不存在的概率。本文对图1的其他层也进行了同样的实验，并将其结果与第四层结果进行了对比，发现第四层中的子图结构更有利于社交网络情景中的链路预测，故本文用第四层的子图结构来进行社交网络链路预测。算法1描述了SE-ACO算法的具体过程，其目的是由社交网络在时刻t的快照找出图1中子图(a)与子图(b)，然后预测这些子图中在时刻t+1的快照的潜在链接（即图1中的虚线链接）。接下来，根据蚁群优化算法找出的社交网络中的三角关系。找到三角关系后，本文试图根据这些三角关系找出图1中的子图(a)与子图(b)。由于某些链接在多个子图结构中是共用的，故其评分会更高。最后，本文按评分降序排列得出预测链接的列表。
【参考文献】：
期刊论文
[1]基于资源传输匹配度的复杂网络链路预测方法[J]. 刘树新,李星,陈鸿昶,王凯. 通信学报. 2020(06)
[2]一种基于资源传输路径拓扑有效性的链路预测方法[J]. 王凯,李星,兰巨龙,卫红权,刘树新. 电子与信息学报. 2020(03)
[3]图神经网络[J]. 白铂,刘玉婷,马驰骋,王光辉,闫桂英,闫凯,张明,周志恒. 中国科学:数学. 2020(03)
[4]基于层次化混合特征图的链路预测方法[J]. 李冬,申德荣,寇月,林梦儿,聂铁铮,于戈. 中国科学:信息科学. 2020(02)
[5]基于图神经网络的动态网络异常检测算法[J]. 郭嘉琰,李荣华,张岩,王国仁. 软件学报. 2020(03)
[6]基于图聚类与蚁群算法的社交网络聚类算法[J]. 叶小莺,万梅,唐蓉,谢云,陈桂宏,李强. 计算机应用研究. 2020(06)
[7]基于加权网络链路预测的新兴技术主题识别研究[J]. 黄璐,朱一鹤,张嶷. 情报学报. 2019(04)
[8]基于信息融合的概率矩阵分解链路预测方法[J]. 王智强,梁吉业,李茹. 计算机研究与发展. 2019(02)
[9]基于深度卷积神经网络的多节点间链路预测方法[J]. 舒坚,张学佩,刘琳岚,杨志勇. 电子学报. 2018(12)
[10]基于边重要度的矩阵分解链路预测算法[J]. 郭丽媛,王智强,梁吉业. 模式识别与人工智能. 2018(02)
本文编号：3366238
【文章来源】：通信学报. 2020,41(12)北大核心EICSCD
【文章页数】：15 页
【部分图文】：
公开标准数据集中基于ROC曲线下面积的几种算法的比较结果
单个关系无向网络中某节点和某社群间可能的相关性如图1所示。图1中第一层显示了节点和社群的最简单关系，该层中单个关系无向网络中仅存在一个链接，如时刻t的快照所示。时刻t的快照表示一种网络结构，链路预测算法用该结构预测下个快照中的新链接。如前所述，每2个实体间至少应有一个链接，这样才能预测下个快照中的链接。图1中的2个实体分别为左侧的源节点和右侧的目标社群。第一层中未保留链接来预测网络中的下一快照。第二层的目标社群由2个节点组成，该层中时刻t的快照表示源节点与社群间的关联，时刻t+1的快照表示可创建的可能链接（虚线）。由于所有链接和节点的权重相同，因此图1中未描绘其他可能的同构交互。第二层中有4种不同的关系，因此存在4种不同的可能链接。第四层是本文关注点的重点，其群体结构为三角关系，左右两部分分别有2个可能的链接。本文将讲述如何根据第四层的子图结构来预测链接。而第三层中为最常见的社交网络结构，在此不做赘述。图1所示四大层次并不是如今算力所能解决的，还可以考虑更多节点、更复杂的群体结构，但由于找出这些的群体成本更高，因此本文未考虑更复杂的层次，仅示例社交网络中两实体间更复杂的交互层次交互关系，如图2所示。图1中的第四层定义了本文所述方法，具有一个节点和一个三角关系，且三角关系中至少存在一条公共边。第四层有2个子图(a)和(b)。由于子图(b)的结构属性多于子图(a)，而结构属性越多，预测出正确链接的机会就越大，故子图(b)价值更大。为证明这一观点，本文对比了根据子图(a)与子图(b)所预测的链接的准确性。首先从社交网络样本中提取出子图(a)和子图(b)，然后考察了作为潜在链接的所有潜在链接（即图1中的虚线），最后根据精度度量对比了这2个子图所预测出的链接质量。对比结果显示本文观点是正确的，即如果使用更多的结构属性，可以更正确地预测链接。Huang[31]的实验也证实了该结论，具体遍历与循环数计算方式参考文献[31]。因此，根据黄璐等[32]提出的概率模型，子图(b)中仅有一条边不存在的概率要大于子图(a)中2个链接都不存在的概率。本文对图1的其他层也进行了同样的实验，并将其结果与第四层结果进行了对比，发现第四层中的子图结构更有利于社交网络情景中的链路预测，故本文用第四层的子图结构来进行社交网络链路预测。
图1中的第四层定义了本文所述方法，具有一个节点和一个三角关系，且三角关系中至少存在一条公共边。第四层有2个子图(a)和(b)。由于子图(b)的结构属性多于子图(a)，而结构属性越多，预测出正确链接的机会就越大，故子图(b)价值更大。为证明这一观点，本文对比了根据子图(a)与子图(b)所预测的链接的准确性。首先从社交网络样本中提取出子图(a)和子图(b)，然后考察了作为潜在链接的所有潜在链接（即图1中的虚线），最后根据精度度量对比了这2个子图所预测出的链接质量。对比结果显示本文观点是正确的，即如果使用更多的结构属性，可以更正确地预测链接。Huang[31]的实验也证实了该结论，具体遍历与循环数计算方式参考文献[31]。因此，根据黄璐等[32]提出的概率模型，子图(b)中仅有一条边不存在的概率要大于子图(a)中2个链接都不存在的概率。本文对图1的其他层也进行了同样的实验，并将其结果与第四层结果进行了对比，发现第四层中的子图结构更有利于社交网络情景中的链路预测，故本文用第四层的子图结构来进行社交网络链路预测。算法1描述了SE-ACO算法的具体过程，其目的是由社交网络在时刻t的快照找出图1中子图(a)与子图(b)，然后预测这些子图中在时刻t+1的快照的潜在链接（即图1中的虚线链接）。接下来，根据蚁群优化算法找出的社交网络中的三角关系。找到三角关系后，本文试图根据这些三角关系找出图1中的子图(a)与子图(b)。由于某些链接在多个子图结构中是共用的，故其评分会更高。最后，本文按评分降序排列得出预测链接的列表。
【参考文献】：
期刊论文
[1]基于资源传输匹配度的复杂网络链路预测方法[J]. 刘树新,李星,陈鸿昶,王凯. 通信学报. 2020(06)
[2]一种基于资源传输路径拓扑有效性的链路预测方法[J]. 王凯,李星,兰巨龙,卫红权,刘树新. 电子与信息学报. 2020(03)
[3]图神经网络[J]. 白铂,刘玉婷,马驰骋,王光辉,闫桂英,闫凯,张明,周志恒. 中国科学:数学. 2020(03)
[4]基于层次化混合特征图的链路预测方法[J]. 李冬,申德荣,寇月,林梦儿,聂铁铮,于戈. 中国科学:信息科学. 2020(02)
[5]基于图神经网络的动态网络异常检测算法[J]. 郭嘉琰,李荣华,张岩,王国仁. 软件学报. 2020(03)
[6]基于图聚类与蚁群算法的社交网络聚类算法[J]. 叶小莺,万梅,唐蓉,谢云,陈桂宏,李强. 计算机应用研究. 2020(06)
[7]基于加权网络链路预测的新兴技术主题识别研究[J]. 黄璐,朱一鹤,张嶷. 情报学报. 2019(04)
[8]基于信息融合的概率矩阵分解链路预测方法[J]. 王智强,梁吉业,李茹. 计算机研究与发展. 2019(02)
[9]基于深度卷积神经网络的多节点间链路预测方法[J]. 舒坚,张学佩,刘琳岚,杨志勇. 电子学报. 2018(12)
[10]基于边重要度的矩阵分解链路预测算法[J]. 郭丽媛,王智强,梁吉业. 模式识别与人工智能. 2018(02)
本文编号：3366238
本文链接：https://www.wllwen.com/kejilunwen/yysx/3366238.html
