复杂网络中社区发现方法研究

发布时间：2018-04-20 13:35

本文选题：社区发现 + 复杂网络　；参考：《哈尔滨工业大学》2017年博士论文

【摘要】：随着社会和科技的不断发展,个体之间的社会关系和联系方式变得越来越复杂,并构成了许多复杂系统。人们很难直接从纷繁多样的复杂系统中获取有价值的信息。为此,将复杂系统抽象为形式相对简单的复杂网络,通过对复杂网络进行深入研究,能够有效地挖掘出复杂系统的各种普遍规律和特性。目前,人们已经发现复杂网络的小世界性、无标度性和社区结构等特性。社区是由部分关系紧密的节点及其之间连边组成的节点聚簇结构。社区结构最主要特点是,社区内部节点之间链接相对紧密、社区之间链接相对稀疏。由于人们可以通过社区结构便捷地获取到感兴趣的信息,并将之应用到热点挖掘、个性化推荐、链接预测等领域,因此,复杂网络中社区发现方法成为了当今研究的热点之一。本文从全局角度和局部角度出发,在提高社区发现结果稳定性、利用已知背景信息克服网络信息缺失、挖掘重叠社区结构、融合节点内容主题和链接关系等四个不同侧面研究了复杂网络中社区发现方法中存在的特有问题,并给出了相应的解决方法,提升了社区发现结果的质量和稳定性。第一,针对传统标签传播社区发现方法结果不稳定的问题,提出了一种稳定的标签传播社区发现方法,提高了基于标签传播社区发现结果稳定性。传统基于标签传播的社区发现方法中的随机过程导致了在同一网络中多次社区发现结果相差较大,社区发现结果稳定性较差。基于此,本文提出了一种稳定的标签传播社区发现方法。首先,通过网络中不重叠三角形进行标签初始化,赋予不重叠三角形节点相同的初始标签,使得社区结构更加稳定;然后,根据节点标签熵的大小对传播节点队列进行排序,降低了传播节点队列设置的随机性;最后,在标签传播过程中,当遇到数量最多的标签不唯一时,根据当前被传播节点的两层邻接点标签分布情况确定选择的传播标签,增加了标签传播选择过程的稳定性。第二,针对网络部分信息缺失导致社区发现结果偏差的问题,提出了基于半监督局部聚类社区发现方法,实现了利用部分已知背景信息克服网络信息缺失问题。传统社区发现方法没有充分利用已知部分社区背景信息去克服网络部分信息缺失所导致的社区发现结果偏差的问题。基于此,本文提出了一种半监督局部聚类社区发现方法。首先,改进了传统局部聚类社区发现方法中节点加入社区的衡量方法,使得社区发现过程更符合社区结构定义;接着,采取奖励惩罚措施,对社区发现过程中与已知信息相符的给予奖励,鼓励其社区结构形成;对不符合已知信息的社区结构予以惩罚,阻碍其社区结构的继续形成,从而引导社区发现结果更加符合真实网络的社区结构。此方法能够更好地在信息不完整的网络中挖掘出原本的社区结构。第三,针对网络节点角色多元化与社区结构硬划分的问题,提出了基于半同步标签传播和局部聚类的重叠社区发现方法,提高了重叠社区结构发现质量。传统社区发现方法对复杂网络进行硬划分,忽略了更加符合实际情况的复杂网络社区重叠结构。基于此,本文提出了一种半同步标签传播重叠社区发现方法。该方法结合了传统标签传播方法中的异步传播策略和同步传播策略,避免了标签传播震荡问题的同时,在计算效率和社区发现结果质量之间取得了较好的平衡。另外,本文还提出了一种基于局部聚类的重叠社区发现方法,该方法采取了改进的Pagerank算法进行种子节点选择,利用Spin-glass模型作为社区扩张节点选择的标准,能够更好地挖掘出复杂网络中重叠社区结构。最后,针对传统社区发现方法忽略了节点内容信息层面属性的问题,提出了融合内容主题和链接关系的社区发现方法,获得了更加符合真实情况的社区发现结果。传统社区发现方法基于网络结构本身,仅仅考虑了节点间的链接关系,忽略了节点自身的内容信息层面的属性。基于此,本文提出了一种融合内容主题和链接关系的社区发现方法。首先,通过LDA模型获取节点内容主题向量,并计算内容主题向量间的相似度;然后,将内容主题向量间的相似度分别融合到基于标签传播和基于局部聚类的社区发现方法中。在融合内容主题和标签传播的社区发现方法中,候选标签被赋予权重,权重值为候选节点与被传播节点之间的内容主题相似度,被传播节点的新标签选择权重值最大的候选标签;在融合内容主题和局部聚类的社区发现方法中,综合节点与社区在内容主题和链接关系的相似度,选择使得社区综合密度增加最多的节点加入社区。此方法相对于单独基于内容主题或单独基于链接关系的社区发现方法取得了更符合真实情况的社区结果。
[Abstract]:This paper puts forward a kind of stable label propagation community discovery method , which makes the community structure more stable . This paper proposes a method of community discovery based on local clustering .

【学位授予单位】：哈尔滨工业大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】