基于结构相似度的动态复杂网络社团增量更新算法研究

发布时间：2017-08-09 02:23

  本文关键词：基于结构相似度的动态复杂网络社团增量更新算法研究

  更多相关文章： 动态复杂网络 社团划分 相似度 增量更新

【摘要】：随着科学技术的发展,科学研究理论的变革,复杂网络已成为热门研究课题。目前,发现的复杂网络结构特征有小世界、无标度、幂律分布等,其中比较重要且研究广泛的是社团结构特征。在大容量存储成为可能、大数据时代到来的背景下,当今各领域的网络均呈现出规模大且频繁平稳变化的特点。以往提出的社团划分算法并不能被直接简单地从传统小规模静态网络上移植到当今大规模动态网络平台上运行,这样做是低效率的,甚至是不切合实际的。因此,针对当今各领域网络形态的特点,提出一种专门应用于动态大规模复杂网络的社团划分算法,来解决复杂网络动态变化引起社团划分变动的问题。本文在余弦相似度的基础上提出了用于描述两点距离的结构相似度——基于二级影响的结构相似度的定义。所谓二级影响结构相似度,即是网络中边的变化不仅会影响两端点,同时也可能会对两端点邻域内的节点造成影响(点变化同理)。针对当今复杂网络超大规模的特点,在节点间结构相似度及结构相似度相关的定义基础上提出了一种局部的静态社团划分算法LBS (Local method Based on Similarity)算法。LBS算法采用局部思想,即可以不用掌握全局信息,就可以进行社团划分,极大降低了算法的时间复杂度。LBS算法采用两阶段方式对网络进行社团划分：第一阶段,通过节点的连接偏好,形成社团小结构；第二阶段,通过发挥连接偏好链中核节点的角色任务,对连接偏好链进行连接,最终形成社团结构。基于LBS算法在社团的增量更新上的优势,本文进一步提出了动态复杂网络上的社团增量更新算法IU-LBS (Incremental Updating LBS)算法。IU-LBS算法在网络发生变化时,首先检测变化相关节点集,然后对属于不同类别的节点采用相应的社团更新方法。本文通过在多个真实网络和人工生成网络上运行LBS静态算法和IU-LBS动态算法,进一步实证了LBS算法针对于静态复杂网络的社团划分、IU-LBS算法针对于动态复杂网络的社团更新均是高效准确的。
【关键词】：动态复杂网络 社团划分 相似度 增量更新
【学位授予单位】：辽宁大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要4-5
• ABSTRACT5-11
• 第1章 绪论11-15
• 1.1 选题背景及研究意义11-13
• 1.2 本文的主要工作及创新点13-14
• 1.3 论文结构14-15
• 第2章 复杂网络和社团理论及研究方法15-22
• 2.1 复杂网络及社团理论15-17
• 2.2 国内外现有和经典的静态社团划分方法17-19
• 2.3 动态复杂网络上的社团划分方法19-22
• 第3章 社团划分相关定义22-30
• 3.1 复杂网络的表示方法22-23
• 3.2 相似度表示方法23
• 3.3 基于二级影响的结构相似度定义23-26
• 3.4 基于结构相似度的区域定义26-27
• 3.5 连接偏好的定义27-28
• 3.6 网络中节点的域信息存储结构28-30
• 第4章 静态局部社团划分算法-LBS算法30-45
• 4.1 LBS算法基本思想30
• 4.2 LBS算法具体步骤30-34
• 4.3 静态算法的实验与分析34-45
• 4.3.1 网络(图)的存储方式与表示34-35
• 4.3.2 实验目的35-36
• 4.3.3 划分质量评价标准36
• 4.3.4 参数选择的影响分析36-38
• 4.3.5 现实网络实验结果及分析38-42
• 4.3.6 人工网络实验结果及分析42-45
• 第5章 动态复杂网络上的社团更新算法-IU-LBS算法45-59
• 5.1 IU-LBS算法基本思想45-46
• 5.2 IU-LBS算法基本过程及具体步骤46-55
• 5.2.1 变化相关节点集的确定46-47
• 5.2.2 更新变化节点的属性域47-48
• 5.2.3 社团划分相关的变化量48-50
• 5.2.4 社团划分的更新50-52
• 5.2.5 IU-LBS算法具体步骤及示例52-55
• 5.3 动态算法的实验与分析55-59
• 5.3.1 实验目的55-56
• 5.3.2 划分质量评价标准56
• 5.3.3 实验网络数据集56-59
• 第6章 总结和展望59-61
• 6.1 总结59
• 6.2 展望59-61
• 致谢61-62
• 参考文献62-64

【相似文献】

中国期刊全文数据库 前6条

1 张勇;金伟其;;基于结构相似度与感兴趣区域的图像融合评价方法[J];光子学报;2011年02期

2 许少凡;刘显峰;狄红卫;;基于加权结构相似度的图像融合质量评价[J];暨南大学学报(自然科学版);2007年05期

3 王晓艳;刘勇;蒋志勇;;一种基于结构相似度的IHS变换融合算法[J];遥感技术与应用;2011年05期

4 狄红卫;刘显峰;;基于结构相似度的图像融合质量评价[J];光子学报;2006年05期

5 黄健斌;钟翔;孙鹤立;茆婉婷;;基于相似性模块度最大约束标记传播的网络社团发现算法[J];北京大学学报(自然科学版);2013年03期

6 ;[J];;年期

中国重要会议论文全文数据库 前3条

1 张勇;金伟其;;基于结构相似度与感兴趣区域的图像融合评价方法[A];中国光学学会2010年光学大会论文集[C];2010年

2 许晟;李亚楠;王斌;吴丽辉;;基于加权SimRank的中文查询推荐研究[A];第五届全国信息检索学术会议论文集[C];2009年

3 李增扬;李兵;何克清;;本体中复杂网络特性的发现[A];2006全国复杂网络学术会议论文集[C];2006年

中国博士学位论文全文数据库 前1条

1 俞唯仁;普适的结构相似度在大规模网络中的计算优化技术研究[D];东华大学;2012年

中国硕士学位论文全文数据库 前10条

1 陈东;基于子图匹配的社会网络目标群体检索技术研究[D];解放军信息工程大学;2014年

2 许凯;基于结构相似度的图像修补算法研究[D];兰州大学;2016年

3 周进;基于结构相似度的动态复杂网络社团增量更新算法研究[D];辽宁大学;2016年

4 张振山;基于结构相似度的图像去噪方法研究[D];西安电子科技大学;2014年

5 万芬;结构相似度图像质量评价算法的改进研究[D];大连海事大学;2011年

6 郑德品;基于结构相似度的图像质量评价方法研究[D];浙江大学;2007年

7 周长飞;基于MIC的图像显著性检测技术研究[D];国防科学技术大学;2013年

8 徐小琳;重视边缘的结构相似度图像/视频质量评价方法研究[D];华南理工大学;2012年

9 陈岩;基于结构相似度的图像质量评估研究[D];华北电力大学（北京）;2008年

10 陈勇;结构相似度及其在推荐系统中的应用研究[D];电子科技大学;2011年

，

本文编号：643139