论文部分内容阅读
在传统的社区网络发现中,人们的目标是发现网络中的非重叠结构社区,所有顶点只能存在单一社团中,社团之间的节点不会出现重叠,并且社团内的顶点彼此间关系紧密,社团间的顶点彼此疏散。但随着研究的进一步深入,学者们发现非重叠结构社区发现算法已经不能满足人们的需求,顶点能同时存在于多个社区中,即重叠社区结构,这类社区结构更加符合真实世界中存在的社区网络,更具有研究意义。传统的重叠社区发现算法大多将节点作为主要研究对象,但基于节点的社区划分很难处理重叠节点较多的真实网络,因此学者们将注意力转移到边上,基于边划分的重叠社区算法得到很大发展。本文基于单层网络映射(SLG),提出多层网络映射(MLG)的重叠社区发现算法,SLG是将原始图转化为边图,在边图上进行社区划分,再将其结果转化为原始图的划分结果,其本质是使用网络中边蕴含的信息进行社区划分。但SLG只经过一次的边图转换,会导致结果的重叠度不够,只能得到重叠的节点,不能得到重叠的关系,并且重叠节点很少,与真实网络还存在差异,针对这些问题,本文提出了多层网络映射的重叠社区发现算法MLG。MLG算法主要有2方面的改进:引入多层网络映射思想,在边图映射时,进行N次迭代,使最后转化为原始图社区划分结果的重叠度变高以及重叠范围变大;在网络映射的过程中设定阈值,过滤相似度很小的边,使相似度较小的边不进行下一次的边图映射,为后续的社区发现过程降低干扰。MLG算法在执行时首先对网络图进行预处理,去除冗余的边,然后对原始图进行多次映射得到多层边图,对多层边图采用层次聚类算法进行划分,最后将多层边图的划分结果转换为原始网络图相应的划分。本文将MLG算法与SLG算法和CPM算法进行比较,实验使用8种数据集(4种标准网络数据集Dolphins、Karate、Politics、Football和4种人工网络数据集128-10-4、128-40-4、128-60-4、256-60-4),并用3种经典的社区评估方法(EQ、PD和CR)对实验结果进行详细分析,实验结果表明MLG算法优于SLG算法和CPM算法,提升了社区划分的合理性和准确性。