论文部分内容阅读
自然界中存在大量的复杂系统,如生态系统、网络系统、通信系统和经济系统等。这些复杂系统往往是由多个交互的单元组成,这些单元之间存在一定的联系。为了了解复杂系统的功能和行为、各个单元的相互作用方式,必须借助网络进行研究。复杂系统中的单元对应为网络中的点,而各个单元间的联系则对应为网络中的边,由于复杂系统节点数目庞大,对应网络中节点数目较多,这样的网络被称为复杂网络。随着复杂网络研究的深入,研究学者们发现复杂网络有较多结构特征,而社团结构是其最重要特征之一。复杂网络的社团结构不仅能够帮助我们理解大规模网络的拓扑结构,还能反映其对应的现实复杂系统中各单元、模块的功能,为现实世界中复杂系统的复杂性研究提供十分重要的意义。因此,复杂网络中社团结构的识别成为研究复杂网络的热点话题之一。 目前研究学者们已提出很多社团结构识别算法并将其应用到实际网络中,但是算法还存在一定的不足。本文主要从算法的时间复杂度、算法识别效果以及算法初始条件方面进行改进: (1)基于中心节点的局部社团识别算法。算法首先计算网络中各节点的度和聚集系数,选取网络中度最大且聚集系数也最大的节点作为中心节点,并将其作为独立的起始社团,同时将其加入已访问节点集合。然后更新当前社团的邻居节点集合,计算邻居集合中节点与社团的连接强度,通过不断地将连接强度最大的节点加入社团,网络的局部社团结构被识别出。该算法只需要知道少量的网络局部信息就能将社团识别出,时间复杂度较低,将该算法应用到人工网络和社团结构较为明显的实际网络,识别出的社团效果较好,实验分析验证了算法的可行性。 (2)基于相邻节点相似度的社团结构识别算法。针对已有相似度构造方法的不足而提出改进的相邻节点相似度,该算法将相邻节点相似度与社团强度的量化定义结合,通过不断删除相似度矩阵中最小值元素对应的边,最终将网络中符合要求的社团识别出。将本文算法与其他算法作比较,可知算法识别出的社团结构效果较好,同时算法开始时不需要提前知道社团的数目,时间复杂度较低。将算法应用到人工网络和现实网络中,实验分析验证算法的准确性。