论文部分内容阅读
重叠社区发现问题是复杂网络分析中很热门的一个问题。重叠社区发现旨在揭示复杂网络中的重叠的社区结构。重叠的社区结构接近真实网络中存在的社区结构,因此,对于重叠社区发现问题的研究是有着实际意义的。传统的重叠社区发现研究都是以节点作为主要研究目标。近年来,一些工作开始以边作为研究目标,旨在通过对网络中存在的边社区进行发现,进而达到解决重叠社区发现问题的目的。我们笼统地称这类算法为边社区发现算法。与传统的重叠社区发现算法不同,边社区发现算法将社区看作是由边构成的。由于将边作为研究对象,边社区发现算法在解决重叠社区发现问题时,会具有独特的优势。例如,通常,边在真实网络中是属于单一社区的。边社区发现算法在对边社区进行发现工作时,会自然地形成节点的重叠社区结构;近来的一些边社区发现算法会使用层次聚类算法对边进行聚类,这样做能够同时考虑到相应的节点的层次关系和重叠关系。边社区发现算法虽然有着独特优势,但仍存在着发现的边社区质量低、边相似关系考虑不全和节点的重叠度过高的问题。为进一步利用相似性关系拓展传统重叠社区发现策略,本文从边相似关系角度开展了针对边相似关系模型的阶段性改进工作,从考虑扩展边之间的关系的基于线图相似度,到考虑具有共同邻居边之间的关系的拓展余弦边距离,再到考虑具有公共邻居边之间的极值情况的极值非相邻边的边相似度,进行了递推式改进。(1)利用线图模型来对边聚类问题建模。考虑到边与边之间的相似关系不仅存在于具有共同节点的边之间,还存在于具有共同邻居的边之间以及不相邻的边之间。提出了一种基于线图的边相似度计算方法;结合马尔科夫聚类算法和基于线图的边相似度计算方法,提出了基于线图的边聚类LCLG算法;在真实网络和生物网络上的实验结果验证了LCLG算法的有效性。(2)考虑到具有公共邻居的边之间的相似关系,结合余弦相似度,提出了一个拓展的余弦边距离计算方法。将快速密度峰值搜索聚类算法引入到边社区发现中,并提出了基于盒图的社区中心边的自动选取策略;结合拓展的余弦边距离计算方法、快速密度峰值搜索聚类算法及基于盒图的社区中心边自动选取策略,提出了边密度聚类LDC算法;在真实网络上的实验结果表明,LDC算法能够发现具有良好模块度和高覆盖率的重叠社区。(3)考虑到具有共同邻居的边之间的两种极值情况,提出了极值非相邻边的边相似度计算方法;使用拓展的模块度评价指标来改善层次聚类算法的划分结果,并提出了极值非相邻边的边聚类MLC算法;在真实网络上的实验结果表明,MLC算法能够发现具有良好模块度的重叠社区结构。本文提出的LCLG算法、LDC算法和MLC算法,能够对复杂网络中的边社区进行发现,进而达到解决重叠社区发现问题的目的,在理论和实际应用方面都具有一定意义。