基于概率模型的重叠社区发现算法研究

复杂网络论文 社区结构论文 重叠社区发现论文 概率模型论文
论文详情
现实世界的很多复杂系统可以用网络的形式来表达,比如在社会网络和生物网络中,网络中的点表示系统中的实体,网络中的边来表示实体间的关系。随着研究的不断深入,学者们发现实际网络除了具有小世界和幂率分布等统计特性外,还具有社区结构特征。社区内部的节点之间的连接相对紧密,社区之间的连接相对稀疏。寻找复杂网络中社区结构的方法已经成为复杂网络研究的重要内容之一传统的社区发现算法主要是图形分割和层次聚类,层次聚类算法又可以分为两类:凝聚方法和分裂方法。自Newman等人提出用模块度函数来评价社区划分质量后,相继出现了一些基于模块度极值优化的方法。在真实网络中,并不是每个节点都仅属于一个社区,而是存在着重叠社区结构。随后出现了一系列重叠社区划分方法,更加真实地反映网络结构。最近,一些学者利用统计推理的方法来划分重叠社区,其中一个简单的概率算法——SPAEM能很好地发现重叠社区。本文在深入理解SPAEM算法的基础上,通过实验发现该算法存在一些缺陷,比如在大规模网络中效率比较低,随机初始化使得算法容易陷入局部最优解等。首先,对SPAEM算法的时间复杂度进行了详细分析;然后,对算法做了一些改进,降低了算法时间复杂度;此外,为了避免算法陷入局部最优解,本文还提出了种SPAEM算法的初始化方法,使算法可以在更短的时间内获得更好的社区发现结果。基于真实网络和人工网络的实验结果证明了改进算法的有效性。在很多实际网络中,改进算法的社区发现结果要好于其他重叠社区发现算法。在人工网络,尤其是非常稀疏的网络中,改进算法也能得到很好的社区发现结果。
致谢第5-6页
中文摘要第6-7页
ABSTRACT第7页
1 引言第10-16页
    1.1 研究背景及意义第10-12页
    1.2 国内外研究现状第12-14页
    1.3 研究内容及主要工作第14-15页
    1.4 论文的组织结构第15-16页
2 社区发现理论基础第16-32页
    2.1 网络的基本性质第16-18页
        2.1.1 网络的图表示第16页
        2.1.2 聚类系数第16-17页
        2.1.3 平均路径长度与介数第17-18页
        2.1.4 度分布第18页
    2.2 社区发现算法第18-29页
        2.2.1 传统图类及聚类方法第19-20页
        2.2.2 分裂方法第20-21页
        2.2.3 基于模块度优化方法第21-23页
        2.2.4 基于统计推理的方法第23-26页
        2.2.5 重叠社区发现算法第26-29页
    2.3 社区结构评价标准第29-31页
    2.4 小结第31-32页
3 SPAEM概率模型第32-39页
    3.1 概率混合模型及参数估计第32-34页
        3.1.1 概率混合模型第32页
        3.1.2 EM算法第32-34页
    3.2 SPAEM模型第34-38页
        3.2.1 算法思想第34-36页
        3.2.2 参数估计第36-37页
        3.2.3 重叠节点第37-38页
        3.2.4 算法分析第38页
    3.3 小结第38-39页
4 SPAEM算法改进第39-50页
    4.1 模型求解优化第39-44页
        4.1.1 SPAEM算法时间复杂度分析第39-42页
        4.1.2 EM迭代优化第42-44页
    4.2 初始值优化的改进SPAEM算法第44-49页
        4.2.1 算法思路第44-47页
        4.2.2 初始化方法第47-49页
    4.3 小结第49-50页
5 实验及结果分析第50-65页
    5.1 实验设置第50页
    5.2 实验评价标准第50-51页
        5.2.1 准确度标准第50页
        5.2.2 时间复杂度标准第50-51页
    5.3 基于真实数据的实验第51-56页
        5.3.1 Karate数据集第51-52页
        5.3.2 Dolphins数据集第52-54页
        5.3.3 Netscienee数据集第54页
        5.3.4 Power数据集第54-55页
        5.3.5 protein-protein数据集第55页
        5.3.6 Blogs数据集第55-56页
        5.3.7 word-assoeitaion数据集第56页
        5.3.8 PGP数据集第56页
    5.4 基于人工数据的实验第56-60页
    5.5 结果分析第60-63页
        5.5.1 基于真实数据的准确率分析第60-61页
        5.5.2 基于真实数据的效率分析第61-63页
        5.5.3 基于人工数据的结果分析第63页
    5.6 小结第63-65页
6 结论第65-67页
    6.1 论文工作总结第65页
    6.2 未来的研究工作第65-67页
参考文献第67-71页
学位论文数据集第71页
论文购买
论文编号ABS2195357,这篇论文共71页
会员购买按0.30元/页下载,共需支付21.3
不是会员,注册会员
会员更优惠充值送钱
直接购买按0.5元/页下载,共需要支付35.5
只需这篇论文,无需注册!
直接网上支付,方便快捷!
相关论文

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