复杂网络的重要链接识别方法研究

摘要

从复杂网络的构成元素来看，边和节点的研究同时兴起于上个世纪八十年代，但边的研究仍相对较少，尽管不少学者很早在边的强弱的度量做出贡献。在衡量各自的重要性方面，节点重要性排序愈发成熟完善，而衡量边的强弱并不能直接作为其重要性：在某些方面，连接强度大的边未必有很高的重要性，连接强度弱的边未必其重要性就差。况且在加权网络中，边的权重也不能直接当作边重要性的值，它仅仅可以作为衡量边重要性的参考。因此，在不同的应用场合，如何量化边的重要性就显得尤为关键。
　　边是复杂网络中建立联系的直接体现，而且网络中边的条数远大于节点的数量。与节点相比，在相同数量下边的增加和缺失对已有的统计特征数值的影响相对较小，但是在某些功能方面，一些边具有举足轻重的作用。如何挖掘并量化排序这类边非常有实用价值且难度不亚于节点的重要性衡量。本文接下来对边的重要性衡量问题做了一些研究和探讨，主要有两个方面，取得的创新性成果如下：
　　（1）边在网络中最基本的一个功能就是维持节点或节点集之间的连通性。本文从社区的角度出发，挖掘并量化维系社团间连边的连通重要性，这类边对社区演化和增置冗余边备用有着重要指导意义。为此，本文提出一种新的衡量算法LE（Link Entropy）：首先，使用非负矩阵分解得到每个节点归属于不同社区的概率分布，然后借助信息熵和交叉熵来量化边对于连接社区的重要性。通过观测分析边的渗透实验和最大连通片的变化，该算法在很小的阈值内就能达到最大连通片的涌现，此外，非负矩阵分解过程中随机初始化的矩阵影响不大且对社区个数要求并不高。
　　（2）边是信息传播的载体，网络中不同位置的边有不同的信息流量负载，如何控制边来最快遏制谣言传播和使公益信息更好扩散值得关注。信息流通过程中，节点所获得的信息量与其连边的信息负载量有着直接关联。本文以重要节点挖掘为依托，提出了一种基于信息流量的算法IFL(Information Flow of Link)来得到边的流量负载并以此作为在信息传播的重要性值。该算法利用高斯-赛德尔迭代法和基于邻居权重的自适应更新原则，在较少迭代次数内就可获得稳定结果。鉴于缺乏边在信息传播方面重要性的公认检验指标，本文采取侧面验证节点重要性排序的方式：通过节点排序结果和传染病模型（SIR）所得的1000次均值排序作对比来验证该算法的可行性，间接表明边在信息传播过程中重要性值的合理性。实验表明，通过连边信息负载量所获得的节点重要性排序结果准确度高，说明所依赖的边的信息负载合理可行。
　　总之，本文从两个角度对重要链接进行了量化识别研究，并在真实网络上对算法进行了有效性证明。本文的研究为重要链接识别提供了新思路，在知识发现和社会计算等领域有一定的价值。

目录

第一章 绪论

1.1研究背景及意义

1.2国内外研究现状

1.3 本文研究内容与主要工作

1.4 论文组织结构

第二章 重要性排序的相关知识

2.1复杂网络简介

2.2边重要性算法

2.3节点重要性与评价基准

2.4本章小结

第三章 边在维持全局连通的重要性衡量算法

3.1 问题描述

3.2 LE算法

3.3 实验数据及度量方法

3.4 实验结果与分析

3.5 本章小结

第四章 边在信息传播重要性的衡量算法

4.1 问题描述

4.2 IFL算法

4.3 实验数据及度量方法

4.4 实验结果与分析

4.5 本章小结

第五章 总结与展望

5.1本文工作总结

5.2研究工作展望

参考文献

攻读学位期间取得的研究成果

致谢

个人简况及联系方式

声明