本文是一篇计算机论文，本文在深入研究标签传播社区发现算法的基础上，融合节点影响力的概念，针对传统LPA算法随机性强、社区划分结果不一致、准确率不高等问题展开深入研究，提出了两个改进的标签传播算法，优化了节点选择及标签更新策略，并通过大量实验验证了所提算法社区发现结果的稳定性、有效性和更高的准确性。
第一章绪论
1.1研究背景和意义
1.1.1课题研究背景
伴随着互联网和大数据技术的飞速发展，复杂网络的[1]研究逐渐渗透至信息科学[2]、生物科学[3]等诸多领域，成为了网络时代研究中极具挑战性的一个课题。许多科技、商业、经济和生物方面的数据在现实世界中都可以使用复杂网络进行表示[4]，例如电力网格、社交网络、万维网等。这些各种各样的复杂网络系统都可以近似拓补为复杂网络结构，网络中的节点代表系统中的实体，网络中的链接代表实体间存在的相互作用关系。在诸如科研合作网络、交通运输网络等的社会网络中，通常用节点表示对象，用边表示对象之间的关系。如图1.1所示，每一条边代表一名对象和另一名对象的社会关系，可以反映出人与人之间的亲密程度。在这样的一个社会网络里，内部的相关成员就可以进行更加密切的交流，他们通常有着共同的目标或话题。社会网络是由相互链接的个体组成的网络结构，其中个体可以是个人、组织或其它实体，网络中的链接关系通常反映出这些个体之间的社会关系。社会网络的规模通常非常庞大，其中链接关系也非常复杂，这对社会网络的研究工作带来了巨大的挑战。随着用户数量和数据量的不断增加，社会网络的结构也变得越来越复杂，需要更加先进的技术和方法来理解和分析。
由于大规模复杂社会网络的出现导致传统的社区发现方法面临诸多挑战。社区结构[5]作为复杂网络大数据的一个重要特征，吸引了国内外众多学者的关注。社会网络通常由多个群组组成，在社区内部，节点之间的连接比较紧密，而社区之间的节点连接则相对稀疏。这种结构使得社区内部的信息传递和交流更加高效，也更有利于对网络的分析和建模。社区结构揭示了社会网络是由许多相互关联但相对独立的社区构成的，社区结构的发现对于理解网络的真实含义、分析网络的结构和功能稳定性、以及推动社会网络信息传播和影响最大化研究都具有重要意义。如图1.2所示，是一个简单的社区结构示例图，用不同的颜色区分不同的社区，可以清晰地看出，同一社区内节点连接更为紧密，社区间的节点连接稀疏。
1.2国内外研究现状
按照社会网络图的社区之间是否允许存在重叠节点，可以将社区发现方法分为重叠社区发现和非重叠社区发现。重叠社区是一种社区结构，与传统的社区结构不同的是，它允许节点属于多个社区。这种现象可以看作是节点在社区划分中的模糊区域，它的出现对于更精细的社区划分和更准确的节点分类具有重要意义。早期的社区发现研究者大都重点关注非重叠社区，很少考虑重叠节点，随着人们对社区概念的不断深入，发现网络中的社区不仅仅是互相没有交集的，如今网络结构错综复杂且伴随着动态变化，重叠社区出现在人们生活的方方面面，并且社区中的重叠节点通常充当更重要的角色。如图1.4所示，列举了两个社会网络图，图(a)是非重叠社区网络图，社区之间没有交集。图(b)是重叠社区网络图，红色节点是重叠节点，属于多个社区。
1.2.1非重叠社区发现算法研究现状
Girvan和Newman[9]于2002年提出的社区概念，主要应用与小规模社区，这类算法应用在简单、规模小的网络中可以表现出良好的性能，随着网络化时代的到来，社区规模和复杂程度都明显增大，重叠社区和动态化的社区结构也越来越普遍，为了满足人们对于信息挖掘的需求，大量的有关社区发现的算法涌现出来。社区发现是复杂网络研究领域的一个核心问题，目前已经有许多社区发现算法被提出并应用于发现快速高效的社区。
第二章社区发现相关理论基础
2.1社会网络
2.1.1社会网络基本概念
社会网络把某一部分具有相同爱好或是处于相同领域的人联系在一起，其形成与发展是基于个体之间的多种关系，包括但不限于价值观、理念、兴趣、友谊、血缘、共同经历等，这些关系共同构成了一个复杂的网络结构。根据节点间连接关系的不同，社会网络可以分为三大类：无权社会网络、加权社会网络和符号社会网络。无权网络的边权值都为1，通常表示节点之间是否有连接关系。加权网络的边权值不唯一，节点之间的权值反映了它们之间的亲密程度，权值越高表示两个节点之间关系越紧密。然而这两种网络都只考虑了节点间积极的关系，没有考虑节点间的消极程度，符号网络带有正或负符号属性，分别代表积极的朋友关系和消极的敌对关系。尽管网络的结构和形态各异，但还是有很多相似的属性，例如网络大都具有明显的社区结构，且只有部分节点拥有较大的度，是网络中的核心节点。无权网络是出现最早的社会网络，其余两种网络其实就是特殊的无权网络，在此之前，已经有大量针对无权网络的研究涌现出来，本文也重点研究了无权网络。
现实世界中的网络五花八门，很难找出一些共同的特性，但随着人类对网络研究的深入发现，无论网络复杂还是简单，它们普遍存在着某种特征，但并不是必须符合的属性，而是对大量网络进行分析后得出的规律性总结。
第一个典型的特征就是人们熟知的“小世界”现象，尽管网络中的大部分节点之间没有直接连接，但它们通常可以通过少数几步路径相互到达，根据大量计算得出，网络中任意两个节点之间的平均距离为log(n)，n为网络中的节点总数。在日常生活中可以发现，某些你觉得离你很遥远的人，其实你与他之间只相隔了6个人，通过6个人就可以联系到任何人。
第二个特征是网络中的度分布，在大量的网络中观察发现，大多数节点的连接很少，只有少数节点和其他节点的连接较多，而这类节点通常是网络中的重要节点，在网络中所占比例非常小，所以平均度不会随着网络规模变化而变化，独立于网络规模的大小。
2.2社区发现理论基础
社区发现是复杂网络分析中的一项重要的研究工作，如果将复杂网络模型转化为一张包含众多节点和连边的图，那么社团结构就是一张特殊的子图。它由一些相似的相互连接的顶点构成，并且保证同一社区内部的节点间连接密度要高于不同社区间的连接密度。社区又有强弱之分，在弱社区的定义下，社区内节点之间的连接相对于社区外节点之间的连接更加密集，但不强制要求每个节点只与社区内的节点连接，因此相对于强社区定义更加宽松。在实际应用中，大多数社区发现算法所得到的社区结构为弱社区结构，而非严格的强社区结构。
2.2.1社区发现问题描述
日常的社交网络可以看做一个无向图，通常用二元组G=(V,E)来表示，其中V={vi|i=1,2,..,n}为节点集合，节点数量一般用|V|来表示。E={e(vi,vj)|∀vi,vj∈V∧i≠j,e(vi,vj)=e(vj,vi)}，|E|为连边的数量。例如，给定一个有m条边和n个节点的网络图，则|V|=n，|E|=m，两个节点vi和vj之间存在连边时，e(vi,vj)=1。社区发现的本质就是根据节点的属性划分网络，根据某种方法计算出节点间的亲密程度，根据亲密度进行社区划分，最终使得具有相同或相似特征的节点划分到同一个社区内。如图2.1所示，该网络被划分为两个社区，分别用不同的颜色表示。可以明显看出，社区内的节点联系较社区间的联系更为稠密。
第三章 融合种子节点影响力及邻域相似度的标签传播算法 ............ 22
3.1 引言 ..................................... 22
3.2 LPA-INSS 算法 ...................................... 22
第四章 一种改进的基于 LeaderRank 的两阶段标签传播算法 ........ 35
4.1 引言 ........................................... 35
4.2 LPA-ITSLR 算法 .......................... 35
结论 ................................. 48
第四章一种改进的基于LeaderRank的两阶段标签传播算法
4.2 LPA-ITSLR算法
4.2.1问题的提出
本章以基于标签传播的两阶段社区发现算法LPA-TS为例，对其进行分析，发现两阶段的标签传播算法普遍存在一些问题。在LPA-TS算法的第一阶段，当出现与当前节点相似度最大的节点有两个及以上的情况时，算法随机选取其中一个节点进行标签更新，由此可能导致不同的划分结果。
结论
本文在深入研究标签传播社区发现算法的基础上，融合节点影响力的概念，针对传统LPA算法随机性强、社区划分结果不一致、准确率不高等问题展开深入研究，提出了两个改进的标签传播算法，优化了节点选择及标签更新策略，并通过大量实验验证了所提算法社区发现结果的稳定性、有效性和更高的准确性。本文主要研究成果如下：
(1)提出一种稳定的融合种子节点影响力及邻域相似度的标签传播算法LPA-INSS。引入种子节点的概念，有效解决了LPA算法初始标签数量过多导致后期迭代更新的不稳定及效率低的问题。对于非种子节点，提出了基于连接强度和邻域相似度的标签更新策略。实验结果表明，所提算法有效降低了标签传播过程的随机性，提高了执行效率，在6个真实网络和8个不同规模及复杂性的人工数据集上均得到了稳定的社区划分结果，且准确性高于对比的9种经典的社区发现算法。其中，在真实及人工数据集上社区划分结果的模块度较传统LPA算法相比最大提升分别为87.64%和47.04%，在两个较大规模的人工数据集上模块度相比其他7种算法提高了77%左右。
(2)提出一种改进的基于LeaderRank的两阶段标签传播算法LPA-ITSLR。定义了新的相似性度量并融合LeaderRank值作为节点重要性的衡量指标，在此基础上进行标签的更新，最后依据模块度作进一步的社区合并。实验结果表明，所提算法解决了LPA-TS算法因标签选择的随机性可能导致的多次社区划分结果不一致及小社区问题，在9个真实网络和19个人工数据集上总体取得了较其它数十种算法更加稳定准确的社区划分结果。在6个小规模和3个大规模真实网络上，改进后的算法多次运行所得社区划分结果始终一致、数量最接近真实社区数目且模块度最高。对于人工数据集，所提算法社区划分结果模块度较其他7种LPA算法最高提升约96%，特别是在包含20000~50000个节点的大规模数据集上，NMI值基本都达到了0.98以上，表明改进后的算法社区划分结果准确性更高。
参考文献（略）