复杂网络社团结构模型与算法及其在生物

雩风三日

复杂网络社团结构模型与算法及其在生物

     自然界中许多复杂系统，如生物分子系统、祸合系统等，皆可抽象成复杂网络。信息技术的迅速发展使得收集和研究海量的网络数据成为可能。随着真实网络数据的大量涌现，通过分析网络的统计性质，研究网络系统结构与功能成为了众多学科的研究热点。目前从整体上分析复杂网络不可行，研究人员将大型网络分解成小规模子网络，通过对子网络的研究来理解、推导网络的整体结构与行为特性。与著名的小世界与无标度特征一样，社团结构特性被公认为是复杂网络中最重要的统计属性之一。社团结构的研究有助于揭示与理解生命体内基因结构与功能关系、设计商业营销策略、维护国家安全等。
" `$ X! B# K0 V2 W    因此，以复杂网络社团结构为研究对象，完善社团结构模型理论，设计社团结构检测算法，拓展社团结构在生物网络中的应用，就成为本文的主要研究内容。具体而言，本文开展以下工作并作出相应的贡献:
    1.针对社团结构量化问题，提出一种泛化模块密度模型，其包含除模块度函数之外的所有测度，为研究社团结构度量标准提供统一的平台。并且证明该模型可容忍分辨极限问题。最后证明优化泛化模块密度函数与加权核I}-均值、非负矩阵分解和谱算法的目标函数是等价的。
    2。由于社团结构的拓扑复杂性，单一的拓扑方式不足以全面刻画社团结构。基于半监督非负矩阵分解算法与模块密度之间的等价关系，提出一种基于半监督策略的非负矩阵分解算法，该方法融合非负矩阵分解与半监督策略。与传统算法对比，该方法可同时利用多种网络拓扑结构相似性，具有更高的准确性与可靠性。
    3.同时检测分层、重叠社团结构对理解网络结构、动态行为分析有着极其重要的意义。为了克服谱性质的局限性，提出一种特征空间谱算法。首先证明网络中节点间的通信性可用网络的特征空间线性表出，奠定算法的理论基础，再利用分层聚类算法提取分层社团结构，利用短回路条数来识别重叠社团。与传统谱聚类相比，该方法在不增加时间复杂度的情况下大幅度提高算法的准确性，并且可同时检测分层、重叠的社团结构。
$ y9 l4 F" ^5 _; |; F; U3 m    4.谱聚类因具有易实现、高准确性、矩阵理论支撑等特点而备受关注，但谱算法的三次方时间复杂度使其无法应用于大型网络。因此，对谱聚类算法进行有效加速是一个非常有现实意义的问题。针对该问题，提出一种社团结构的半监督谱聚类算法，该方法利用半监督先验知识来引导谱聚类算法，通过扩大最大与次大特征值之差来加速谱聚类算法。同时对非传统谱聚类进行综合性对比。
    5.生物网络中社团结构对应具有特定生物功能的复合体或代谢路径。提出两种复合体检测算法:首先利用复合体拓扑结构，将复合体预测问题转化为经典的全团问题，进而提出一种基于图通信性的核一附属结构复合体检测算法;其次分析生物网络中的社会行为特性，验证弱连接与拓扑相似性之间存在负相关性，继而定义基于桥的拓扑相似性，并设计算法提取蛋白质复合体。
    6.挖掘致病模块的动态行为对理解与治疗复杂疾病具有重要的意义。以乳腺癌为研究对象，提取与分析乳腺癌致病代谢路径的动态行为。首先针对乳腺癌不同周期构建时序网络。将时序网络动态模块提取问题转化为最小化嫡问题，并且设计出快速的启发式算法挖掘时序网络中的模块。结果表明:1)动态模块蛋白质信号域富集程度显著高于静态模块;2)动态模块可作为生物标记，显著提升乳腺癌发病周期的预测;3)基因交互动态与基因表达动态无显著性关联关系。

1 X1 ~3 ?( e2 A, p关键词:复杂网络;社团结构;聚类算法;蛋白质复合体;疾病预测
% z& p6 v2 j( m2 K
+ v; Q  V: W7 F& Y( x" \  \( r( I3 e