面向网络数据的改进标签传播算法设计与实现

发布时间：2020-09-17 12:32

　　现实生活中,许多大型复杂系统都是以网络的形式存在的。随着信息量的增加,网络的规模也越来越大,比如微博社交网络、交通网络、大型电力网络、生物神经网络等等。因此,挖掘网络的内在结构,对于更好的分析和运用网络具有至关重要的意义。社区发现正是挖掘复杂网络的研究热点之一,它是探索和理解网络如何工作的一个重要方法。目前,已经有许多社区发现方法被提出,其中标签传播算法(LPA)是处理大规模网络的一种重要算法,由于其拥有线性时间复杂度而受到广泛关注。但由于该算法中每个节点的标签更新依赖于其邻居节点的标签,标签的更新顺序对算法的迭代速度和聚类效果非常敏感,所以直接影响了社区划分结果的准确性和稳定性。基于以上的问题,本文提出了两种基于标签传播算法的改进算法,具体研究内容如下。(1)提出基于加权聚类集成的标签传播算法。该算法利用聚类集成技术,对多次标签传播算法产生的结果集进行融合,并通过模块度对单个基聚类的有效性进行评估,以此来构建加权相似性矩阵,最后采用层次聚类方法形成更理想的社区划分结果。通过将提出的新算法与其他改进的标签传播算法在真实数据集上进行的实验比较,结果显示,在NMI指标和ARI指标上的结果都能展示出新算法能有效的提高社区发现的鲁棒性。(2)提出基于节点重要性的标签传播算法。该算法通过将信息熵和模块度结合的方式来评估一个节点的重要性,并将节点按照节点重要性从高到低排序,然后使标签从关键节点开始传播,并且选择其最重要的邻居节点的标签来更新自身的标签,从而提高了社区发现的准确性。最后,将新算法和近几年几个改进的标签传播算法在一些典型的社区网络上进行了对比实验分析,实验结果展示出基于节点重要性的标签传播算法能有效地提高社区发现的质量。本文从不同的角度对标签传播算法进行了改进,且改进后的算法能有效地提高社区发现的质量。新算法的提出为网络数据的分析提供了新的技术支持,也为更准确地挖掘网络社区提供了更为广泛的应用价值。
【学位单位】：山西大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5;TP301.6
【部分图文】：

邻接矩阵,社区,典型方法,内在结构

(a)无向无权网络 (b) 的邻接矩阵 ( )图 2.1 无向无权网络及其邻接矩阵聚类是一种用于发现网络内在结构的典型方法。它是按照网络数据的内在网络中的节点集进行划分，使划分出的每个社区互不相交，且社区之