基于图论的复杂网络社团挖掘与结构分析

摘要

网络科学是当前研究现实世界事物之间关系的有力工具之一。将复杂系统建模为复杂网络是进一步分析和研究现实世界对象之间关系的前提，其中点表示复杂系统中的对象，边表示对象之间的关系。面对建模成的复杂网络，迫切的问题是探索网络中蕴含的信息，从中等尺度角度揭示网络的组成及其物理意义，即如何从复杂网络中提取元数据组。元数据组是一组具有真实物理意义的节点，可通过实验验证节点的各种子集是否具有相同或相似的功能提取元数据组。由于材料成本、人工成本、时间成本等客观限制，面对当前的海量数据这种枚举式的验证是不可能完成的任务。因此人们将目光转向计算的方法，具体的流程是先将要研究的复杂系统建模成复杂网络，对其中的元数据组进行建模如通常建模为社团或模块，并设计相应的社团挖掘算法。通过计算方法，可方便、快速、低成本地提取复杂系统中的元数据组。本质上计算方法包含两个核心科学问题:首先是如何定义社团，即根据网络中元数据组的特性怎样描述社团的问题，如传统地将社团定义为内部边连接紧密外部边稀疏的稠密子图;其次是如何设计出高效的社团挖掘算法。
　　本文主要基于图论围绕社团挖掘的两个核心科学问题开展研究，提出了边反三角中心性并基于此设计了社团挖掘算法EACH，定义了两种新型社团，即Cograph社团和2-club社团，并设计了相应的挖掘算法EPCA和DIVANC，最后给出2-club社团在蛋白质相互作用网络中功能模块结构分析中的应用。主要内容详述如下:
　　1.针对当前经典的社团挖掘算法主要基于内紧外松的社团设计，且较多的考虑如何设计衡量社团‘内紧’的相关指标而对‘外松’关注不够的问题。本文从路径外切的角度提出用来衡量社团外松程度的边反三角中心性，进一步基于此设计划分的社团挖掘算法EACH。边反三角中心性定义为该边参与形成的P4（由4个节点，3条边组成的简单路径）数目与该边参与的可能的P4数目之比。EACH迭代地删去边反三角中心性最高的边直到当前所有边的边反三角中心性全部为0，并基于孤立点处理策略将删边过程中的孤立点加入到当前合适的连通分支中，输出的连通分支即为社团。该算法简单高效，挖掘的社团紧凑，物理意义显著。
　　2.以稠密子图为中尺度结构研究复杂网络中元数据组时忽略了元数据组内部的结构，然而其对理解该元数据组的功能形成机制及运作模式至关重要。为了探索元数据组各成员之间的内部拓扑结构，定义了具有图论特征的Cograph社团，其结构唯一地对应着Cotree。基于Cotree，可进一步清晰地揭示Cograph社团中规模和层次可变且结构等价的子结构，为用户提供从微观尺度到中观尺度连续观察社团内部结构构造的独特视角。本文提出边P4中心性并基于此设计了挖掘Cograph社团的划分算法EPCA。边P4中心性定义为该边参与形成P4的数目，由于P4是由4个节点3条边顺序相连组成的简单无环路径，所以若边P4中心性较大，这条边可能是连接社团之间的边。EPCA迭代地删去边P4中心性最高的边，删到当前网络中所有边的边P4中心性为0停时结束，当前连通分支全为Cograph，输出其作为Cograph社团。源于边P4中心性，EPCA计算成本低、无参数、不依赖任何外部的度量。
　　3.面对当前复杂网络社团挖掘研究中遇到的挑战:内紧外松的稠密子图并不能刻画元数据组的本质特征，以及受蛋白质相互作用网络中的元数据组由稠密的相互作用三元组模体组成启发，本文定义了富含相互作用三元组的2-club社团刻画复杂网络中的元数据组。2-club社团是连通的2-club，而2-club是直径为2的子图。基于边小生境中心性设计了算法DIVANC挖掘2-club社团，进一步提出简单的两步重叠策略将DIVANC扩展成可挖掘重叠的2-club社团。构造边小生境中心性时考虑其参与的P4数目和其参与形成的三角形数目。边小生境中心性较大，该边可能是社团之间的边。DIVANC迭代地删去边小生境中心性最高的边，删到当前网络中所有边的边小生境中心性为0停时结束，当前连通分支全为2-club，输出非重叠2-club社团，若需要重叠2-club社团，执行两步重叠策略，得到重叠2-club社团。
　　4.透彻地理解PPI网络中的功能模块仍然是当前系统生物学研究中的一个重要挑战。针对当前大多数关于模块的分析主要集中在如何从整个PPI网络中挖掘具有生物意义的功能模块，而较少关注其内部结构，没有给出其内部结构与功能的关联分析的问题，本文基于图论分析功能模块的内部结构，揭示功能模块的相关特征情况，并进一步推断其在整个PPI网络中的功能，给出了理解PPI网络中功能模块组织结构和特性分布的新视角。

目录

声明

摘要

插图索引

表格索引

符号对照表

缩略语对照表

第一章 绪论

1．1 研究背景与意义

1．2 研究进展与存在问题

1．2．1 国内外研究进展

1．2．2 存在问题

1．3 本文研究内容及组织结构

1．3．1 研究思路与主要贡献

1．3．2 本文组织结构

第二章 基于边反三角中心性的社团挖掘算法

2．1 引言

2．2 边反三角中心性定义

2．3 社团挖掘算法EACH

2．4 实验结果与分析

2．4．1 数据及评价指标

2．4．2 边反三角中心性与其它中心性比较

2．4．3 算法的性能测试

2．5 本章小结

第三章 Cograph社团及其挖掘算法

3．1 引言

3．2 Cograph社团的定义

3．2．1 相关术语

3．2．2 Cograph社团

3．3 Cograph社团的性质

3．4 挖掘算法EPCA

3．4．1 边P4中心性

3．4．2 EPCA算法步骤

3．5 实验结果与分析

3．5．1 数据及评价指标

3．5．2 比较算法

3．5．3 合成网络SN和社交网络

3．5．4 生物PPI网络

3．5．5 内部结构分析

3．6 本章小结

第四章 2-club社团及其挖掘算法

4．1 引言

4．2 2-club社团的定义

4．2．1 富含三元组的子图

4．2．2 2-club社团

4．3 2-club社团的挖掘算法DIVANC

4．3．1 边小生境中心性

4．3．2 算法DIVANC

4．3．3 重叠社团挖掘

4．4 实验结果与分析

4．4．1 数据及评价指标

4．4．2 算法有效性验证

4．4．3 算法特性分析

4．4．4 边小生境中心性及重叠社团性能

4．5 本章小结

第五章 基于2-club社团的PPI网络功能模块结构分析

5．1 引言

5．2 功能模块挖掘及2-club社团子类

5．2．1 挖掘算法

5．2．2 2-club社团子类

5．3 2-club社团子类功能模块特征分布

5．3．1 模块各子类数量占比

5．3．2 功能模块的密度及生物匹配分析

5．3．3 拓扑中心性分析

5．3．4 模块生物功能分析

5．4 功能模块在PPI网络中的作用

5．4．2 中心模块CT4和SC1

5．4．3 协调模块SC2

5．4．4 边缘模块CT3

5．4．5 区域中心模块CT2

5．4．6 跨区域中心模块和边缘模块CT1

5．5 本章小结

第六章 结论

6．1 本文工作总结

6．2 未来工作展望

参考文献

致谢

作者简介

攻读博士学位期间的研究成果