动态网络中的重叠社区发现研究

《动态网络中的重叠社区发现研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人或集体已经发表或撰写过的研究成果，对本文的研究做出贡献的集体和个人均己在论文中作了明确的说明并表示了谢意。研究生签名：日期：_论文使用和授权说明本人完全了解云南大学有关保留、使用学位论文的規定，即：学校有权保留井向国家有关部门或机构送交学位论文和论文电子版；允许论文被查阅或借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵循此规定）研究生签名:导师签名：I伽奉日期:本人及导师同意将学位论文

2、提交至清华大学“中国学术期刊（光盘版）电子杂志社”进行电子和网络出版，并编入CNKI系列数据库，传播本学位论文的全部或部分内容，同意按《中国优秀博硕士学位论文全文数据库出版章程》规定享受相关权益。研究生签名：__导师签名:日期：复杂网络大量存在于现实世界中，而在这些网络中，往往存在某些结点之间的关系比较密切同时某些结点之间的关系相対稀疏的现象，这些关系紧密的结点之间形成被称为社区的子结构。在复杂网络中，某些结点可能不是仅仅属于其中的某ー个社区而是可能同时属于多个社区，即网络中存在社区重叠现象。此外，绝大多数的复杂网络的结构不是固定不变的，而是随着时间的演进而不断变化的。随着时间

3、的推进，网络中的结点可能出现或者消失，加入或者离开某一社区，或者是从ー个社区转移到另外ー个社区。结点之间的联系可能越来越错综复杂或者越来越简单。复杂网络中的重叠社区发现和动态特性研究具有很强的现实意义。在现有的社区发现算法中，已经存在一些社区重叠发现算法和动态网络中的社区发现算法，但是同时考虑网络的动态性和社区的重叠性的算法还比较少。本文针对以上不足，提出了一种动态网络中社区重叠的发现算法，并依此对复杂网络的动态性和社区重叠性进行研究。本文主要工作如下：针对传统算法中所采用的对图中结点进行聚类的方法不能很好地解决发现社区重叠现象与发现网络层次组织结构之间的冲突的问题，本文采用了

4、对图中的边进行聚类的方法，提出了一种新的衡量边与边之间相似度的定义，以发现网络中的边社区结构。本文采用改进的层次聚类算法来自然地反映复杂网络中社区的层次结构。在根据边相似度对相似的边进行合并形成新边时，为了能够进行下一歩的合并，本文对合并后产生的新边进行了新的定义。为了追踪动态网络中社区的演化过程，本文采用了时间窗ロ的概念，并将新定义的边相似度和改进的层次聚类算法应用于时间窗口上，以相对平滑地跟踪社区的演化过程。本文采用动态网络数据集进行实验，验证了以上新的边相似度定义的合理性，改进的层次聚类算法的有效性，以及在引入边社区和时间窗ロ的概念以后，追踪动态网络社区演化过程的准确性和

5、相对平滑性。关键词：动态网络；社区重叠；边社区；层次聚类；演化稳定性AbstractAbstractIntherealworld,manycomplexnetworksexist,andinthemostcomplexnetworks,thereareusuallysomeindividualsbetweenwhomrelationshipsaredensertiianthosebetweenotherindividualsandtheindividualswhoserelationshipsaremuchrelativelydenserthanotherscanbeclass

6、ifiedintoasub-structurecalledcommunity.Incomplexnetworks,someindividualsmaynotonlybelongtoonecommunity,buttoseveralcommunitiesatthesametime,whichiscalledthecommunityoverlappingphenomenon.Besidesthat,thestructuresofmostcomplexnetworksarenotconstant,buttransformastimegoesby.Andasthetimegoesby,

7、theindividualsinthenetworksmayappearordisappear,joinintosomecommunityorleavesomecommunityormovefromonecommunitytoanothercommunity.Whafsmore,therelationshipsbetweentheindividualsmaybemoreandmorecomplexorbesimpleraswell.Itissignificanttofindtheoverla