关键词： 社团检测   谱分析法   近邻传播   局部社团发现   可视化实验平台  

摘要： 摘要 随着复杂网络理论研究的不断深入及在各领域的应用,其所具有的社团结构特征吸引了广泛的关注。寻找和分析复杂网络的社团结构对于反映和理解整个网络的构成和功能有重要的意义。本论文主要研究社团结构检测问题,提出了基于谱分析法和近邻传播的算法、基于局部发现的算法两种检测方法,并建立了可视化实验平台。 论文对传统的Normal矩阵谱分析法及近邻传播算法进行了研究。传统的Normal矩阵谱分析法在网络社团结构不明显的情况下难以得到理想的结果,针对这个问题,论文提出了一种基于谱分析法和近邻传播的社团检测算法。该算法采用近邻传播算法对多个Normal矩阵特征向量的元素进行聚类分析,根据聚类结果来获得整个网络的社团检测结果。这种基于谱分析法和近邻传播的算法在无需预先知道社团数目的前提下对于社团结构不明显的网络也具有较好的检测效果。 论文针对目前部分算法时间复杂度较高、无法对大规模网络进行检测的问题提出了一种基于局部发现的社团结构检测算法。论文设计了一个用于快速寻找指定节点社团成员的局部社团检测算法,通过对该算法进行扩展,不断将检测出的局部社团成员从网络中移除来进行网络整个社团结构的检测。这种基于局部发现的社团检测算法在不需要预先知道社团数目的基础上具有较好的时间复杂度,并且检测效果也比较理想。 论文设计和实现了一个可视化实验平台,该平台能够对社团检测结果进行可视化显示,并计算相应数据。使用该平台将论文提出的两种算法与GN算法、CNM算法进行对比,实验数据表明,基于谱分析法和近邻传播的算法在无需预先知道社团数目的基础上无论网络的社团结构是否明显都具有较好的检测效果,基于局部发现的算法具有很好的计算效率、无需知道社团数目并且检测效果也令人满意。

关键词： 复杂网络   社团结构   模块密度   社团检测  

摘要： 近年来，复杂网络逐渐成为描述与分析现实复杂系统的重要工具而备受关注。复杂网络的大规模性、强耦合性、局部性等特点促使研究人员通过局部特性来刻画与研究整体特性。其中，社团结构作为一种局部研究方法在计算机科学、生物信息学和社会学等多个领域都有重要的意义。 在社团检测算法中如何有效量化社团划分结果及如何设计出高效、准确的算法是两大关键问题所在。为了解决社团量化的问题，Newman等在对比真实网络与随机网络的基础上提出了模块度函数。尽管最大化模块度函数属于NP-难问题，但绝大多数算法都是基于优化模块度函数。针对于模块度函数存在的分辨极限问题，李等通过对比社团内部边和外部边密度提出了模块密度函数，并证明了该测量标准可以在很大程度上克服分辨极限问题。但是模块密度只能应用于无权图。在真实网络中，给每一个节点赋予相同的权重并不合理。为了克服该缺陷，本文提出了一种泛化的模块密度。并设计出基于优化加权模块密度的模拟退火算法。实验结果表明该测度更加有效的刻画网络社团结构。 为了进一步拓展泛化的模块密度的应用，本文提出了一个基于泛化模块密度函数的可以对蛋白质相互作用网络的功能模块进行检测的算法，并开发出相应的可视化软件。实验结果表明该算法不仅可以快速检测出蛋白质相互作用网络中的功能模块，同时可检测出具有重叠结构的蛋白质功能模块。

关键词： 复杂网络   社团检测   模块化函数Q   分辨率极限   模块密度D   负社团   正则化模块密度函数NMD   扩散核   自适应仿射传播   可视化  

摘要： 近年来,由于信息技术的飞速发展,科学家和学者们能够越来越容易地在现实世界中收集到高通量的网络数据,这使得复杂网络的研究变得炙手可热起来。除了Watts和Strogatz在1998年发现的小世界特性以及Barabasi和Albert在1999年发现的无标度(尺度)特性外,网络的社团(社区、模块)结构特性被认为是复杂网络中最重要的统计特性之一。目前,关于网络中的社团仍然不存在统一的定义,通常指的是满足下面条件的节点子集：子集内部节点之间具有稠密的连接,而与子集外部的节点具有稀疏的连接。研究表明,网络的这种社团结构与某些功能属性有着紧密的联系,比如网络的鲁棒性和信息快速传递特性等。因此在网络中描述和检测这些社团结构具有重要的实际意义并已成为近几年来的研究热点。 本论文中,我们主要关注复杂网络中社团结构检测相关问题的研究,取得的主要研究成果如下： 1.提出了一种新的社团检测方法-JEOMD。该方法以加入惩罚项的模块密度函数D作为指标函数,并使用跳跃极值最优化方法来优化该指标函数,能够得到网络的层次分割结果。在一组真实网络上的实验表明,与基于模块化函数Q的优化方法相比,JEOMD方法能够更有效地检测出网络中存在的不同层次和不同规模的社团结构。在该组真实网络及其对应的随机网络上的对比实验表明,加入惩罚项的模块密度函数D作为社团检测的指标函数在一定程度上比模块化函数Q更有效。 2.提出了一个新的衡量社团划分质量的指标函数,称之为标准化模块密度(normalized modularity density-NMD)。在示例网络中证明了NMD能够改善模块化函数Q中存在的分辨率极限问题;证明了NMD与图分割中广泛应用的normalized-cut目标函数存在着紧密的联系,即当社团数目m已知时,最大化标准化模块密度相当于最小化目标函数normalized-cut。使用改进的模拟退火算法优化指标NMD。在一组模拟网络上的实验表明,与基于模块化函数Q的优化方法相比,基于NMD的方法能够取得更高的检测正确率;在一组真实网络上的实验表明,基于NMD的方法能够检测出网络中更精细的模块结构,从而为NMD能够改善Q的分辨率问题提供了更进一步的证据;把指标函数NMD和D推广到其加权形式NMDω和Dw,并用于在加权网络中进行社团检测。分析了加权模块化函数Qw同样存在分辨率极限问题;指出了加权模块密度函数Dw存在的负社团问题;在两个实例网络上证明了NMDω不仅能够克服Qw中存在的分辨率极限问题,而且能够避免Dw中出现的负社团问题。为了比较指标NMDω与Qw和Dw在加权网络社团检测中的性能,使用模拟退火算法实现三个指标的优化。在一组模拟网络上的实验表明,优化NMDω指标能够取得比优化Qw和Dw更高的检测正确率;在一组真实网络上的实验表明,优化NMDω指标,不仅能够从加权网络中检测出精细尺度下的社团,尤其是优化Qw所不能检测出来的小而稠密的社团,而且能够避免优化Dw时出现的负社团问题。 3.提出了一种基于自适应核仿射传播的网络社团检测方法-AKAP。在该方法中,标准化的马尔可夫扩散核(Markov diffusion kernel)被用来隐式地衡量节点之间的非相似度,引入自适应仿射传播方法优化得到的非相似度矩阵。在模拟网络上的实验表明,与Newman快速算法相比,AKAP方法能够取得更高的检测正确率;在一组真实网络上的实验表明,AKAP方法能够有效地检测出网络中存在的有意义的社团结构和包含的社团数目。 4.提出了一种有效的网络节点的可视化方法。在该方法中,定义了一种新的节点间距离,将得到的距离矩阵作为全局保形映射Isomap的测地线距离,应用Isomap方法得到网络的二维可视化结果。在模拟网络上的实验表明,与基于能量模型的可视化方法相比,我们的方法能够更好地保持原始网络中节点的局部和全局相似性,且当网络具有清晰的社团结构时,得到的二维可视化点集也具有紧凑的聚类特性,因此能够从可视化结果中判断原始网络是否具有社团结构特性,也可以对可视化的结果继续采用传统的聚类方法进行聚类以得到网络每个社团的具体成员。