复杂网络重叠社团划分算法研究与实现

《复杂网络重叠社团划分算法研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Ｉ朵击如成＊赛ＣＭＩＮＡＵＮＩＮＯＬＯ色ＹＯＦＩＶＥＲＳＩＴＹＯＦＥＬＥＣＴＲＯＮＩＣｓｃＥＭＣＥＡＮＤＴＥＣＨ＾专业学位硕±学位论文ＭＡＳＴＥＲＴＨＥＳＩＳＦＯＲＰＲＯＦＥＳＳＩＯＮＡＬＤＥＧＲＥＥＶ＇七曲听■：。■＇；罕－＼Ｉ：打诗论文题目复杂网络重叠社团划分算法妍究与实现专业学位类别工程硕±学号２０１３２２２２０２４９作者姓名康晓慧指导教师刘啼副教授Ｖ．Ｌ货，．．ｖＭ—ｖ．：．ｖ＇．，

2、＾．独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加Ｗ标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：蠢疏聲日期：心ｆ占年４月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部口或机构送交论文的复印件

3、和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可Ｗ将学位论文的全部或部分内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）、作者签名：嚴搞，讀１导师签名：沪碱日期：＞《年４月：日９分类号密级注1UDC学位论文复杂网络重叠社团划分算法研究与实现（题名和副题名）康晓慧（作者姓名）指导教师刘峤副教授电子科技大学成都（姓名、职称、单位名称）申请学位级别硕士专业学位类别工程硕士工程领域名称软件工程提交论文日期2016.03.18论文答辩日

4、期2016.04.18学位授予单位和日期电子科技大学2016年06月答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号。RESEARCHANDIMPLEMENTATIONOFOVERLAPPINGCOMMUNITYDETECTIONALGORITHMINCOMPLEXNETWORKSAMasterThesisSubmittedtoUniversityofElectronicScienceandTechnologyofChinaMajor:MasterofEngineeringAuthor:KangXiaohuiAdvis

5、or:Prof.LiuQiaoSchool:SchoolofInformationandSoftwareEngineering摘要摘要在大数据时代，随着复杂网络数据持续爆发式地增长，复杂网络所带来的影响已经进入我们生活的方方面面。因此，对这些复杂网络进行社团结构划分研究有着重要的价值和意义。复杂网络社团结构可以分为非重叠社团结构和重叠社团结构，与非重叠社团结构相比，重叠社团结构更贴近网络的真实社团组织结构。然而，重叠社团结构的研究目前处于起步阶段，同时由于重叠社团划分算法的复杂度较高，因此需要研究者们付出更大的努力。本文致力于探索

6、准确、有效的复杂网络社团划分算法。提出了一种非重叠社团划分算法和两种有效的重叠社团划分算法。本论文取得的主要创新性成果如下：（1）注重于网络边在复杂网络社团结构划分中的重要意义，提出了一种新的基于节点亲密度和度的边权重度量方法（WeightMeasurebasedonIntimacyandDegree,WMID）。将此度量方法应用在复杂网络的社团划分中，设计了划分非重叠社团结构的社团划分算法和划分重叠社团结构的社团划分算法，在社团划分中，该方法将任意一个复杂网络转化为一个加权网络，然后对网络进行社团划分。本文在多组真实网络数据集上

7、进行了大量的实验。实验结果表明，基于节点亲密度和度的边权重社团划分方法可以快速、有效地划分网络社团结构。WMID方法为有向和无向网络的重叠和非重叠社团划分提供了一种实用、灵活且可靠的方法。（2）由于基于种子节点的重叠社团划分方法具有复杂度低、速度快、划分结果贴近真实社团等优点，本文提出了一种新的基于剪枝和种子节点的重叠社团发现算法(OverlappingAlgorithmbasedonCuttingandSeedsExpansion，OACSE)。该算法创新性地将双连通图理论与网络社团划分结合起来，同时采用电导值评估方法与基于邻居

8、节点的社团传播方法扩张种子节点进行社团划分。本文在人工数据集和真实网络数据集上进行了多组实验。实验证明，OACSE算法可以在中小型网络中有效地发现社团结构。OACSE算法为重叠社团划分研究提供了另一种可行的方法。关键词：重叠社团划分，加权网络，种子