论文部分内容阅读
在复杂网络的研究领域里,社区发现是热门的研究方向,研究划分复杂网络的社区结构,对于分析网络中的结构、功能和演变具有非常重要的作用。复杂网络的社区,即是一些复杂网络中紧密相连的子网络,外部的网络连接相对稀疏。社区结构,存在于社交网络、生物网络、铁路网络与论文引用网络等网络中,能够反映出复杂网络里的动态特征和功能。对复杂网络进行社区结构的挖掘,可以应用于各种各样的领域中,比如说个性化推荐、蛋白质功能检测、交通网络规划与信息检索等。
在社区发现领域中,近些年的发展中涌现出不少优秀的算法,解决了大部分的网络划分社区的问题。但是,对于一些具体的网络问题,比如说重叠社区和时间复杂度等问题,仍存在着识别重叠社区中重叠节点稳定性不高、局部网络核心子群不能正确识别与大多数社区发现算法迭代之后时间复杂度太高等问题。
针对上述复杂网络的社区发现存在的问题,本文通过研究复杂网络的特性与社区结构等方面,对前人的算法引用一些新的思想进行优化,提出了两种基于复杂网络的社区发现算法。本文主要的工作与贡献如下:
第一,针对COPRA算法更新随机、稳定性较差等缺陷,本文提出了一种基于标签传播的重叠社区发现算法(COLBN)。该算法通过遍历每个节点来计算节点的值,找到基准节点确定划分社区数量。然后,利用基准节点为邻接节点更新标签来识别重叠节点,当寻找到所有重叠节点后即可划分出重叠社区。本文利用神奇湾中宽吻海豚网络数据集和关于美国政治的书籍数据集,和COPRA算法对比试验,证明COLBN算法显著降低标签传播过程的更新随机性,提高生成网络社区的稳定性。
第二,针对局部网络核心子群寻找困难和社区发现算法时间复杂度高等问题,本文提出了一种基于局部网络的复杂网络发现算法。该算法首先根据源节点寻找到凝聚子群的核心区域,找到凝聚核心之后,需要的是把核心里的边集所连接的所有节点作为一个局部网络社区,再去调用改进的LWP局部社区发现算法进行后续的社区发现算法。在使用世界城市网络和政治博客的数据集进行实验,在使用自定义的评价指标之后,与Clauset算法、LWP算法与LMD算法等经典局部社区发现算法进行对比实验可以发现,该改进算法能够显著降低社区发现算法的时间复杂度,改进算法执行的时间效率。并且进行对比实验时可以确定,该算法具有比较好的稳定性。
在社区发现领域中,近些年的发展中涌现出不少优秀的算法,解决了大部分的网络划分社区的问题。但是,对于一些具体的网络问题,比如说重叠社区和时间复杂度等问题,仍存在着识别重叠社区中重叠节点稳定性不高、局部网络核心子群不能正确识别与大多数社区发现算法迭代之后时间复杂度太高等问题。
针对上述复杂网络的社区发现存在的问题,本文通过研究复杂网络的特性与社区结构等方面,对前人的算法引用一些新的思想进行优化,提出了两种基于复杂网络的社区发现算法。本文主要的工作与贡献如下:
第一,针对COPRA算法更新随机、稳定性较差等缺陷,本文提出了一种基于标签传播的重叠社区发现算法(COLBN)。该算法通过遍历每个节点来计算节点的值,找到基准节点确定划分社区数量。然后,利用基准节点为邻接节点更新标签来识别重叠节点,当寻找到所有重叠节点后即可划分出重叠社区。本文利用神奇湾中宽吻海豚网络数据集和关于美国政治的书籍数据集,和COPRA算法对比试验,证明COLBN算法显著降低标签传播过程的更新随机性,提高生成网络社区的稳定性。
第二,针对局部网络核心子群寻找困难和社区发现算法时间复杂度高等问题,本文提出了一种基于局部网络的复杂网络发现算法。该算法首先根据源节点寻找到凝聚子群的核心区域,找到凝聚核心之后,需要的是把核心里的边集所连接的所有节点作为一个局部网络社区,再去调用改进的LWP局部社区发现算法进行后续的社区发现算法。在使用世界城市网络和政治博客的数据集进行实验,在使用自定义的评价指标之后,与Clauset算法、LWP算法与LMD算法等经典局部社区发现算法进行对比实验可以发现,该改进算法能够显著降低社区发现算法的时间复杂度,改进算法执行的时间效率。并且进行对比实验时可以确定,该算法具有比较好的稳定性。