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