复杂网络结构分析与链路预测

发布时间：2017-12-26 08:13

本文关键词：复杂网络结构分析与链路预测　出处：《电子科技大学》2016年博士论文　论文类型：学位论文

【摘要】：研究复杂网络是认识复杂系统的重要手段。诸多对于复杂网络拓扑结构的研究成果表明,真实系统往往会涌现出许多有趣的性质,而这些性质往往又决定了复杂系统的功能,并影响着复杂网络领域中的许多理论研究。链路预测是其中一个重要的研究方向,在理论和应用层面上都有重大的意义和价值。理论上讲,改善链路预测算法与挖掘网络结构特征是相互促进的,这对于模拟网络演化过程有着重要的意义;从应用上讲,链路预测算法可以直接应用于社交网络的关系预测,与另一重要的信息过滤技术即推荐系统也有着紧密的联系。以复杂网络为研究对象,本文先对网络结构做了不同尺度的分析,包括宏观、中观和微观的尺度,然后针对网络结构特征提出了相应的链路预测算法,最后将链路预测算法应用到了推荐系统中。此研究利用了计算机科学、统计物理学等诸多学科常用的理论和方法,不仅发现了一些有趣且有效的结构特征,还通过分析链路预测与推荐系统在目标上的差异,进而抽取了网络的信息骨架。本文研究的问题包括:(1)在宏观层面的网络结构分析中,对比了不同演化机制对于真实网络的影响。针对复杂网络演化模型是否优秀的评估问题,提出了一种基于似然分析的模型,该模型突破了传统方法在此问题上的缺陷:它不需要统计任何网络特征指标,且首次量化了多种演化机制在网络演化过程中的作用大小。(2)在中观层面上,提出了一种新的方法论,推断并验证了有向网络中的一个显著子图。将势能理论引入到有向网络中,结合聚类性和同质性,得到了同时拥有这三种性质的Bi-fan结构;然后通过在多个真实网络中开展实验以验证该结构的有效性。对于该问题的研究形成了一套适用于挖掘网络结构的新方法论,即通过理论分析进行推导,再通过实验进行验证。(3)在微观层面上,重点研究了节点的中心性指标。通过分析企业员工在关系网络中的中心性指标,对员工是否升职或是否离职进行了分类,其中度和核数都是非常优秀的指标。进一步地,本文首次发现了度和核数之间的紧密联系:仅仅通过给节点上的值迭代地施加一个算子,节点上的值就会从度变为H指数,并最终收敛到核数。收敛过程中的每一个值都是对节点中心性的刻画。(4)应用网络结构特征的分析结果以提高链路预测算法。在微观层面上,通过研究每个节点在聚类性上的差异,提出了基于朴素贝叶斯的链路预测算法,它不仅将同类算法的预测准确度提高了5.7%,还有助于发现一些相似性很高却没有产生连边的节点对。在中观层面上,受计算机通信网络中最可信路由问题的启发,提出了含权的链路预测算法,此算法在众多含权网络中的整体表现最好、也最稳定。(5)将链路预测模型应用于网络演化和推荐系统中。在网络演化问题中,讨论了链路预测模型在量化演化机制贡献时的缺陷,同时分析了基于似然分析的评估模型的优势。在推荐系统方面,发现用户的活跃度以及商品的流行度能直接影响推荐算法的准确性,而且恰当地利用与目标用户没有相似兴趣的用户,反而会取得更好的推荐效果。于是我们猜想信息系统中可能存在一些冗余的甚至是有误导性的信息,并通过考察网络结构和兴趣漂移对推荐效果的影响,创新性地提出了信息骨架的概念,用于实验的网络只需要保留28%信息便可维持推荐系统的准确性;再进一步考察时间因素的影响,提出了可以自动更新却不需要大量重复计算的含时推荐算法。
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【参考文献】