复杂网络中社区发现算法研究

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

1、寡｝－＿－１ｈ；、ｈｖ、－４ＡＷ、＇Ｎ＊ａｌｗ妾；‘＞■．？至ｉ至６＊＂：‘＾＾ｉｈＹ．ｒｔ．ｌ＾４ｌ一－Ｔ．．「ｒｒ’－ｎｌｈ’ｎｆ『Ｈ、ｈｈｈ＾ｈ未经本论文作者的书面授权，依法收存和保管本论文书面版本、电子版本的任何单位和个人，均不得对本论文、修改、出的全部或部分内容进行任何形式的复制、发行租、改编等有碍作者著作权的商业性使用（但纯学术性使用不在此限。）。否则，应承担侵权的法律责任博古学位论文原创性声明，本人郑重声明，是本人在指导教师的指导下：所呈交学位论文，独立进行研巧工作所取得的成果。除文中已经

2、注明引用的内容外本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，巧己在文中Ｗ明滿方式标明。。本人完全意识到本声明的法律结果由本人承担学位论文作者签名：Ｉ马姑＞曰期９曰；年／月复杂网络中社区发现算法研究ResearchonCommunityDetectionAlgorithmsinComplexNetworks作者姓名：周旭专业名称：计算机应用技术研究方向：数据挖掘指导教师：刘衍珩教授学位类别：工学博士培养单位：计算机科学与技术学院论文答辩日期：2016年6月5日授予学位日期：2016年月日论文

3、评阅人：答辩委员会组成：盲审专家正高级西北工业大学主席郑斯清教授美国德克萨斯大学达拉斯分校盲审专家正高级中南大学委员杨华民教授长春理工大学盲审专家正高级天津大学李文辉教授吉林大学李雄飞教授吉林大学刘衍珩教授吉林大学秦贵和教授吉林大学赵宏伟教授吉林大学摘要摘要复杂网络中社区发现算法研究现实世界的许多复杂系统都可以表示成复杂网络，如社会网、生物网、技术网等。社区结构是复杂网络中的一个重要属性，它表明网络中的节点具有集聚化特性。网络具有的复杂性、多样性、动态性等特点会使发现社区结构的研究工作变得更加复杂，也使该工作成为最具挑战的课题任务之一。检测社区结构可用于分析和

4、理解网络中的结构功能、发现网络中的隐含模式、预测网络的动态发展规律，乃至对于网络的认知和利用具有非常重要的意义。在解决社会网络、无线传感器网络、邮件交互网络等实际问题中，社区发现的研究工作是网络分析中的重要组成部分。虽然目前诸多社区结构挖掘算法已经被广泛应用于网络社区发现问题，但如何能够在不需要先验知识的基础上，既降低算法的复杂度又提高社区划分结果的准确度，一直是社区发现算法不断发展和研究的方向。本文研究复杂网络中的社区发现、重叠社区发现、动态社区发现三个方面的内容，主要贡献与创新工作如下：1.为了解决基于模块度优化的社区发现方法存在的分辨率限制问题，本文将社

5、区发现看做是一个多目标优化问题，首次利用布谷鸟算法求解社区发现问题并提出了一种基于多目标布谷鸟优化的社区发现方法(MDCL)。该算法通过同时优化两个互相冲突的目标函数NegativeRatioAssociation和RatioCut来控制网络中的社区规模，同时，MDCL设计了满足要求的离散形式位置更新公式和放弃操作算子，并采用局部搜索和克隆策略提高种群质量。在人工和真实网络数据集上验证了算法的有效性，实验结果表明MDCL方法相比于其他算法可以挖掘出高质量的社区结构。2.本文提出了一种基于蚁群算法的重叠社区发现方法(AntCBO)。该算法主要包括蚂蚁初始化、蚂蚁

6、移动和后处理三个模块。算法在初始化阶段确定蚂蚁位置和各节点中的初始标签；在移动阶段，通过蚂蚁在转移机制的启发下自由移动实现各个节点中标签信息的更新，当终止条件满足时各个节点会得到相应的标签序列；最后，通过后处理策略得到网络中的重叠社区划分结果。另外，本文提出了一种求解转移概率的启发式信息计算方法。在人工和真实数据集上的实验结果均表明，相比于其他算法，AntCBO算法具有更好的性能，可以更加准确地检测出网络中重叠节点和重叠社区结构。3.为解决基于边聚类算法导致社区结构出现节点过度重叠的问题，同时为有效地提高重叠社团划分的准确性，本文提出了一种基于密度边聚类的重叠

7、社区发I吉林大博士学位论文现算法(DBLC)。该算法在边扩展阶段基于核心密度可达概念对核心边进行初始聚类得到若干边社团，然后通过更新策略将未分类的边划分至与之相似度最高的社团中。同时，我们提出了一种计算边与边相似度的方法。基于人工数据集和真实网络数据集上的实验结果表明，该算法在挖掘重叠社区结构和重叠节点方面性能表现更优。4.静态网络中的社区发现研究工作会忽略网络的动态性，难以识别网络中社区结构的变化，而动态社区发现算法研究可有效地检测动态社区结构。本文提出了一种基于多目标生物地理优化动态社区发现算法(MBBOD)。该方法采用分解机制同时优化分别表示快照代价的目

8、标函数模块度和表示时间代价的目标函数标