基于节点重要性的复杂网络社团挖掘算法研究

《基于节点重要性的复杂网络社团挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、密级：公开工学硕士学位论文基于节点重要性的复杂网络社团挖掘算法研究ResearchonAlgorithmforMiningCommunityBasedontheImportanceofNodeinComplexNetworks培养单位：信息科学与技术学院专业：计算机应用技术研究生：张晓芬指导教师：封筠教授二〇一六年六月独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得石家庄铁道大

2、学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：日期：摘要摘要复杂网络在现实世界中普遍存在，社团结构是网络的一个重要拓扑特征。社团结构的挖掘已成为复杂网络学科下的热点研究方向，对理解分析网络功能与性质，发现网络中的隐藏规律以及预测网络行为等方面至关重要，具有重要理论研究意义和应用价值。近年来，越来越多的社团结构挖掘算法相继被提出，而面对扩大的网络规模，社团挖掘结果常受初始节点位置影响、需事先指定社团规模大小、时间复杂度高等问题在目前算

3、法中显得尤为突出。如何在寻找到的重要节点基础上展开复杂网络的社团结构挖掘，相关研究工作才刚刚起步。本文的研究是在对复杂网络节点重要性评价分析的基础上，探究基于重要节点的社团挖掘算法，试图解决或部分解决目前经典算法中的常见问题，并将所提出的算法应用于现实网络中。本文研究工作的主要贡献如下：(1)在网络节点重要性评价方面，研究了当前主流的四种单一中心性评价指标，以及一种基于主成分分析的综合性评价指标计算方法，给出了基准网络上的不同评价指标下的节点重要性分布；(2)提出了一种种子节点非重叠社团挖掘算法。根据中心性评价指标

4、确定种子节点，利用深度优先搜索策略进行全局社团划分，对于重叠节点利用社团间的连边数解决其归属问题。与经典社团聚类算法相比，基准网络上的实验结果表明该算法取得了较好的社团划分结果，且算法的计算复杂度较低；(3)提出了一种基于核心节点的局部社团挖掘算法。将网络中的重要节点作为初始社团的核心节点，通过计算核心节点与其邻居节点的相似度进行局部社团划分，再对相似的局部社团合并以得到最终的社团结构。与经典社团聚类算法和所提出的种子节点社团挖掘算法相比，基准网络上的实验结果表明该算法在划分性能方面具有明显的优势；(4)将所提出的

5、局部社团挖掘算法应用于蛋白质相互作用网络的功能模块检测，并结合基因本体数据库对模块的生物学意义进行了分析。与CPM算法和MCODE算法相比，实验结果表明所提出的算法在节点丢失率较低情况下，可挖掘到的匹配率>=50%的蛋白质模块数比例较高。关键词：复杂网络；社团挖掘；重要节点；蛋白质相互作用网络AbstractAbstractComplexnetworksareubiquitousintherealworld.Communitystructureisoneoftheimportanttopologicalcharac

6、teristcsofthenetwork.Miningcommunitystructurehasbecomeahotresearchdirectioninthecomplexnetworkdiscipline.Itisimportantforanalyzingnetworkfunctionsandproperties,discoveringthehiddenrulesandpredictingthebehaviorofthenetwork.Communitystructuremininghasimportantth

7、eoreticalsignificanceandapplicationvalue.Inrecentyears,moreandmorecommunitystructureminingalgorithmshavebeenproposed.Basedontheexpansionofthenetworksize,itisparticularlyprominentthatcommunityminingresultsareoftenaffectedbytheinitialnodelocation,communitysizesp

8、ecifiedinadvanceandhightimecomplexity.Onthebasisofthefoundimportantnode,relatedresearchonminingcommunitystructureofcomplexnetworkshasjuststarted.Theresearchofthisthesisisbasedonnod