复杂网络中的社团发现与链路预测

《复杂网络中的社团发现与链路预测》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP301密级：公开研究生学位论文论文题目（中文）复杂网络中的社团发现与链路预测Communitydetectionandlinkpredictionof论文题目（外文）complexnetwork研究生姓名桂春学科、专业计算机科学与技术·计算机应用技术研究方向复杂网络、机器学习学位级别博士导师姓名、职称张瑞生教授论文工作起止年月2013年9月至2018年9月论文提交日期2018年9月论文答辩日期2018年12月学位授予日期2018年12月校址：甘肃省兰州市复杂网络中的社团发现与链路预测摘要社团结构是复杂网络的重要特征之一，可以用

2、来表达网络的一些功能和特征；链路预测用已知网络拓扑结构特征和节点属性预测两个节点之间产生连边的概率，两者对复杂系统的研究和应用都具有重要的理论和现实意义。为了降低标签传播算法在社团发现中由于随机性引发的聚类结果不稳定的问题，使用社团归属度来确定社团个数和社团初始形状，很大程度上改进了标签传播的随机选择缺点。提出的LPA-CBD（LabelPropagationAlgorithmBasedonCommunityBelongingDegree，基于社团归属度的标签传播算法）算法首先寻找平均吸引力最大节点的初始社团，然后通过社团归属度来优化或扩

3、大初始社团，在得到网络的初始社团划分后，对剩余节点利用标签传播算法进行标签选择。实验通过在十个真实网络以及3个人工网络上测试，并与经典的LPA、随机游走算法、BGLL算法、GN算法、快速贪心算法、LeadingEigenvector等社团发现算法在社团数量、算法准确度和模块度等评价指标上对比，实验证明LPA-CBD算法在各个指标上表现良好，不仅具有较低的算法复杂度和较高的社团发现质量，并且提高了原始标签传播算法的稳定性。社团结构是网络中普遍存在的拓扑特征之一，许多真实网络的社团结构不但具有层次性，还具有重叠性，目前大多数工作只研究网络的层

4、次性和重叠性的一个方面。Ahn在2010年发表的文章证明了层次性和重叠性是网络社团结构相同现象的两个方面，本文在Ahn的方法的基础上提出了社团检测的新算法：SAoLG（SpectralAnalsisofLineGraph，线图的谱分析），将谱分析方法应用到边社团发现上，进行了兼顾层次性和重叠性的社团检测研究，实验中使用的网络有一个标准网络、两个社团结构清晰的网络（空手道俱乐部网络和海豚社交网络）以及四个真实网络，实验结果的评价准则选择模块度modularity、划分密度PD(PartitionDensity)、社团数目CN(Communi

5、tyNumber)、节点覆盖率CR(CoverageRate)、未覆盖节点数UV(UncoveredVertices)、节点划分准确率Accuracy、正确划分节点数CDV(CorrectlyDividedVertices)，实验对比算法分别为Ahn的算法（LC算法）、CPM算法和GN算法，实验结果表明SAoLG算法实现了网络的重叠社团检测并且社团划分的结果优于其他三个经典的社团检测算法。网络的社团结构同样影响着复杂网络链路预测的准确性。利用图的拉普拉斯矩阵的特征向量作为样本空间进行社团结构划分能够收敛到全局最优，是很好的划分社团结构的方

6、法之一。通过引入基于拉普拉斯矩阵的相似度计算方法，提出一种链路预测新算法：LPbSA（LinkPredictionbasedonSpectralAnalysis，基于谱分析的链路预测），将对节点提取属性特征进行边的预测转化为直接对边提取属性特征并根据其属性值进行预测。ILPbSA算法首先获取网络拉普拉斯矩阵的特征值和特征向量，选择最小非平凡特征向量的维数为2维和3维，分别获取2维和3维最小非平凡特征向量对应的相似度（文中使用角距离、欧式距离以及曼哈顿距离三种相似度），得到网络中所有节点对之间可能存在的边的6个属性，然后使用机器学习算法对边

7、进行分类，分类变量的值为0和1，其中0表示节点对之间无连边，1表示节点对之间有连边，这样就将网络的链路预测问题转换成了对边的分类预测问题，实验在七个真实数据集上分别与基于节点局部信息的相似性指标、基于路径的相似性指标和基于随机游走的相似性指标三类算法共18个相似性指标的链路预测结果作对比，实验结果证明了LPbSA算法的可行性、有效性。关键词：社团检测，归属度，链路预测，边图，谱分析IICommunitydetectionandlinkpredictionofcomplexnetworkAbstractCommunitystructurei

8、soneofthemostimportantfeaturesofcomplexnetwork,whichcanbeusedtoexpresssomefunctionsandfeaturesof