基于核心图的标签传播社团划分算法

发布时间：2017-04-07 15:05

  本文关键词：基于核心图的标签传播社团划分算法，由笔耕文化传播整理发布。

【摘要】：在现实生活中,我们常常将一些实际问题通过建模的方法,把对象和关系抽象成网络结构,进而发现对象间的共同特性。社团结构是复杂网络的一个重要特性,网络中的社团是指网络中连接比较紧密的节点的集合。社团内部的节点连接比较紧密,而社团间的节点连接则比较稀疏。复杂网络的社团划分有助于分析网络的结构,并能进一步发现网络中隐藏的特性。本文就复杂网络的社团发现做了如下工作：(1)文章首先介绍了社团划分的背景和研究意义,并总结了社团划分算法的研究现状。在此基础上,进一步对基于局部信息的标签传播算法进行了深入的研究。标签传播算法因其简单又快速而被广泛应用,但是它也存在稳定性较差、鲁棒性弱等问题。为了提高标签传播算法网络划分的质量,我们对标签传播算法的初始化过程进行改进。本文提出了基于核心图的标签传播算法,通过计算图中任意两点的k阶公共邻居,将具有最大相似性的节点及k阶邻居作为初始核心社团,并分配其初始标签。通过上述过程,提取一些较为紧密的子结构来作为标签传播的初始社团,并给这些结构分配初始社团标签。在真实网络中的实验结果表明该算法可以大幅提高结果的稳定性。(2)在二部图中标签传播算法不理想,为了在二部图中能够准确划分社团结构,我们提出了一种基于局部信息的LPA算法在二部图中的划分。二部图是由两类节点组成,而且同一类节点之间没有边相连。考虑到二分网络的结构特性,我们把二分网络按带加权投影的方式得到一个带权值的网络。本算法中,初始的步骤是在带权值的网络寻找初始核心社团,因此初始核心社团的数量和规模,对整个算法有着决定性的影响,这就跟选取的边权重的初始阈值有关。选择恰当的初始阈值,才能得到合适初始核心社团。然后把这些初始核心社团行标记,并在二部图进行标签传播。在传播的过程中,如果节点有多个可选的标签时,可以选多个。这样在网络中不仅能发现社团结构,还能找出重叠节点。实验结果表明,此算法应用在二部图中不仅提高了网络划分的质量,还能得到重叠的社团结构。
【关键词】：社团发现 标签传播 相似性 核心图 二部图 边权值
【学位授予单位】：南京信息工程大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.02;G206
【目录】：

• 摘要5-6
• Abstract6-7
• 第一章 绪论7-17
• 1.1 复杂网络社团划分的背景7-10
• 1.2 复杂网络社团研究现状10-15
• 1.3 本文的研究内容与文章结构15
• 1.4 本文的组织结构15-17
• 第二章 背景知识综述17-30
• 2.1 图与网络17-20
• 2.1.1 哥尼斯堡七桥问题17
• 2.1.2 规则网络17-18
• 2.1.3 随机图18
• 2.1.4 小世界网络模型18-19
• 2.1.5 无标度网络模型19-20
• 2.2 复杂网络的基本概念20-22
• 2.2.1 度分布21
• 2.2.2 平均路径长度21
• 2.2.3 聚类系数21-22
• 2.2.4 簇结构定义22
• 2.3 基于局部信息的LPA算法的描述22-27
• 2.3.1 LPA算法的基本思想23-26
• 2.3.2 LPA算法已有的改进26-27
• 2.4 重叠的LPA算法研究27-29
• 2.5 本章小结29-30
• 第三章 标签传播算法的改进30-42
• 3.1 基于局部信息的LPA算法的改进30-35
• 3.1.1 K阶共同节点的相似度30-32
• 3.1.2 初始核心社团的选取32-33
• 3.1.3 基于核心图的标签传播算法33-35
• 3.2 实验与仿真结果35-41
• 3.2.1 Zachary空手道俱乐部网络35-36
• 3.2.2 海豚社会关系的网络36-38
• 3.2.3 美国大学足球队比赛网络分析38-41
• 3.3 本章小结41-42
• 第四章 基于二分图的标签传播划分算法42-57
• 4.1 基于二分图模型的复杂网络42-45
• 4.1.1 度和度分布43-44
• 4.1.2 聚集系数44-45
• 4.1.3 最短路径长度45
• 4.1.4 介数45
• 4.2 社团结构及聚类算法45-49
• 4.2.1 基于边聚集系数的聚类算法46
• 4.2.2 Ka,b—团(Ka,b-Biclique)划分方法46-47
• 4.2.3 优化模块化函数算法47-49
• 4.3 基于局部信息的LPA算法在二分图中的改进49-52
• 4.3.1 二分图的投影49-50
• 4.3.2 带权值的初始核心社团的选取50-51
• 4.3.3 算法的具体过程51-52
• 4.4 实验结果及分析52-56
• 4.4.1 Southern Women Data实验分析52-54
• 4.4.2 随机图实验54-56
• 4.5 本章小结56-57
• 第五章 总结与展望57-59
• 5.1 全文工作总结57-58
• 5.2 对未来研究的展望58-59
• 参考文献59-63
• 致谢63-64
• 作者简介64

【参考文献】

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

1 王林,戴冠中;复杂网络中的社区发现——理论与应用[J];科技导报;2005年08期

2 马吴迪;胡学钢;何伟;;一种改进的二分网络链路预测算法[J];合肥工业大学学报(自然科学版);2014年01期

3 郭崇慧;张亮;;基于PCA的复杂网络社区结构分析方法[J];运筹与管理;2008年06期

  本文关键词：基于核心图的标签传播社团划分算法，由笔耕文化传播整理发布。

，

本文编号：290688