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

重叠社区发现论文 社区发现论文 边社区论文 边相似度论文
论文详情
重叠社区发现问题是复杂网络分析中很热门的一个问题。重叠社区发现旨在揭示复杂网络中的重叠的社区结构。重叠的社区结构接近真实网络中存在的社区结构,因此,对于重叠社区发现问题的研究是有着实际意义的。传统的重叠社区发现研究都是以节点作为主要研究目标。近年来,一些工作开始以边作为研究目标,旨在通过对网络中存在的边社区进行发现,进而达到解决重叠社区发现问题的目的。我们笼统地称这类算法为边社区发现算法。与传统的重叠社区发现算法不同,边社区发现算法将社区看作是由边构成的。由于将边作为研究对象,边社区发现算法在解决重叠社区发现问题时,会具有独特的优势。例如,通常,边在真实网络中是属于单一社区的。边社区发现算法在对边社区进行发现工作时,会自然地形成节点的重叠社区结构;近来的一些边社区发现算法会使用层次聚类算法对边进行聚类,这样做能够同时考虑到相应的节点的层次关系和重叠关系。边社区发现算法虽然有着独特优势,但仍存在着发现的边社区质量低、边相似关系考虑不全和节点的重叠度过高的问题。为进一步利用相似性关系拓展传统重叠社区发现策略,本文从边相似关系角度开展了针对边相似关系模型的阶段性改进工作,从考虑扩展边之间的关系的基于线图相似度,到考虑具有共同邻居边之间的关系的拓展余弦边距离,再到考虑具有公共邻居边之间的极值情况的极值非相邻边的边相似度,进行了递推式改进。(1)利用线图模型来对边聚类问题建模。考虑到边与边之间的相似关系不仅存在于具有共同节点的边之间,还存在于具有共同邻居的边之间以及不相邻的边之间。提出了一种基于线图的边相似度计算方法;结合马尔科夫聚类算法和基于线图的边相似度计算方法,提出了基于线图的边聚类LCLG算法;在真实网络和生物网络上的实验结果验证了LCLG算法的有效性。(2)考虑到具有公共邻居的边之间的相似关系,结合余弦相似度,提出了一个拓展的余弦边距离计算方法。将快速密度峰值搜索聚类算法引入到边社区发现中,并提出了基于盒图的社区中心边的自动选取策略;结合拓展的余弦边距离计算方法、快速密度峰值搜索聚类算法及基于盒图的社区中心边自动选取策略,提出了边密度聚类LDC算法;在真实网络上的实验结果表明,LDC算法能够发现具有良好模块度和高覆盖率的重叠社区。(3)考虑到具有共同邻居的边之间的两种极值情况,提出了极值非相邻边的边相似度计算方法;使用拓展的模块度评价指标来改善层次聚类算法的划分结果,并提出了极值非相邻边的边聚类MLC算法;在真实网络上的实验结果表明,MLC算法能够发现具有良好模块度的重叠社区结构。本文提出的LCLG算法、LDC算法和MLC算法,能够对复杂网络中的边社区进行发现,进而达到解决重叠社区发现问题的目的,在理论和实际应用方面都具有一定意义。
摘要第4-6页
Abstract第6-7页
第1章 绪论第11-17页
    1.1 社区发现第11-12页
    1.2 重叠社区发现与边社区发现第12-14页
    1.3 本文工作及论文安排第14-17页
第2章 社区发现方法综述第17-35页
    2.1 传统的社区发现算法第17-20页
        2.1.1 图分割算法第17-18页
        2.1.2 分裂式与凝聚式层次聚类算法第18-19页
        2.1.3 基于模块度的算法第19-20页
    2.2 重叠社区发现算法第20-25页
        2.2.1 派系过滤算法第20-22页
        2.2.2 局部社区发现算法第22-23页
        2.2.3 模糊重叠社区发现算法第23-24页
        2.2.4 其它重叠社区发现算法第24-25页
    2.3 边社区发现算法第25-29页
        2.3.1 边聚类算法第26-27页
        2.3.2 iLCD算法第27-28页
        2.3.3 其它边社区发现算法第28-29页
    2.4 重叠社区发现中的评价指标第29-33页
    2.5 本章小结第33-35页
第3章 基于线图的边聚类算法第35-55页
    3.1 引言第35-36页
    3.2 相关方法第36-38页
        3.2.1 相关的定义及线图模型第36-37页
        3.2.2 Leicht-Holme-Newman相似度计算方法第37-38页
        3.2.3 马尔科夫聚类算法第38页
    3.3 基于线图的边聚类算法第38-46页
        3.3.1 基于线图的边相似度计算方法第38-42页
        3.3.2 基于线图的边聚类算法第42-46页
        3.3.3 算法复杂度分析第46页
    3.4 实验第46-53页
        3.4.1 具有标准划分的真实网络第47-49页
        3.4.2 不具有标准划分的真实网络第49-53页
    3.5 本章小结第53-55页
第4章 边密度聚类算法第55-71页
    4.1 引言第55-56页
    4.2 相关方法第56-58页
        4.2.1 快速密度峰值搜索聚类算法第56-57页
        4.2.2 盒图模型第57页
        4.2.3 相关定义第57-58页
    4.3 边密度聚类算法第58-63页
        4.3.1 拓展的余弦边距离计算方法第58-60页
        4.3.2 边密度聚类算法第60-63页
        4.3.3 算法复杂度分析第63页
    4.4 实验第63-69页
        4.4.1 评价指标第64页
        4.4.2 具有标准划分的真实网络第64-68页
        4.4.3 不具有标准划分的真实网络第68-69页
    4.5 本章小结第69-71页
第5章 极值非相邻边的边聚类算法第71-87页
    5.1 引言第71页
    5.2 相关方法第71-74页
        5.2.1 原始的边聚类算法第71-73页
        5.2.2 相关定义第73页
        5.2.3 拓展的模块度评价指标第73-74页
    5.3 极值非相邻边的边聚类算法第74-77页
        5.3.1 极值非相邻边的边相似度计算方法第74-76页
        5.3.2 极值非相邻边的边聚类算法第76-77页
        5.3.3 算法复杂度分析第77页
    5.4 实验第77-85页
        5.4.1 评价指标及数据集第77-78页
        5.4.2 真实网络第78-84页
        5.4.3 LCLG、LDC、MLC算法在真实网络上的对比第84-85页
    5.5 本章小结第85-87页
第6章 结论与展望第87-89页
参考文献第89-95页
攻读博士学位期间取得的科研成果第95-97页
致谢第97页
论文购买
论文编号ABS2993017,这篇论文共97页
会员购买按0.30元/页下载,共需支付29.1
不是会员,注册会员
会员更优惠充值送钱
直接购买按0.5元/页下载,共需要支付48.5
只需这篇论文,无需注册!
直接网上支付,方便快捷!
相关论文

点击收藏 | 在线购卡 | 站内搜索 | 网站地图
版权所有 艾博士论文 Copyright(C) All Rights Reserved
版权申明:本文摘要目录由会员***投稿,艾博士论文编辑,如作者需要删除论文目录请通过QQ告知我们,承诺24小时内删除。
联系方式: QQ:277865656