重叠社区发现中的边聚类算法研究

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

1、■ｉｗｌｈＭ＾ＭＭｉ＾ｗｈ＾—ｈ—ｈｈｉ—＾ｈ—ｈｈｈ＾＾ｈ—ｈ—ｉｉｈ—重叠社区发现中的边聚类算法研究ResearchonLinkClusteringAlgorithmsinOverlappingCommunityDetection作者姓名：王贵参专业名称：计算机应用技术研究方向：复杂网络分析指导教师：黄岚教授学位类别：工学博士培养单位：计算机科学与技术学院论文答辩日期：2016年12月02日授予学位日期：年月日论文评阅人：答辩委员会组成：姓名职称工作单位姓名职称工作单位盲审专家正高级大连理工大学主席许进教授北京大学盲审专家正高级东北大学委员孔俊教授东北师范大学盲审专家正高级电子

2、科技大学王生生教授吉林大学刘淑芬教授吉林大学杨永健教授吉林大学胡亮教授吉林大学未经本论文作者的书面授权，化法收存和保管本论文书面版本、电子版本的任何单位和个人，均不得对本论文的全部或部分内容进行任何形式的复制、修改、发行、出租Ｖ改编等有碍作者著作权的商业性使用（但纯学术性使用不在此限）。否则，应承坦侵权的法律责任。吉林大学博±学位论文原创性声明本人郑重声明，，：所呈交的博±学位论文是本人在指导教师的指导下独立进行研究工作所取得的成果。除文中已经荘明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研究。做出重要贡献的个人和集

3、体，均已在文中■明确方式标明本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：２０１６年１２月６日摘要摘要重叠社区发现中的边聚类算法研究重叠社区发现问题是复杂网络分析中很热门的一个问题。重叠社区发现旨在揭示复杂网络中的重叠的社区结构。重叠的社区结构接近真实网络中存在的社区结构，因此，对于重叠社区发现问题的研究是有着实际意义的。传统的重叠社区发现研究都是以节点作为主要研究目标。近年来，一些工作开始以边作为研究目标，旨在通过对网络中存在的边社区进行发现，进而达到解决重叠社区发现问题的目的。我们笼统地称这类算法为边社区发现算法。与传统的重叠社区发现算法不同，边社区

4、发现算法将社区看作是由边构成的。由于将边作为研究对象，边社区发现算法在解决重叠社区发现问题时，会具有独特的优势。例如，通常，边在真实网络中是属于单一社区的。边社区发现算法在对边社区进行发现工作时，会自然地形成节点的重叠社区结构；近来的一些边社区发现算法会使用层次聚类算法对边进行聚类，这样做能够同时考虑到相应的节点的层次关系和重叠关系。边社区发现算法虽然有着独特优势，但仍存在着发现的边社区质量低、边相似关系考虑不全和节点的重叠度过高的问题。为进一步利用相似性关系拓展传统重叠社区发现策略，本文从边相似关系角度开展了针对边相似关系模型的阶段性改进工作，从考虑扩展边之间的关系的基于线图相似度，到考

5、虑具有共同邻居边之间的关系的拓展余弦边距离，再到考虑具有公共邻居边之间的极值情况的极值非相邻边的边相似度，进行了递推式改进。(1)利用线图模型来对边聚类问题建模。考虑到边与边之间的相似关系不仅存在于具有共同节点的边之间，还存在于具有共同邻居的边之间以及不相邻的边之间。提出了一种基于线图的边相似度计算方法；结合马尔科夫聚类算法和基于线图的边相似度计算方法，提出了基于线图的边聚类LCLG算法；在真实网络和生物网络上的实验结果验证了LCLG算法的有效性。(2)考虑到具有公共邻居的边之间的相似关系，结合余弦相似度，提出了一个拓展的余弦边距离计算方法。将快速密度峰值搜索聚类算法引入到边社区发现中，并

6、提出了基于盒图的社区中心边的自动选取策略；结合拓展的余弦边距离计算方法、快速密度峰值I摘要搜索聚类算法及基于盒图的社区中心边自动选取策略，提出了边密度聚类LDC算法；在真实网络上的实验结果表明，LDC算法能够发现具有良好模块度和高覆盖率的重叠社区。(3)考虑到具有共同邻居的边之间的两种极值情况，提出了极值非相邻边的边相似度计算方法；使用拓展的模块度评价指标来改善层次聚类算法的划分结果，并提出了极值非相邻边的边聚类MLC算法；在真实网络上的实验结果表明，MLC算法能够发现具有良好模块度的重叠社区结构。本文提出的LCLG算法、LDC算法和MLC算法，能够对复杂网络中的边社区进行发现，进而达到解

7、决重叠社区发现问题的目的，在理论和实际应用方面都具有一定意义。关键词：重叠社区发现，社区发现，边社区，边相似度，边聚类IIAbstractAbstractResearchonLinkClusteringAlgorithmsinOverlappingCommunityDetectionOverlappingcommunitydetectionhasbeenahottopicincomplexnetworks.Itaimst