| 基于证据理论的多关系网络重要节点挖掘方法 |
| 来源：一起赢论文网 日期：2022-01-30 浏览数：815 【 字体： 大 中 小 大 中 小 大 中 小 】 |
|
第４３ 卷 第１２ 期２０２０ 年１２月计 算机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．４３Ｎｏ．１２Ｄｅｃ．２０２０基于证据理论的多关系网络重要节点挖掘方法罗 浩 闰光辉 张 萌 包峻波 李俊成 刘 婷（ 兰州交通大学电子与信息工程学院 兰州 ７３００７０）摘 要 多关系网络作为现实世界建模的典型形式， 已成为当前网络科学领域研究的热点． 挖掘网络中的重要节点作为复杂网络分析领域的基本问题， 是理解复杂网络结构和动力学特性的有效方式． 关于单关系复杂网络中重要节点的研究已经形成了较为完备的方法框架， 但对于多关系网络中重要节点研究缺乏系统性的研究成果， 尝试推广已有的重要节点挖掘方法到多关系网络已成为当前研究的热点问题之一． 本文综合考虑中心性和传递性对节点重要程度的影响， 对无权无向多关系网络中的重要节点挖掘问题进行了系统研究． 首先， 通过建立多层网络模型对多关系网络进行描述， 并构造多层邻接矩阵对其进行表示． 其次， 按照多层网络节点局部聚集系数的概念， 给出了刻画网络传递性的多关系网络节点局部聚集系数的计算方法． 在此基础上， 结合多关系网络节点的度中心性，推广单关系网络的ＣｌｕｓｔｅｒＲａｎｋ 重要节点度量指标到多关系网络， 提出了多重ＣｌｕｓｔｅｄＲａｎｋ（ＭｕｌｔｉｐｌｅｘＣｌｕＳｔｅｒＲａｎｋ， ＭＣＲ） 指标． 考虑到多关系网络耦合信息和传递机制的差异性会对节点重要程度的度量产生影响， 多重ＣｌｕｓｔｅｒＲａｎｋ指标在规模较大的网络中可能会存在计算误差， 从而影响度量重要节点的准确性， 因此引人Ｄ－Ｓ证据理论对多重ＣｌｕｓｔｅｒＲａｎｋ 进行改进， 将节点的度中心性和局部聚集系数进行融合， 提出了更为高效的多重证据中心性（ＭｕｌｔｉｐｌｅｘＥｖｉｄｅｎｔｉａｌＣｅｎｔｍｌｉ ｔｙ， ＭＥＣ）重要节点挖掘方法．最后， 在４个真实数据集上进行了大量实验， 并从鲁棒性和脆弱性、 传播动力学特性两方面对所提出的方法进行了评价． 实验结果表明， 多重证据中心性所得到重要节点度量结果要优于只关注网络结构的度中心性和特征向量中心性所得到的重要节点度量结果， 而多重Ｃｌｕｓｔｅｒ－Ｒａｎｋ在规模较大的网络中确实会存在计算误差， 难以准确挖掘网络中的重要节点． 实验验证了多重证据中心性可以有效消除多关系网络耦合信息和传递机制在重要节点挖掘中的影响， 能够更准确地挖掘网络中的重要节点． 此外， 通过分析各方法的时间复杂度并统计各方法的实际运行时间， 验证了相对于多重Ｃｌ ｕｓｔｅｒＲａｎｋ， 改进后的多重证据中心性具有更低的时间复杂度．本文所做工作对多关系网络重要节点挖掘问题提供了新的思想方法， 并进一步拓展了Ｄ－Ｓ证据理论的应用场景．关键词 多关系网络； 多重网络； 重要节点； 中心性； 传递性； 局部聚集系数； 证据理论中图法分类号ＴＰ１８１ＤＯＩ号１０．１ １８９７／ＳＰ．Ｊ．１０１６．２０２０．０２３９８ＩｄｅｎｔｉｆｙｉｎｇＩｍｐｏｒｔａｎｔＮｏｄｅｓｉｎＭｕｌｔｉ－ＲｅｌａｔｉｏｎａｌＮｅｔｗｏｒｋｓＢａｓｅｄｏｎＥｖｉｄｅｎｃｅＴｈｅｏｒｙＬＵＯＨａｏＹＡＮＧｕａｎｇ－ＨｕｉＺＨＡＮＧＭｅｎｇＢＡＯＪｕｎ－ＢｏＬＩＪｕｎ－ＣｈｅｎｇＬＩＵＴｉ ｎｇ（． Ｓｃｈｏｏｌ ｏｆＥｌ ｅｃｔ ｒｏｎｉｃａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇｔＬａｎｚｈｏｕＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉ ｔｙｆＬａｎｚｈｏｕ７３００７０）ＡｂｓｔｒａｃｔＡｓａｔｙｐｉｃａｌｍｏｄｅｌｏｆｔｈｅｒｅａｌｗｏｒｌｄ，ｔｈｅｍｕｌ ｔｉ－ｒｅｌａｔｉｏｎａｌｎｅｔｗｏｒｋｈａｓｂｅｃｏｍｅｏｎｅｏｆｈｏｔｔｏｐｉｃｓｉ ｎｔｈｅｆｉｅｌ ｄｏｆｎｅｔｗｏｒｋｓｃｉ ｅｎｃｅ．Ｉｄｅｎｔｉ ｆｙｉ ｎｇｉ ｍｐｏｒｔａｎｔｎｏｄｅｓｉ ｓｏｎｅｏｆｔｈｅｆｕｎｄａｍｅｎｔａｌｐｒｏｂｌ ｅｍｏｆｎｅｔｗｏｒｋａｎａｌｙｓｉｓ，ｗｈｉｃｈｉｓｅｓｓｅｎｔｉａｌｔｏｕｎｄｅｒｓｔａｎｄｔｈｅｓｔｒｕｃｔｕｒｅａｎｄｄｙｎａｍｉｃｃｈａｒａｃ？ｔｅｒｉ ｓｔｉｃｓｏｆｔｈｅｃｏｍｐｌｅｘｎｅｔｗｏｒｋｓ．Ｌｏｔｓｏｆｅｘｃｅｌ ｌｅｎｔｓｔｕｄｉｅｓｃａｒｒｉｅｄｏｎｔｈｅｉ ｍｐｏｒｔａｎｃｅｏｆｎｏｄｅｓｉ ｎａｓｉ ｎｇｌｅ－ｒｅｌａｔｉ ｏｎａｌｎｅｔｗｏｒｋ，ｂｕｔｔｈｅｒｅｓｅａｒｃｈｏｎｉ ｍｐｏｒｔａｎｔｎｏｄｅｓｉ ｎｍｕｌｔｉ－ｒｅｌａｔｉｏｎａｌｎｅｔｗｏｒｋｓ收稿日期：２０１９－０９ ０５； 在线发布日期：２０２０－０２－１６． 本课题得到国家自然科学基金（ ６２０６２０４９） 、教育部人文社会科学研究青年基金（ ２０ＹＪＣＺＨ２ １２） 和甘肃省自然科学基金（ ２０ＪＲ５ＲＡ３９０） 资助． 罗 浩， 博士研究生， 中国计算机学会（ＣＣＦ） 会员， 主要研究方向为数据挖掘和复杂网络分析． Ｅ－ｍａｉｌ：ｌ ｕｏｈ３８２＠ｆｏｘｍａｉｌ．ｃｏｍ．闫光辉（ 通信作者）， 博士， 教授， 中国计算机学会（ ＣＣＦ） 会员， 主要研究领域为数据库理论与系统、物联网工程与应用、 数据挖掘、复杂网络分析等． Ｅ－ｍａｉｌ ：ｙａｎｇｈａｃａｄｅｍｉｃ＠１６３． ｃｏｍ． 张 萌， 硕士，主要研究方向为数据挖掘和复杂网络分析． 包峻波， 硕士， 主要研究方向为数据挖掘和复杂网络分析． 李俊成， 硕士， 主要研究方向为数据挖掘和复杂网络分析．刘 婷， 硕士， 主要研究方向为数据挖掘和信息安全．１２ 期罗 浩等： 基于证据理论的多关系网络重要节点挖掘方法２３９９ｌａｃｋｓｓｙｓｔｅｍａｔｉｃｒｅｓｅａｒｃｈ．Ｔｒｙｉｎｇｔｏｅｘｐｌｏｒｅａｎｄｅｘｔｅｎｄｔｈｅｅｘｉ ｓｔｉ ｎｇｍｅｔｈｏｄｓｉ ｎｓｉ ｎｇｌ ｅｎｅｔｗｏｒｋｓｔｏｍｕｌ ｔｉ－ｒｅｌａｔｉ ｏｎａｌｎｅｔｗｏｒｋｓｈａｓｂｅｃｏｍｅｏｎｅｏｆｔｈｅｈｏｔｉｓｓｕｅｓ．Ｆｏｒｍｕｌ ｔｉ－ｒｅｌａｔｉｏｎａｌ ｎｅｔｗｏｒｋｓ，ｔｈｉｓｐａｐｅｒｆｏｃｕｓｅｄｏｎｔｈｅｓｔｕｄｙｏｆｔｈｅｉｄｅｎｔｉｆｙｉ ｎｇｉ ｍｐｏｒｔａｎｃｅｎｏｄｅｓｃｏｎｓｉ ｄｅｒｉ ｎｇｔｈｅｉｎｆｌ ｕｅｎｃｅｏｆｃｅｎｔｒａｌｉ ｔｙａｎｄｔｒａｎｓｉｔｉｖｉ ｔｙ．Ｗｅｃｒｅａｔｅｄｔｈｅｍｕｌ ｔｉｌａｙｅｒｎｅｔｗｏｒｋｍｏｄｅｌｔｏｄｅｓｃｒｉｂｅａｍｕｌｔｉ－ｒｅｌａｔｉｏｎａｌｎｅｔｗｏｒｋａｎｄｕｓｅｄｔｈｅｍｕｌｔｉｌａｙｅｒａｄｊａｃｅｎｃｙｍａｔｒｉ ｘｔｏｒｅｐｒｅｓｅｎｔｉｔ．Ｔｏｑｕａｎｔｉｆｙｔｈｅｔｒａｎｓｉ ｔｉｖｉｔｙｉ ｎｍｕｌ ｔｉ－ｒｅｌａｔｉｏｎａｌｎｅｔｗｏｒｋｓ，ｗｅｐｒｏｐｏｓｅｄａｍｅｔｈｏｄｆｏｒｃａｌｃｕｌａｔｉ ｎｇｔｈｅｌ ｏｃａｌｃｌ ｕｓｔｅｒｉｎｇｃｏｅｆｆｉｃｉｅｎｔａｃｃｏｒｄｉｎｇｔｏｔｈｅｎｏｔｉｏｎｏｆｃｌｕｓｔｅｒｉ ｎｇｃｏｅｆｆｉｃｉｅｎｔｆｏｒｍｕｌ ｔｉ ｌａｙｅｒｎｅｔｗｏｒｋｓ．Ｕｌ ｔｅｒｉｏｒｌｙ，ｗｅｐｒｏｐｏｓｅｄｍｕｌｔｉｐｌｅｘＣｌｕｓｔｅｒＲａｎｋｃｏｍｂｉ ｎｉ ｎｇｔｈｅｍｕｌｔｉｐｌｅｘｄｅｇｒｅｅｃｅｎｔｒａｌ ｉｔｙａｎｄｅｘｔｅｎｄｉ ｎｇＣｌｕｓｔｅｒＲａｎｋｉｎｓｉ ｎｇｌ ｅ－ｒｅｌａｔｉｏｎａｌｎｅｔｗｏｒｋｓｔｏｍｕｌｔｉ－ｒｅｌａｔｉ ｏｎａｌｎｅｔｗｏｒｋｓ．Ｃｏｎｓｉｄｅｒｉｎｇｔｈｅｉ ｎｆｌｕｅｎｃｅｏｆｃｏｕｐｌｉ ｎｇｉ ｎｆｏｒｍａｔｉ ｏｎａｎｄｔｈｅｄｉ ｆｆｅｒｅｎｃｅｏｆｔｒａｎｓｍｉ ｓｓｉｏｎｍｅｃｈａｎｉ ｓｍｆｏｒｍｕｌ ｔｉ－ｒｅｌａｔｉ ｏｎａｌｎｅｔｗｏｒｋｏｎｖｉ ｔａｌｉ ｎｆｏｒｍａｔｉ ｏｎｏｆｎｏｄｅｓ，ｍｕｌ ｔｉｐｌｅｘＣｌ ｕｓｔｅｒＲａｎｋｍａｙｈａｖｅｃａｌ ｃｕｌａｔｉ ｏｎｅｒｒｏｒｓｉ ｎｌ ａｒｇｅ－ｓｃａｌｅｍｕｌ ｔｉ－ｒｅｌａｔｉｏｎａｌｎｅｔｗｏｒｋｓ，ｗｈｉｃｈｍａｙａｆｆｅｃｔｔｈｅａｃｃｕｒａｃｙｏｆｍｅａｓｕｒｉ ｎｇｅｓｓｅｎｔｉａｌｎｏｄｅｓ．Ｔｈｅｒｅｆｏｒｅ，ｉ ｎｔｈｉ ｓｗｏｒｋｗｅｉｍｐｒｏｖｅｄｍｕｌｔｉｐｌｅｘＣｌｕｓｔｅｒＲａｎｋａｎｄｐｒｏｐｏｓｅｄａｎｏｔｈｅｒｍｏｒｅｅｆｆｉｃｉｅｎｔｍｅｔｈｏｄｔｏｉ ｄｅｎｔｉ ｆｙｖｉ ｔａｌｎｏｄｅｓｆｏｒｍｕｌｔｉ－ｒｅｌａｔｉｏｎａｌｎｅｔｗｏｒｋｓｎａｍｅｄｍｕｌｔｉｐｌｅｘｅｖｉ ｄｅｎｔｉａｌｃｅｎｔｒａｌ ｉｔｙ，ｗｈｉ ｃｈｆｕｓｅｄｔｈｅｎｏｄｅｄｅｇｒｅｅｃｅｎｔｒａｌｉｔｙａｎｄｌｏｃａｌｃｌ ｕｓｔｅｒｉ ｎｇｃｏｅｆｆｉｃｉｅｎｔｂｙｔｈｅＤｅｍｐｓｔｅｒ－Ｓｈａｆｅｒｅｖｉｄｅｎｃｅｔｈｅｏｒｙ．Ｎｕｍｅｒｏｕｓｅｘｐｅｒｉｍｅｎｔｓｗｅｒｅｃａｒｒｉｅｄｏｕｔｏｎｆｏｕｒｒｅａｌｎｅｔｗｏｒｋｓ．Ｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｉｓｅｖａｌ ｕａｔｅｄｆｒｏｍｔｗｏａｓｐｅｃｔｓ：ｒｏｂｕｓｔｎｅｓｓａｎｄｖｕｌｎｅｒａｂｉ ｌ ｉ ｔｙ＊ｔｒａｎｓｍｉ ｓｓｉｏｎｄｙｎａｍｉ ｃｓｃｈａｒａｃｔｅｒｉ ｓｔｉ ｃｓ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌ ｔｓｓｈｏｗｔｈａｔｍｕｌ ｔｉｐｌ ｅｘｅｖｉ ｄｅｎｔｉａｌｃｅｎｔｒａｌ ｉｔｙｃａｎｇｅｔｂｅｔｔｅｒｒｅｓｕｌ ｔｓｔｈａｎｍｕｌ ｔｉｐｌｅｘｄｅｇｒｅｅｃｅｎｔｒａｌｉｔｙａｎｄｍｕｌ ｔｉｐｌ ｅｘｅｉｇｅｎｖｅｃｔｏｒｃｅｎｔｒａｌｉｔｙｗｈｉｃｈｏｎｌｙｆｏｃｕｓｏｎｔｈｅｓｔｒｕｃｔｕｒｅｏｆｍｕｌ ｔｉｐｌｅｘｎｅｔｗｏｒｋｓａｎｄｍｕｌｔｉｐｌ ｅｘＣｌ ｕｓｔｅｒＲａｎｋｄｏｅｓｈａｖｅｃａｌ ｃｕｌａｔｉ ｏｎｅｒｒｏｒｓｉｎｌ ａｒｇｅ－ｓｃａｌｅｎｅｔｗｏｒｋｓ，ｍａｋｉ ｎｇｉ ｔｄｉｆｆｉｃｕｌ ｔｔｏｉ ｄｅｎｔｉｆｙｉｍｐｏｒｔａｎｔｎｏｄｅｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｖｅｒｉｆｉｅｄｍｕｌ ｔｉｐｌｅｘｅｖｉｄｅｎｔｉａｌｃｅｎｔｒａｌｉｔｙｃａｎｅｆｆｅｃｔｉ ｖｅｌｙｅｌｉ ｍｉ ｎａｔｅｔｈｅｉ ｎｆｌ ｕｅｎｃｅｏｆｔｈｅｃｏｕｐｌｉ ｎｇｉｎｆｏｒｍａｔｉｏｎａｎｄｔｈｅｔｒａｎｓｍｉ ｓｓｉｏｎｍｅｃｈａｎｉ ｓｍｉ ｎｍｕｌｔｉ－ｒｅｌａｔｉ ｏｎａｌ ｎｅｔｗｏｒｋｓ，ａｎｄｈａｓｌｏｗｅｒｔｉ ｍｅｃｏｍｐｌｅｘｉｔｙｔｈａｎｍｕｌｔｉｐｌｅｘＣｌ ｕｓｔｅｒＲａｎｋ．Ｉｎｔｈｉｓｐａｐｅｒ ， ｗｅｎｏｔｏｎｌｙｐｒｏｖｉ ｄｅｎｅｗｉ ｄｅａｓａｎｄｍｅｔｈｏｄｓｆｏｒｉ ｄｅｎｔｉｆｙｉ ｎｇｃｒｉｔｉ ｃａｌｎｏｄｅｓｆｏｒｍｕｌｔｉ－ｒｅｌａｔｉ ｏｎａｌｎｅｔｗｏｒｋｓｂｕｔａｌｓｏｅｘｐａｎｄｓｔｈｅａｐｐｌｉｃａｔｉｏｎｏｆｉ ｎｆｏｒｍａｔｉ ｏｎｆｕｓｉ ｏｎｔｅｃｈｎｏｌｏｇｙ．Ｋｅｙｗｏｒｄｓｍｕｌｔｉ－ｒｅｌ ａｔｉｏｎａｌｎｅｔｗｏｒｋ；ｍｕｌ ｔｉｐｌ ｅｘｎｅｔｗｏｒｋ；ｉ ｍｐｏｒｔａｎｔｎｏｄｅｓ；ｃｅｎｔｒａｌ ｉｔｙ；ｔｒａｎｓｉ ｔｉ ｖｉ ｔｙ；ｌｏｃａｌｃｌ ｕｓｔｅｒｉ ｎｇｃｏｅｆｆｉ ｃｉ ｅｎｔ；ｅｖｉ ｄｅｎｃｅｔｈｅｏｒｙｉ 引 言近年来， 随着复杂网络分析技术的迅猛发展， 人们对现实世界中广泛存在的复杂系统已经有了从宏观到微观的递进认识． 节点作为微观层面的基本单元， 在现实网络中往往扮演着不同角色［１ ２］， 挖掘网络中的重要节点已成为复杂网络分析的基本问题之一． 迄今发展起来的理论框架主要是面向单个网络结构． 单个网络结构是一种简化的网络科学研究模型， 而现实世界中相互关联、彼此依存的复杂系统普遍存在， 刻画此类复杂系统的网络结构称之为网络的网络（ ＮｅｔｗｏｒｋｓｏｆＮｅｔｗｏｒｋｓ， ＮｏＮ） ． 相伴大数据时代的到来， ＮｏＮ逐渐成为网络科学领域富有挑战性的前沿课题［３］． 多关系网络（ ｍｕｌ ｔｉ－ｒｅｌａｔｉ ｏｎａｌｎｅｔｗｏｒｋｓ） 作为ＮｏＮ的一种典型形态， 从复杂网络分析的角度出发， 尝试发展理论框架来研究多关系网络， 并大量推广已有复杂网络分析方法到多关系网络具有重大理论意义和现实意义．现阶段， 国内外学者针对多关系网络的研究进行了一些探索， 对于多关系网络的建模和表示， 相对理想的方法是建立多层网络模型． 国外学者已针对多层网络模型， 提出了相关度量指标和分析方法， 形成了较为完整的理论框架， 为多关系网络的研究奠定了理论基础． 但在实际应用层面， 面向多关系网络进行重要节点挖掘尚缺少成熟的方法框架． 因此， 针对多关系网络的结构和动力学特点， 设计相应的重要节点挖掘方法已成为当前节点重要性研究的重要任务．本文针对无权无向多关系网络重要节点挖掘问题， 通过建立多层网络模型对其进行表示， 综合考虑节点中心性和传递性， 提出了多重ＣｌｕｓｔｅｒＲａｎｋ２４００ 计 算机 学 报 ２０２０年（ ＭｕｌｔｉｐｌｅｘＣｌ ｕｓｔｅｒＲａｎｋ， ＭＣＲ） 指标． 考虑到多关系网络传递机制和关系间信息的差异性， 引人Ｄ－Ｓ证据理论将多关系网络节点的度中心性和局部聚集系数进行信息融合， 提出了多重证据中心性（Ｍｕｌ ｔｉｐｌｅｘＥｖｉｄｅｎｔｉａｌＣｅｎｔｒａｌ ｉ ｔｙ， ＭＥＣ） ． 通过４个真实网络的实验结果表明， 由于多层网络传递机制差异性较强，节点的中心性和传递性不具备相关性， 采用传统ＣｌｕｓｔｅｒＲａｎｋ方法简单融合的多重Ｃｌ ｕｓｔｅｒＲａｎｋ， 会造成节点部分信息的损失． 而采用Ｄ－Ｓ证据理论进行融合的多重证据中心性可以有效消除节点传递机制对节点重要程度造成的影响， 相比于只考虑结构中心性的度中心性方法而言， 能够更加准确地挖掘多关系网络中的重要节点， 特别是在大规模网络的重要节点挖掘中， 其准确度高于其它方法．本文的主要贡献如下：（１） 参考多层网络局部聚集系数的概念和计算方法， 对多关系网络进行了抽象和简化， 给出了多关系网络局部聚集系数的计算方法；（２） 针对无权无向多关系网络， 统筹考虑节点的中心性和传递性， 提出了多重ＣｌｕｓｔｅｒＲａｎｋ度量方法， 并对多关系网络节点的度中心性和局部聚集系数的相关关系进行了研究， 验证了“由于受多层网络传递机制和层间信息的影响， 二者不具备相关性，若直接扩展单层网络Ｃｌ ｕｓｔｅｒＲａｎｋ的思想方法到多关系网络， 会对重要节点度量指标的准确度造成影响 的猜想；（３） 针对多重ＣｌｕｓｔｅｒＲａｎｋ存在的缺陷， 进一步引人Ｄ－Ｓ证据理论， 将节点的度中心性和局部聚集系数融合， 提出了节点多重证据中心性的度量方法，实验结果表明， 该方法可以消除多层网络传递机制和层间信息差异性对测量节点重要程度的影响， 相比于单纯关注中心性的度中心性， 综合考虑中心性和传递性的多重证据中心性能够更加精准地挖掘多关系网络中的重要节点， 使得多层网络的度量指标和Ｄ－Ｓ证据理论在挖掘重要节点的实际应用中得以扩展．２ 相关工作２．１多关系网络的表示对多关系网络开展研究， 首要问题是建立合适的模型和表示方法． 鉴于目前在单个网络上已经建立了较为成熟的分析框架， 对多关系网络的简单处理思路是采用“降维”思想， 围绕特定领域网络， 运用社会学、可拓学等其它学科的理论， 通过构建加权网络的方式将多关系网络转化为单关系网络［４ ５］； 或是借助矩阵分解、多子网复合等理论方法对已有网络进行时间划分或快照处理， 对单个网络分别研究后再进行复合［６ ７］． 然而， 通过降维转化为单关系网络的处理方法， 会丧失原始数据中所含的特定结构信息， 以及不同类型关系之间的关联信息， 不利于后续研究的开展． 此外， 还有一些研究围绕“全连通网络”， 运用超图理论展开分析Ｗ， 该类研究虽能够对网络进行融合， 保留了信息的完整性， 但“超图”模型通常只适用于刻画“全连通网络”， 局限性较强．在计算机科学和计算机线性代数领域， 研究者们运用张量分解（ ｔｅｎｓｏｒｄｅｃｏｍｐｏｓｉｔｉｏｎ）［８＿９］和多路数据（ｍｕｌ ｔｉ ｗａｙｄａｔａ） 分析［１ °］的方法研究了不同类型的多层网络． 在物理学领域， 物理学家们围绕多层网络（ ｍｕｌｔｉ ｌａｙｅｒｎｅｔｗｏｒｋｓ、 网络的网络（ ＮｅｔｗｏｒｋｓｏｆＮｅｔｗｏｒｋｓ，ＮｏＮ）［１ ５－１ ６］和节点着色网络（ ｎｏｄｅ－ ｃｏｌｏｒｅｄｎｅｔｗｏｒｋｓ） ， 已经做了许多重要的基础性工作． Ｂｏｃｃａｌｅｔｔｉ 等人［１７］于２０１４年首次提出了多层网络的基本数学定义， 该定义统一了迄今文献上关于多层网络的不同提法． 经过近几年的发展，多层网络模型已逐渐成熟， 形成了一些符合复杂网络基本特征和动力学机制的理论方法， 为后续研究提供了理论工具． 针对多关系网络， 可将每一类关系映射到一个网络层上， 同时考虑各类关系间的交互信息， 构建多层网络开展研究． 因此， 多层网络模型是表示多关系网络的理想形式， 将多层网络模型运用到多关系网络中， 在应用层面进行拓展， 是值得深人研究的一个问题．２． ２ 重要节点度量指标结构中心性和传递性是衡量节点重要程度的重要因素． 在单个网络的重要节点研究方面， 已经有了较完备和丰富的度量指标方法挖掘网络中的重要节点［１ ８］． 根据网络的局部特性划分， 可分为全局中心性、局部中心性、半局部中心性３ 类． 全局中心性的经典指标有介数中心性（ ＢｅｔｗｅｅｎｎｅｓｓＣｅｎｔｒａｌｉ ｔｙ，ＢＣ）［Ｉ ９］、 接近中心性（ＣｌｏｓｅｎｅｓｓＣｅｎｔｒａｌｉ ｔｙ， ＣＣ）〔２。］、特征向量中心性（ＥｉｇｅｎｖｅｃｔｏｒＣｅｎｔｒａｌｉｔｙ，ＥＣ）［２１］等， 局部中心性有度中心性（ ＤｅｇｒｅｅＣｅｎｔｒａｌｉｔｙ，ＤＣ）［２１］． 为平衡全局中心性的复杂度和局部中心性因素的单一性， Ｃｈｅｎ等人「 ％提出了一种半局部中心性（ Ｓｅｍｉ－ＬｏｃａｌＣｅｎｔｒａｌ ｉ ｔｙ， ＳＬＣ ） ， 通过考虑节点１２期 罗 浩等： 基于证据理论的多关系网络重要节点挖掘方法 ２４０１的４ 阶邻居信息来度量节点重要程度， Ｇａｏ等人２３在其基础上通过引入Ｄ－Ｓ 证据理论， 提出了一种证据半局部中心性（ ＥｖｉｄｅｎｔｉａｌＳｅｍｉ－ｌ ｏｃａｌＣｅｎｔｒａｌｉｔｙ，ｅｓｃ） ， 但两者都只关注了中心性， 而忽略ｒ传递性在度量重要节点中的关键作用． Ｃｈｅｎ 等人＆综合考虑了二阶邻居和局部集聚特性， 提出了Ｃｌ ｕｓｔｅｒＲａｎｋ指标． 该指标在运行效率和准确度上都要优于前者．２．３多层网络的度量指标面向多层网络， 如何借用已有的物理量去描述其基本拓扑结构和性质还面临巨大的挑战， 将单个网络中已有的成熟工具和方法扩展到多层网络领域成为当前复杂网络研究的一大热门方向． 最初的做法是将不同网络层的节点和连边以不同权重的方式进行合并， 从而将多层网络转化成为单层网络， 再利用传统物理量分析网络的各种结构属性． 这种方法虽然简单， 但存在很多问题， 因为在将多层网络合并成单层网络时，一些不同网络层之间的重要信息会全部丢失， 同时还存在如何设定各种权重的Ｈ题Ｍ． 因此， 发现一套适合多层网络理论框架的必要性开始凸显， 国内外学者围绕设计多层网络的度量指标做了大量研究工作， 也取得了一些成果， 多层网络的中心性、 路径长度、 聚集系数等概念被相继提出， 为后续研究奠定了基础． 与单层网络的度量指标不同， 多层网络的一些度Ｍ指标是在特定条件和应用场景下提出的， 尚未形成像单层网络众多经典方法一样的公认指标． 值得一提的是， Ｂａｔｔｉｓｔｏｎ等人＞］在向量的基础上提出的多层网络节点度（ｄｅｇｒｅｅ）、 节点强度（ ｓｔｒｅｎｇｔｈ） 以及Ｃ〇ＺＺ〇等人［２７基于多层网络的传递性提出的多层网络聚集系数的概念都是从多层网络的基本性质和动力学特性出发的， 具有一定的普适性， 成为目前比较经典的多层网络度量方法． 特别是在节点的传递性方面， 在实际数据集上的实验分析表明， 在社会网络和交通网络中层内聚集性和层间聚集性的差异是不同的， 这实际上反映了在这些网络中节点传递性的起源机制大不一样． 他们提供的聚集系数定义表达式为不同类型的网络传递性研究提供了新的思路．３ 基本概念３． １多关系网络的矩阵表示按照Ｂｏｃｃａｌｅｔｔｉ 等人［１ ７］提出的多层网络定义，多关系网络可用一种特殊的多层网络进行构建， 称之为多重网络（ Ｍｕｌ ｔ ｉｐｌｅｘＮｅｔｗｏｒｋ）， 其唯一的层间连接模式是来自不同层对应节点之间的连接．图１ 描述了具有１０个节点， ３ 个网络层的多层网络和多重网络示意图．一般地， 对于Ｎ个节点， ＪＷ层的无权无向多关系网络， 可用ＭＪＶＸｉＷＮ的邻接矩阵进行表示， 这对于计算算法的实现是十分有用的． 进一步， 可根据连接方式的不同将多关系网络分解为层内网络和层间网络， 分别用层内邻接矩阵和层间邻接矩阵进行表示：２８］， 定义如下．定义１． 层内邻接矩阵． 多关系网络第＾类关系所对应的层内连接可由一个邻接矩阵来表示，记为 ， 则多关系网络的层内邻接矩阵定义为ＡＭ，＝？ＡＭｅＲＭＶ＞＜ ＭＮ（１ ）ｉ－ｌ１．２Ｌ３（ ａ ） 多层网络 （ｂ） 多重网络Ｌ２Ｕ１＊１１多Ｗ网络￣多ｆｉ 网络原理图定义２． 层间邻接矩阵． 多关系网络所对应的层间连接可由一个加权邻接矩阵来表示， 记为州６ＫＭＸ Ｍ， 取单位矩阵／、 ， （．６＇则多关系网络的层间邻接矩阵定义为ｗＭＣ＝ｖｙｔ－？ｉＭｃｅｍｍ，ｖｘｍｖ（２）根据层内邻接矩阵和层间邻接矩阵．可以很方便地得到多关系网络的邻接矩阵．定义３． 多关系网络的邻接矩阵． 令ＡＭ， 为多关系网络层内邻接矩阵， 为层间邻接矩阵， 则多关系网络的邻接矩阵：（３）３． ２ 多关系网络的度中心性根据Ｂａｔｔｉｓｔｏｎ等人［２６］提出的多层网络节点度和节点强度的概念， 可得到多关系网络节点的度中心性（ Ｍｕｌｔｉｐｌ ｅｘＤｅｇｒｅｅＣｅｎｔｒａｌｉｔｙ， ＭＤＣ） 定义．定义４． 多关系网络节点的度中心性． 假设多关系网络ＧＭ＝（Ｖ， ￡Ｍ） 包含Ｍ种关系， 节点数为ＪＶ， 则节点从ｅｖ（ｉ＝ｌ，２，…， Ｎ）的度中心性向量可表示为： 《，＝（ ／＜：；１］， 尺；２：，一， 尺严）， 其中］＜：：°］为节点％在层ａ 中的度， 定义为２４０２计 算机 学 报２０２０ 年⑷１ｉ＞进一步， 我们可以在多关系网络上得到相应的节点度、平均度、 度的二阶矩的定义．节点度（ ｎｏｄｅｄｅｇｒｅｅ）：Ｋ，＝２Ｋ，Ｕ（５）ａ平均度（ ｍｅａｎｄｅｇｒｅｅ） ：〈／０＝十（ ６）度的二阶矩（ ｔ ｈｅｓｅｃｏｎｄｍｏｍｅｎｔｏｆｔｈｅｄｅｇｒｅｅ） ：２（ 氏）２（７）３． ３ 多关系网络的局部聚集系数Ｃｏｚｚｏ 等人［２７］从路径和环的概念出发， 提出了多层网络局部聚集系数和全局聚集系数的概念． 在单层网络中， 可用邻接矩阵来计算网络中路径和环的数量［２９－抝类似地， 将多层网络中的行走称之为“超行走（ ｓｕｐｒａ－ｗａｌ ｋ）”， 并通过层内邻接矩阵和层间邻接矩阵来计算多层网络的聚集系数． 按照Ｃ〇ＺＺ〇 等人提出的多层网络聚集系数的计算方法，本文给出了多关系网络局部聚集系数（ Ｍｕｌ ｔｉｐｌ ｅｘＬｏｃａｌＣｌｕｓｔｅｒｉ ｎｇＣｏｅｆｆｉｃｉｅｎｔ ， ＭＬＣＣ） 的概念和计算方法． 由３．１节？知， 本文运用多ｒＲ网络模铟来表示多关系网络， 则在多关系网络１丨１， 通过“超行走”得到的三元闭环有且仅有阁２ 所示的５ 种基本形式， 其中较大节点代灰闭环的起始Ｗ点， Ｓ内路径用实线表示， 层间路径用虚线表示， 较机实线代表层内第二步行走路径． 通Ｈ“超行走”所构成的三元闭环可通过将各网络层聚合到一层得到， 由此可得到多关系网络节点聚集系数的定义．（ ａ）ＩＩＩ（ｂ）／／Ｃ／Ｃ（ｃ）／ＣＨＣ（ｄ）ＩＣＩＣＩ（ ｅ） ＩＣＩＣＩＣ图２ 多关系网络基本闭环结构示意图定义５． 多关系网络的局部聚集系数． 令Ｍ，Ｊ， Ｃ分别表示多关系网络的邻接矩阵、 层内邻接矩阵、层间邻接矩阵，１２＝＜ｉ／／，ＩＩＣＩＣ，ＩＣＩＩＣ，ＩＣＩＣＩ，ＩＣＩＣＩＣ｝为多关系网络中基本三元闭环结构集合，￥ 为集合■ ０ 中的元素，０＝｛／／＇／．ＩＦＣＩＣ，ＩＣＦＩＣ．１ＣＦＣＩ．１ＣＦＣＩＣ｝为在构成基本？： 允闭环结构的“超行走”过程中， 层内第２ 步发生在一个完全图上的闭环结构集合． 其网络的邻接矩阵ｄ表示ｈ屮的元桌． 则多关系网络节点ａ的局部聚集系数可定义为㈦？（４）“Ｃｍ．，＝—（８）Ｉ＞ｃ： （心＂ｅｅｎ式（ ８） 中，＆和％代表“超行走”分别跨越１ 层、２ 层和３ 层所占的贡献， 在无特定背景情况下，一般设ＣＯｆ＝＝１／３？３． ４Ｉ）－Ｓ证据理论Ｄｅｍｐｓｔ ｅｒ 和Ｓｈａｆｅｒ 建立的Ｄ－Ｓ证据理论， 是在概率论基础上扩展的１ 套数学理论， 适用于人工智能、 模式识别等领域的实际问题． Ｄ－Ｓ证据理论涉及确定辨识框架（ ｆｒａｍｅｏｆｄｉｓｃｅｒｎｍｅｎｔ）？ 计算基本概率指派（ ＢａｓｉｃＰｒｏｂａｂｉｌｉｔｙＡｓｓｉｇｎｍｅｎｔ．ＢＰＡ） 以及证据合成等基本流程． 本节简要介绍其基本概念和合成方法［３１］．定义６．辨识框架． 在Ｄ－Ｓ 证据理论中， 所考察判断的事物（ 或对象）的全体可用一个由」Ｖ个两两互斥元素组成的有限完备集合来表示， 称之为辨识框架（ 或称为假设空间）． 记为平＝｛０１，办，…，０．Ｖ ｝？少的幂集２＇＂记为２＾＝｛ ０ ，…， 如， ，？ ＂， 平）？定义７． 基本概率指派． 设少为辨识框架， 少的幂集２＂构成命题集合， 对于 少， 若函数２＇＾？［０， １］满足以下两个条件：（ｍ（０）—〇＾＾（ ９）｛ｙ］／ｗ（Ａ）＝ｌ则称ｍ为基本概率指派， ｗｚ（Ａ） 为命题Ａ的基本概率数， 被视为准确分配给Ａ的信度．罗 浩等： 基于证据理论的多关系网络重要节点挖掘方法 ２４０３ １ ２ 期定义８．Ｄｅｍｐｓｔｅｒ－Ｓｈａｆｅｒ 组合规则． 设；？ 和所２ 为２ 组基本概率指派， 对应的命题分别为ＡｍＡ２，…，Ａｔ 和 丨， ，？＿ ？， 战， 用？ｗ表示所丨 和；？ｚ２ 组合后的新证据， 则Ｄｅｍｐｓｔｅｒ－Ｓｈａｆｅｒ组合规则为ｆ ｍ（０）＝〇，ｍ（Ａ）：ｌ—ｋＡ＾Ｂｉ＝ＡＸ）ｍＡＡｉ）ｍ２（Ｂｉ）（１ ０）其中， 々＝叫（Ａ） 叫（ 战） 称为冲突系数， 用于Ａｉ．ｎＢｉ＝０衡量证据焦元间的冲突程度， 々 越大， 则冲突越大．由式（１０） 可知々关１， 当々＝１ 时， 组合规则无法使用， 即ＢＰＡ存在矛盾．４ 多重证据中心性４． １多重ＣｌｎｓｔｅｒＲａｎｋ度量指标中心性和传递性作为影响节点重要性的主要因素， 可分别用节点的度中心性和局部聚集系数进行度量， 其中节点的度中心性与节点的重要程度呈正相关、节点的局部聚集系数与其重要程度呈负相关．在单个网络中， Ｃｈｅｎ等人Ｍ提出的Ｃｌ ｕｓｔｅｒＲａｎｋ算法同时考虑了中心性和传递性对节点的影响， 取得了较好的度量效果． 根据ＣｌｕｓｔｅｒＲａｎｋ算法的思想， 在多关系网络上进行推广， 首先提出了多重Ｃｌ ｕｓｔｅｒＲａｎｋＣ Ｍｕｌ ｔｉｐｌｅｘＣｌｕｓｔｅｒＲａｎｋ，ＭＣＲ） ．定义９． 多重Ｃｌ ｕｓｔｅｒＲａｎｋ． 在多关系网络Ｇｍ＝（Ｖ， ＥＭ）中， 记？为节点％的度中心性、 ＣＭ？为节点％的局部聚集系数， 令／（＜＾， ，）＝１ ０夂“为（＾．， 的非线性负相关函数， 则节点切的多重ＣｌｕｓｔｅｒＲａｎｋ 度量值为其中，＝＾Ｌ（ＫＬ＾＋１）１（１２）为层《 内， 节点％的二阶邻居节点的连接强度， ｒ， 为节点 二阶邻居节点的集合．４． ２ 多重证据中心性考虑到多关系网络传递机制和层间信息的差异， 猜想节点的中心性和传递性之间可能不具备相关性， 会对多重Ｃｌ ｕｓｔｅｒＲａｎｋ的计算结果造成误差，从而降低评估节点重要程度的准确性．鉴于此， 运用Ｄ－Ｓ证据理论［２３３ ２］对多重Ｃｌ ｕｓｔｅｒ－Ｒａｎｋ指标进行改进， 对节点的度中心性和局部聚集系数进行信息融合， 进而得到多重证据中心性（ ＭｕｌｔｉｐｌｅｘＥｖｉｄｅｎｔｉａｌＣｅｎｔｒａｌｉｔｙ， ＭＥＣ）？ 根据３．４节Ｄ－Ｓ证据理论基本流程， 给出多重证据中心性的计算步骤：①计算相关指标计算节点度中心性向量Ｋ和局部聚集系数向量ＣＭ， 记 和 分别为Ｋ和ＣＭ中对应第￡ 个位置的元素值， 即节点〃， 的度中心性和局部聚集系数．分别计算／（ＣＭ，， ）＝１（Ｔ？ ， 所得结果向量记为Ｆ．统计Ｋ和Ｆ的最大值和最小值， 分别为Ｋｍ， Ｋ，？ ，Ｆｍ， ｊＦ？，． 通常， 关Ｋ，？ 、Ｆｍ关Ｆ？，．②确定节点的辨识框架少简单而言， 网络中的节点要么重要， 要么不重要， 可定义辨识框架平＝｛Ｉ ， ＮＩ｝， 其中Ｉ 表示节点重要， ＮＩ 表示节点不重要， 二者互斥且少为有限完备集合．③构造基本概率指派函数令ｗＫ．丨 （ｉ） 和ｗＫ， Ｎ， ⑴分别为在■下节点■重要和不重要的概率， 和ｍＦ． Ｎ，（ｉ） 分别代表在／（ＣＭ．，＿） 下节点％重要和不重要的概率． 在无特定条件情况下， 通常约定该概率指派服从均匀分布， 则ＢＰＡ函数可分别定义为ｍＫ． ， ⑴＝＼ｋ，－ｋ， ？＼（１３）Ｋｍ￣Ｋ？， ＋２＾ｍＫ， Ｎｌ（ 〇■＼ｋ－ｋｍ＼（１４）ＫＭ—Ｋｍ＋２ｊｕｔｆｎＦ．， ｄ）＝（１５）ＦＭ—Ｆｍ＋２ＸＧ ）■ＦＭ￣Ｆｍ＋２Ｘ（１６）；？和》 的取值对节点排序没有影响， 通常取Ｇ（〇 ＞１） ．④进行Ｄ－Ｓ证据组合首先定义一个新的指标， 记为Ｍ（〇＝ ｛ ７ｎ［（ 〇（１７）根据式（１０）， 可分别计算？ｗ丨（ｉ） 、ｍＮ１（ｉ） 、７＾（￡） ．其中ｗ，（Ｚ＿）表示节点重要的概率， ｍｎｉ（０表示节点不重要的概率， ０表示节点重要或者不重要的概率．⑤计算ＭＥＣ．根据贝叶斯理论， 在无其它先验知识的情况下， 将 的值等可能分配给叫（￡） 和ｍＮＩ（０， 进一步修正节点认重要的概率ＭＫＧ和不重要的概率Ｍｍ（ ｉ） ， 即， ｍｖ（￡）Ｍ，（ 〇＝ｍ１（￡） ＋＾—（ １８）２４０４ 计 算机 学 报２０２０年Ａ＾Ｔｎ］ｉ（ ｆ）—／？ｚＮｊ（ ｆ）ｍ＾｛ｉ）２（１ ９）由式（１８） 和式（１９） 可得， Ｍ，（ ￡ ） 越大， 或者ＭＮ１（ｉ） 越小， 均说明节点＾越重要． 鉴于此， 定义节点认的多重证据中心性为＾ ＭＹＣｉ）—ＭＮＩ （ ￡）＝ｍ］（ｚ）—ｍＮＩ（ｚ）（２０）进一步归一化处理可得：＾ＭＥＣ．ｉ＾ＭＥＣ．ｍｉ ｎ Ｉ ＋＾ＭＥ｛Ｉ ｙＭＥ［．． ｍｉｎＩ（２１）４． ３ 时空复杂度分析多关系网络中， 记节点数为ｔｚ ， 关系数为ｍ．（１） 时间复杂度分析多关系网络度中心性的时间复杂度为〇（ ｍ？） ，节点的局部聚集系数时间复杂度为〇（ ｗ３？３）． 在已知节点度中心性和局部聚集系数的情况下， 多重Ｃｌ ｕｓｔｅｒＲａｎｋ 和多重证据中心性由于综合考虑了中心性和传递性， 故二者的时间复杂度均依赖于度中心性和局部聚集系数， 其中多重Ｃｌ ｕｓｔｅｒＲａｎｋ 由于考虑了节点的一阶邻居信息， 其时间复杂度为０（ ｍ？〈Ｋ＞ ）， 而多重证据中心性将层间信息通过Ｄ－Ｓ证据理论进行了信息融合， 仅关注了节点本身，故其时间复杂度为〇（ ｎ） ． 综合考虑节点度中心性和节点聚集系数的时间复杂度后， 二者的时间复杂度均为Ｏ（Ｗ） ．（２） 空间复杂度分析鉴于通过构建 的邻接矩阵对多关系网络进行表征， 故其空间复杂度为〇（ ｍ？Ｘｍ？） ． 在具体实现过程中， 考虑到邻接矩阵的稀疏性， 采用稀疏矩阵对其进行处理， 可以有效降低多关系网络的空间复杂度．５ 实验与讨论相比于单关系网络， 目前适用于无权无向多关系网络的重要节点挖掘方法相对较少， 多层网络的度中心性是目前公认度比较高的适用于无权无向多关系网络重要节点的经典度量指标．为从运行时间和重要节点度量准确性两方面评测所提出的方法， 验证４．２节提出的“由于受多关系网络传递机制的差异， 节点的中心性和传递性间不具备相关性， 会造成多重Ｃｌ ｕｓｔｅｒＲａｎｋ 的计算误差，从而降低评估节点重要程度的准确性 的猜想， 以及与只关注节点结构的度中心性相比， 融合节点传递性的多重证据中心性更能准确识别网络中的重要节点， 选取了网络类别、网络规模、关系数量、关系类别各不相同的４ 个真实网络数据集进行了５ 组不同实验， 运用重要节点挖掘研究中最常采用的ＳＩＲ传播模型以及鲁棒性和脆弱性方法进行评价． 同时， 除选择多层度中心性作为对比方法外， 另外选取了适用于无权无向网络的多重特征向量中心性（Ｍｕｌ ｔｉｐｌｅｘＥｉｇｅｎｖｅｃｔｏｒＣｅｎｔｒａｌｉｔｙ， ＭＥＶＣ） 作为对比， 用以说明提出算法的有效性． 多重特征向量中心性定义为［３３］Ｍｉ；？０ｉａ＝Ｘｌ ０Ｊ＾（２２）＾ＭＥＶＣ． ｉ ＝０；ｏｍ°（２３）其中 为多层邻接张量， Ａ， 为最大特征值， ０， 。为对应的特征向量， 为元素全为１ 的向量．实验平台为ＩｎｔｅｌＣｏｒｅｉ９－９９００Ｋ３．６ＧＨｚ， ６４ＧＢＲＡＭ， 操作系统为Ｗｉ ｎｄｏｗｓ１０， 代码由Ｐｙｔｈｏｎ实现．选取数据集分别为ＣＫＭＰｈｙｓｉｃｉａｎｓＩｎｎｏｖａｔｉｏｎ［３ ４］、ＣＳＡａｒｈｕｓ［３５＼ＥＵＡｉｒＴｒａｎｓｐｏｒｔａｔｉｏｎ１ －３６１，ＭｏｓｃｏｗＡｔｈｌｅｔｉｃｓ２０１ ３［３７］， 数据集的基本统计信息如表１所示．表１ 实验数据集基本统计倍息数据集名称 层数 节点数 边数 网络类型 平均度 度的二阶距ＣＫＭＰｈｙｓｉｃｉａｎｓＩ ｎｎｏｖａｔ ｉｏｎ ３ ２４６ １ ５５ １ 社会网络 １８．６０４０５．４０ＣＳＡａｒｈｕｓ５ ６１ ６２０ 社会网络 ４０．３３ １７５２．２０ＥｕＡｉｒＴｒａｎｓｐｏｒｔ ａｔｉｏｎ３７ ４５０ ３５８８ 交通网络 １３４７．９４ １．８Ｘ１０６ＭｏｓｃｏｗＡｔｈｌ ｅｔｉｃｓ２０１３ ３ ８８ ８０４ ２１０２５０ 社会网络 １０．６９ ３ ２８６．２３５． １ 运行时间评价通过统计４个真实网络数据集上各算法的实际运行时间， 来比较提出方法的运行速率． 记ｔＫ， ｋ，＾ＭＣＵ＾ＭＥＣ 分别为多关系网络中计算度中心性、 局部聚集系数、多重ＣｌｕｓｔｅｒＲａｎｋ、 多重证据中心性和特征向量中心性的运行时间． 根据４．３ 节对各算法的时间复杂度分析可知， 多重ＣｌｕｓｔｅｒＲａｎｋ和多重证据中心性的运行时间依赖于ｋ和Ｌ， 即＾ＭＣＲ＿之Ｋ＋ｋ＋ｆＭＣＨ（２４）＾ＭＥＣ—（Ｋ＋，Ｌ ＋丨ＭＥＣ（２５）其中， ４ｃＲ和心Ｃ分别为单独计算多重ＣｌｕｓｔｅｒＲａｎｋ和多重证据中心性的运行时间．罗 浩等： 基于证据理论的多关系网络重要节点挖掘方法 ２４０５１２ 期由于４ 个网络规模不同， 我们通过统计各方法运行时间占总运行时间的比重， 来说明算法运行时间的长短， 即Ｐ ⑴＾（２６）５ 种方法在４个网络上的运行时间统计结果如图３ 所示， 可以看出， 在整个运行过程中， 度中心性和特征向量中心性的计算时间很短， 基本可以忽略不计， 计算局部聚集系数的运行时间相对较长， 在计算多電Ｃｌ ｕｓｔｅｒＲａｎｋ和多重证据中心性的过程中，主要时间消耗在计算局部聚集系数的环节上， 而总ＤａｔａＳｅｔＭｅｔ ｈｏｄ■ＭＬＣＣ一ＭＥＶＣＭＥＣＭＤＣＭＣＲ图３ 各方法运行时间统计图体运行时间和局部聚集系数的运算时间差异不大．图４ 显示了４ 个网络中以＾和．的运行时间统计， 可以看到， 在单独计算二者的运行时间上， 多重证据中心性要比多重Ｃｌ ｕｓｔｅｒＲａｎｋ 用时少得多．综上， 实验结果与４． ２ 节中时间复杂度的分析结论是一致的， 在运行时间上， 多重证据中心性要优于多重Ｃｌ ｕｓｔｅｒＲａｎｋ．ＤａｔａＳｅｔ图４ＭＣＲ和ＭＥＣ运行时间统计图５． ２ 度量准确性评价表２ 列出了在４ 个真实网络数据集中， 运用４ 种方法分别对节点重要程度进行度量， 各自得到重要程度最高的１０ 个节点的标号．表２４ 种方法得到前丨 ０ 个重要节点标号ＣＫＭＰｈｙｓｉｃｉ ａｎｓＩ ｎｎｏｖａｔｉｏｎＣＳＡａｒｈｕｓＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔｉ ｏｎＭｏｓｃｏｗＡｔｈｌ ｅｔｉ ｃｓ２０１ ３ＭＤＣ ＭＥＶＣ ＭＣＲ ＭＥＣ ＭＤＣ ＭＥＶＣ ＭＣＲ ＭＥＣ ＭＤＣ ＭＥＶＣ ＭＣＲ ＭＥＣ ＭＤＣ ＭＥＶＣ ＭＣＲ ＭＥＣｖｌ２２ｖ４１ ｖｌ ５ ｖｌ ２２ ｖ４４ ｖ５１ ｖ７ ｖ４４ ｖｌ ５ ｖｌ ｖ５０ ｖｌ ５ｖ２２ｖ２９ ６０４ ｖｌ３８９２ ｖ２２ｖ２９ｖ４７ｖ９８ｖ２９ｖ５１ｖｌ ９ｖ４４ｖ５１ｖ５０ ｖ２６ｖｌ ５ｖ５０ ｖ７２７ｖ２９６１６ｖｌ２８５８ｖ７２７ｖｌ４１ ｖｌ２３ｖ９３ ｖｌ４ １ ｖ２３ｖ５３ｖ３４ｖ２３ｖ３８ ｖ２ ｖ４０ｖ３８ ｖ７ｖ２９ ６０５ｖ７４７３８ ｖ７ｖ３６ｖ４９ｖ２９ｖ３６ ｖ３４ ｖ５６ ｖ２ １ ｖ７ｖ４０ｖｌ４ｖ３８ｖ４０ ｖ４２ｖ２９ ６０９ ｖ２５９３６ ｖ４２ｖ２１６ ｖｌ ２９ｖ３６ ｖ５５ ｖ７ ｖ５８ ｖ５１ｖ３４ ｖ２ ｖ５０ｖ２ ｖ２ ｖ６０５ ｖ８ ｖｌ７８ １７ ｖ６０５ｖｌＯＯｖ２０５ｖ８ｖｌＯＯ ｖ４６ ｖ５０ｖ２６ ｖ４６ｖ２５２ ｖ７４ ｖ８３ ｖ２５２ ｖｌ７ ｖ２９６１１ｖｌ９８６７ ｖｌ ７ｖ４６ ｖｌ ３ １ ｖ２４ｖ４６ ｖ２６ｖ７ｖ３ １ｖ２６ｖ６４ ｖ３６６ ｖ７ ｖｌ ２ ｖ９ ｖ２９８７８ ｖｌ２９４２ｖ９ｖｌ９１ｖ２１ １ｖ４６ ｖ３１ｖ３１ ｖｌ ８ ｖｌ９ ｖ３１ ｖ８３ ｖ２９３ ｖｌ６６ ｖ６４ｖ８１０ｖ２９ ８０３ ｖｌ９８８２ ｖ８１０ｖ５５ ｖｌ ２５ｖｌ ｌ ｖ９４ ｖ３３ｖ５４ ｖｌ３ｖｌ３ｖｌ２ ｖ６２ｖ６４ ｖ８３ｖ３１５ｖ２４ ３ｖ４６２５１ ｖ３１ ５ｖ２３１ ｖ４４ ｖ２８ ｖ２７ ｖｌ３ｖ６ｖ４６ｖ８ ｖ７ ｖ４３ ９ｖｌ ２ ｖ７ ｖ３２７ｖ３００４７ ｖ５１１１２ ｖ３２７为验证４．２ 节中的猜想， 首先对度中心性和局部聚集系数的相关性进行了讨论， 通过计算４ 个网络中度中心性向量和局部聚集系数向量的Ｋｅｎｄａｌ ｌ相关系数［２２］来说明二者的相关性， 计算结果统一取４ 位有效数字， 如表３ 所示． 可以看出， 在ＭｏｓｃｏｗＡｔｈｌ ｅｔｉｃｓ２０１３中， 度中心性与局部聚集系数之间呈现出较弱相关性外， 在其它３ 个数据集上， 二者均未呈现出明显的相关关系， 所得结论与４．２ 节中猜想—■致？表３ 度与局部系数相关性数据集 Ｋｅｎｄａｌ ｌ 相关系数ＣＫＭＰｈｙｓｉｃｉ ａｎｓＩｎｎｏｖａｔ ｉｏｎ ０．０１７５ＣＳＡａｒｈｕｓ－０．２６５０ＥＵＡｉｒＴｒａｎｓｐｏｒｔ ａｔ ｉｏｎ ０． ２ ９５８ＭｏｓｃｏｗＡｔ ｈｌ ｅｔ ｉｃｓ２０１３ ０．５２７８通常， 对重要节点挖掘方法的评价一般采用基于网络的传播动力学模型和基于网络的鲁棒性和脆弱性２ 种方法［３Ｓ］． 分别在４ 个数据集上进行了５ 组不同实验， 从网络的传播特性和鲁棒性及脆弱性２４０６ 计 算机 学 报 ２０２０年２个方面对所提出的方法进行了全面评价．前４ 组实验从网络的传播特性方面对所提出方法进行了评价． 基于网络的传播动力学模型对重要节点度量方法评价， 常采用ＳＩＲ传播模型． 在ＳＩＲ模型１ ７’３８＿＇｜１］中， 对重要节点的评判标准一般有２ 项：一种为传播速率， 可从传播初始阶段感染态／ （／） 和恢复态ｉ？（ｆ） 的数量和达到稳态时所用时间两方面来评判， 数Ｍ越大、 所用时间越小， 说明该节点越重要； 另一种为节点的平均传播范围， 即达到稳态时感染态／（？ ） 和恢复态 的数量之和， 数量越大， 说明该节点越重要． 为方便说明， 令第／ 个时问迭代步时，感染态和恢复态的数童之和记为Ｆ（０， 感染态的平均数量记为Ｆ， （ｚ）， 达到稳态时的数量记为Ｆ（〇．由于网络规模不同， ＳＩＲ模型的传染概率和恢釔概率依赖于各层层内网络的拓扑结构． 通常， 传染概率的设置依赖于各层内网络的渐近传播阈值乂°：． 渐进传播阈值为传播过程中应取的最小传播概率［３８］， 定义为丨。］ ＝＿＾＿（２７）￣〈 （ Ｋ－——〈 Ｋ：”根据贝叶斯理论和条件概率， 各层传染概率设置为Ｗ．Ａｉ 冲］＾ｖＴ（２８）其中Ａ， 为放大系数 为多关系网络的关系数． 恢复概率通常依赖于各层的平均度， 类似地， 各层恢复概率设置为由于传播过程是依概率进行感染传播， 即使２ 组实验条件完全相Ｎ，Ｍ终得到的结果也会存在一定差异． 为此， 特选取１ 〇〇次独立实验所得结果的期望值作为评价结果．实验１．本实验主要通过观测各节点传播初期的ＦＧ）与各方法测量值之间的相关关系， 来说明节点的传播能力． 本实验设置《＝１〇． 在理想状态下， ＦＧ） 与对应的测量值应呈现正相关关系．在４ 个数据集上的实验结果如图５ 所示． 图５ＣＫＭＰｈｙｓｉ ｃｉａｎｓＩｎｎｏｖａｔｉｏｎ ＣＫＭＰｈｙｓｉ ｃｉ ａｎｓＩ ｎｎｏｖａｔｉｏｎ ＣＫＭＰｈｙｓｉ ｃｉａｎｓＩｎｎｏｖａｔｉｏｎ ＣＫＭＰｈｙｓｉ ｃｉ ａｎｓＩ ｎｎｏｖａｔｉｏｎＭＥＶＣ（ ｂ）ＣＳＡａｒｈｕｓＭＤＣ（ｅ）ＦＸＩＡｉ ｒＴｒａｎｓｐｏｒｔａｔ ｉ ｏｎ ＫＵ八ｉ ｒ Ｔｒａｎｓｐｏｒｔａｔｉ ｏｎ１ ０°ＣＳＡａｒｈｕｓ ＣＳＡａｒｈｕｓ（ｇ）ＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔ ｉｏｎ ＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔ ｉｏｎ（ ｋ）（１ ）图５／＝１０ 时， ＦＵ）与各方法测量值间的相关关系１２ 期 罗 浩等： 基于证据理论的多关系网络重要节点挖掘方法 ２４０７中， 每行子图分别对应同一数据集下的不同方法， 坐标轴采用双对数坐标， 横轴表示每一种方法下各节点的测量值， 纵轴表示各节点作为传染源节点时， 所对应的Ｆ（ ｆ） （ ｒ＝１０）．ＭｏｓｃｏｗＡｔｈｌｅｔｉｃｓ２０１ ３由于规模较大， 故选取各方法得到的前１ ０００ 个节点作为实验节点．实验结果表明： ①在４ 个网络中， 多层度中心和多重证据中心性都能呈现出较好的正相关关系，多重证据中心性要优于多层度中心性， 特别是在规模较大的ＭｏｓｃｏｗＡｔｈｌｅｔｉｃｓ２０１３ 中， 优势更加明显； ②多重Ｃｌ ｕｓｔｅｒＲａｎｋ在规模较小的３ 个网络中， 能够呈现出较好的正相关关系， 但在规模较大的ＭｏｓｃｏｗＡｔｈｌｅｔｉｃｓ２０１３网络中， Ｆ（ 〇与多重Ｃｌ ｕｓｔｅｒＲａｎｋ 没有呈现出相关关系，一些测量值较低的节点反而ＦＵ） 越大； ③相比于其它３ 种方法，多层特征向量中心性总体表现最差， 除在ＣＳＡａｒｈｕｓ和ＣＫＭＰｈｙｓｉｃｉａｎｓＩｎｎｏｖａｔｉ ｏｎ 中呈现出较弱的正相关关系外， 在其它网络中均没有呈现出明显的相关关系．实验２．为了进一步验证各方法的性能， 本实验研究了按不同度量方法对节点的重要程度进行排序后， 节点排序与所对应的平均感染数量〈Ｆ（Ｏ＞（ ｉ＝１０ ） 之间的关系． 性能较好的度量指标， 其图像应该呈现递减关系， 即随着节点重要程度的降低， 对应的受感染节点的平均数会减少． 为了对比． 本实验特意增加了随机排序这种极端情况． 实验结果如图６ 所示， 其中横轴代表各节点排序， 纵轴代表对应的受感染节点平均数量． 类似地， 在ＭｏｓｃｏｗＡｔｈｌｅｔｉｃｓ２０１３中， 分别选取排序前１０００ 名的节点作为实验节点．ＣＫＭＰｈｙｓｉｃｉａｎｓＩｎｎｏｖａｔｉ ｏｎ ＣＳＡａｒｈｕｓ（ ｂ）ＭｏｓｃｏｗＡｔ ｈｌｅｔｉ ｃｓ２０１３Ｒ（ｖ）（ ｄ）ｍ６ 通过５种方法得到的节点排序对应／＝１ ０时的平均感染度显然， 随机排序的情况最差？ 在ＣＳＡａｒｈｕｓ 和ＣＫＭＰｈｙｓｉｃｉ ａｎｓＩｎｎｏｖａｔｉｏｎ中，４种方法均能呈现出递减趋势， 从传播范围上分析， 多重ＣｌｕｓｔｅｒＲａｎｋ得到的结果要优于其它３ 种方法， 特别是在ＣＫＭＰｈｙｓｉｃｉａｎｓＩｎｎｏｖａｔｉ ｏｎ 中， 其它３ 种方法者Ｐ表现出了幅度较大的波动， 而多重Ｃｌ ｕｓｔｅｒＲａｎｋ呈现出的波动较小？ 在ＭｏｓｃｏｗＡｔｈｌｅｔｉ ｃｓ２０１３ 中， 多重证据中心性和多层度中心性能够呈现出较理想的递减趋势， 而其它两种方法表现较差． 从传播范围上分析， 多重证据中心性要优于多层度中心性． 在ＥＵＡｉｒＴｒａｎｓｐｏｒｔａｔｉｏｎ中， 多层特征向量中心性表现最差， 其它三种方法表现相当， 都能够呈现出较好的递减趋势．２４０８ 计 算机 学 报 ２０２０年实验３．本实验通过观测传播达到稳态时所用的时间和ＦＵ）， 从传播速率和传播范围两方面来评测各方法的测量性能． 在４ 个网络中， 按照各方法对节点的重要程度进行排序， 分别选取前１％的节点作为初始传染源节点， 统计１ ００ 个时间迭代步的ＦＧ）， 并绘制ＳＩＲ时间增长曲线， 其中横轴代表时间迭代步数， 纵轴代表对应的Ｆ“） ， 结果如图７ 所示．４ 个网络上的实验结果显示： ①无论是传播时间还是传播范围，ＭＥＣ都能表现出较好结果， 特别是在大规模网络中尤为明显； ②ＭＣＲ在规模较小的网络中表现较为理想， 但在规模较大的ＭｏｓｃｏｗＡｔ ｈｌｅｔｉｃｓ２０１ ３ 数据集中， 其得到的结果Ｍ差， 从而进一步验证了之前的猜想； ③多层度中心性在规模较小的网络屮所得到的结果较好， 但在大规模网络中， 与ＭＥＣ的差距明显增大， 从而说明考虑网络传递性因素是非常必要的．１＊１７ 前１ ％的节点作为初始传染源节点时的ＳＩＲ传播曲线实验４．本实验通过比较节点在ＳＩＲ模型上的传播能力与各测量值之间的相关关系， 来评测各方法的性能．我们对各节点在ＳＩＲ 模型中得到的稳态值Ｆ（ Ｕ进行排序， 并计算了其与各方法之间的肯德尔相关系数（ｒ）． 图８ 描述了在４ 个网络中， 各节点在ＳＩＲ模型中的传播能力与４ 种重要节点测量方法间的相关关系， 图中每一行子图对应同一数据集的不同方法， 坐标轴采用双对数坐标， 横轴表示各节点在对应方法下的测量值， 纵轴表示各节点在ＳＩＲ模型中得到的稳态值Ｆａ） ， 每一个数据点代表网络中的一个节点， 节点的灰度表示在传播过程中， １〇 时的传播能力， 即Ｆ（１０）， 图中标识的ｒ 值即为相应的肯德尔相关系数值． 在ＣＳＡａｒｈｕｓ 和ＣＫＭＰｈｙｓｉｃｉ ａｎｓＩｎｎｏｖａｔｉ ｏｎ中， 四种方法与节点传播能力之间表现出的相关性都较弱， 多重Ｃｌ ｕｓｔｅｒＲａｎｋ 和多重证据中心性要优于其它２ 种方法． 在ＭｏｓｃｏｗＡｔｈｌｅｔｉ ｃｓ２０１３ 中， 多重证据中心性和多层度中心性能够呈现出较好的相关关系， 多重证据中心性仍然表现最好，而其它两种方法呈现出的相关性较弱． 在ＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔｉｏｎ 中， 除多层特征中心性夕卜 ， 其它３ 种方法都能呈现出较强的相关性．罗 浩等： 基于证据理论的多关系网络重要节点挖掘方法 ２４０９ １２ 期ｏｃＳｏ１０１ＣＫＭＰｈｙｓｉ ｃｉ ａｎｓＩ ｎｎｏｖａｔｉ ｏｎ ＣＫＭＰｈｙｓｉｃｉａｎｓＩｎｎｏｖａｔｉｏｎｒ＝０．０９０６ｒ＝０．０５ＦＣｔ）■ ６０ｈｏ■２０ｊｊｊｉＦｉｔ）１ ６０１４ ０■２０？． ．１ ０° ． 丄Ｉｉ１０１ＭＤＣ（ ａ ）ＣＳＡａｒｈｕｓ１０２１ ０１ＭＥＶＣ（ ｂ）ＣＳＡａｒｈｕｓ１０２￥１０（ ｃ）ＣＳＡａｒｈｕｓ（ｄ）ＣＳＡａｒｈｕｓｒ＝０． １３１ ６ｔ＝０．０８７６ ｒ＝０．２７１ ５ ｔ＝０． １９８１ＦＣ Ｏ■ｌ＇． ？ ？？？？ ．２＾００？？？？ｓ，Ｆ（ ｔ ）．？ ？Ｆｉ ｔ ） Ｆ（ ｎ＇ ＇ｉ．１０°１００＂２ｉ１０°？＇＇１１．１０ＭＤＣ（ ｅ ）ＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔｉ ｏｎ１０ＭＥＶＣ（ ｆ）１０ＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔｉ ｏｎＭＣＲ（ｇ）ＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔｉｏｎ１０ＭＥＣ（ ｈ）ＥＵＡｉ ｒＴｒａｎｓｐｏｒｔａｔｉ ｏｎＭＤＣ（ ｉ ）ｔ＝０． ８２２８ｊＦＣｔ）ＩｆＭＣＲ（ ｋ）ＭｏｓｃｏｗＡｔ ｈｌｅｔｉ ｃｓ２０１ ３１０＇ １０２ＭＥＣ（ １ ）ＭｏｓｃｏｗＡｔｈｌｅｔｉ ｃｓ２０１３图８ 节点测Ｍ？值与ＳＩＲ传播能力间的相关关系实验５．本实验从网络的鲁棒性和脆弱性方面对所提方法进行了评价． 着重考察网络中一部分节点被移除后， 网络结构发生变化情况， 变化越大， 说明移除的节点越重要． 用各重要节点挖掘方法将网络中所有节点按重要性进行降序排序， 将一部分节点从网络中移除， 用Ｃ（ ｉ／ｉＶ） 表示移除ｉ／Ｎ比例的节点后， 网络中最大连通集（ｌａｒｇｅｓｔｃｏｍｐｏｎｅｎｔ ） 的节点数目的比例， 通过绘制“ｆ／ＩＶ—Ｃ（ ｉ／Ｎ）”曲线，对节点移除的影响进行分析． 图９ 显示了在４ 个数据集上使用４ 种重要节点挖掘方法对节点排序后，移除一定比例重要节点后， 对网络最大连通集的影响． 实验表明， 在４ 个数据集上， 通过多重证据中心性和多重度中心性得到的节点排序， 当移除部分节点后， 网络结构变化最大， 特别是在移除前１／４ 后，多電证倨屮心性呈观出的变化趋势要比多重度中心性更为明显． 而多重Ｃｌ ｕｓｔｅｒＲａｎｋ方法， 在前３ 个规模较小的数据集中， 也能呈现出明显的变化趋势， 但在规模较大的ＭｏｓｃｏｗＡｔｈｌ ｅｔｉｃｓ２０１ ３ 数据集中， 变化趋势缓慢， 而多重证据中心性和多重度中心性呈现出瞬间下降的趋势？ 图 １〇 显示了在ＭｏｓｃｏｗＡｔｈｌｅｔｉｃｓ２０１３ 数据集中， 移除前１０００ 个节点， 网络最大连通集的变化趋势． 结果表明， 在大规模网络中， 通过多重证据中心性和多重度中心移除极少数重要节点， 便能引起网络结构的分裂， 多重证据中心性所得到的结采要优于多重度中心性， 而多重Ｃｌｕｓｔ ｅｒＲａｎｋ 和多重特征向量中心性所得到的结果变化趋势不明显， 进一步说明了多重证据中心性的有效性和多重Ｃｌ ｕｓｔｅｒＲａｎｋ方法不适用于大规模网络的局限性．ＭｏｓｃｏｗＡｔｈｌｅｔｉｃｓ２０１ ３中， 网络中心性和传递性间的矛盾更加突出， 导致多重Ｃｌ ｕｓｔｅｒＲａｎｋ度量重要节点有效性的降低． 多重度中心性和多重特征向量中心性由于只考虑了单方面因素， 虽然在算法复杂度上具有优势， 但相比于综合考虑中心性和传递性的多重证据中心性， 在度量效果上缺乏精准性．〇． １００． ００３０． ００６０．００９ｉ／Ｎ图１０ 移除前１０００ 个节点的网络连通变化趋势通过上述５ 组实验可以得出， 由于Ｄ－Ｓ 证据理论是基于概率论的处理不确定问题的信息融合方法， 在融合节点中心性和传递性信息的过程中？ 用概率来刻画节点重要程度的大小， 能够有效消除由于多关系网络耦合信息和传递机制的差异性对度量节点重要信息的影响， 所提出的多重证据中心性能够更加精准有效地挖掘网络中的重要节点， 而多重Ｃｌ ｕｓｔｅｒＲａｎｋ采用的是相关性融合的确定方法， 但由于多关系网络耦合信息和传递机制的差异性， 节点的传递性和中心性之间不具备相关性， 因此无法准确挖掘网络中的重要节点． 特别是在大规模网络６ 结束语本文针对无权无向多关系网络重要节点挖掘问题进行了研究分析， 综合考虑多关系网络的中心性和传递性对节点重要程度的影响， 提出了多重ＣｌｕｓｔｅｒＲａｎｋ重要节点度量指标， 并针对其存在问题引入Ｄ－Ｓ证据理论进行改进， 进一步提出了多重证据中心性重要节点挖掘方法． 在４ 个真实网络数据集上的实验结果表明：（１） 在多关系网络中， 由于受耦合信息和传递机制差异性的影响， 节点的度中心性和局部聚集系数不具备相关性， 对二者进行直接融合的多重Ｃｌ ｕｓｔｅｒＲａｎｋ会造成计算结果误差， 降低重要节点挖掘的准确性， 特别是在大规模网络中， 无法有效识别网络中的重要节点；０．２５ ０．５０ｉ／Ｎ（ ｃ）０．７５ １．００ ０．２５ ０．５０ｉ／Ｎ（ ｄ）０．７５ １． ００图９移除节点比例和网络最大连通集规模的关系ＥＵ |
| [返回] |
下一篇：基于区块链的网络安全体系结构与关键技术研究进展