组合方法在网络群体结构划分中的应用

摘要

自然科学、社会学和技术领域里的许多复杂系统都可以用网络来表示,因而近年来关于网络的研究引起了各个学科学者们的极大兴趣。现实网络(real-world networks)在统计意义上的一些共有结构特性得到了广泛而深入的研究。群体结构即是这些性质中的一种,它也是本篇博士论文的主要研究对象。 群体结构反映的是网络中一些点集的如下特征：点的集合的内部连边十分密集,而集合与集合之间的连边较为稀疏。这也成为关于群体结构的一个基本的定义。群体结构的研究对于生物、科技和社会网络的结构认知均具有十分重要的意义；不仅如此,网络群体结构的挖掘还有利于对网络中的个体功能特征进行探索,因而具有重要的理论价值和广阔的应用前景。虽然关于群体结构的量化定义至今尚未在学术界达成共识,但是在上述基本定义的基础上,学者们开展了大量的工作。自2002年Girvan和Newman在《美国科学院院刊》(《PNAS》)上发表了一篇开创性的文章以来,六年间,仅是专门研究群体结构划分方法的文章即有十余篇刊登在《美国科学院院刊》和《自然》(《Nature》)杂志上；包括这些方法在内,至今已知的划分方法达到四十余种；此外,应用这些方法对各学科领域网络的群体结构进行研究的文章更是难以计数。然而,在目前已知的方法中,除了一类基于指标优化的方法(以CNM方法为代表)之外,其它方法均无法在脱离外部参数和人为干预的情况下得到自然的群体结构。这也促使我们以研发新方法为基础开展工作。 本篇论文由三个部分组成：在第一部分(第一章和第二章),我们提出了-种新的群体结构划分方法；第二部分(第三章和第四章)主要给出了该划分方法的应用；应用又大致分为两个方面：一是进行划分方法性能测试与比较,主要通过应用各种方法(含本方法)于已知结构的现实网络和人工网络来实现,二是网络群体结构挖掘,即直接针对具体网络进行群体结构分析。第三部分(第五章)探讨如何进行群体结构的比较和评估。这三个部分的研究内容也正是当前群体结构划分领域的三方面主要研究内容。 在第一章,我们回顾了群体结构划分问题的发展历程,介绍了群体结构的不同定义,并分类综述了近六年来部分有代表性的群体结构划分方法。 在第二章里,我们提出了一种群体结构划分的新方法,即LP方法,该方法基于组合优化中的线性规划理论。这是(截止相应成果发表时)在该领域中,第一种将线性规划应用于网络群体结构划分的方法,也是第一种能够不依赖于外来参数和人为干涉,独立地给出单层群体结构的方法(CNM方法给出多层群体结构)。我们的模型最终可表述为基于单个控制参数的一组线性规划问题。我们证明了该方法关于控制参数的收敛性,并确定了参数的上界,从而也证明了该方法在实际应用中的可行性。基于理论分析,我们还讨论了在实际运用中如何提高LP方法的效率。在第三章中,依照目前通行的评估方法,我们用三组测试证明了LP方法具有比当前的主流算法更好的品质。在第一组关于若干著名的现实基准网络的试验里,相对于GN算法(被认为是分析现实网络最为有效的方法之一)和计算机科学领域的图划分算法,我们的方法均得到了更优的结果。CNM方法是除LP方法外唯一能自然地给出群体结构的算法,因此我们将其与LP方法进行比较。为此我们设计了第二组测试网络,即“扰动试验网络”,并用四种指标对群体结构的结果进行了评估,结果证明我们的方法相对于CNM方法有更好的表现。第三组可信度评估测试基于一组被广泛应用的基准人工网络,即“四群组网络”。所有三组测试均表明,LP方法不仅具有理论上的创新性,而且在实际应用中对于网络群体结构的判定具有高度的准确性。 在第四章中,我们构造了一类特殊的基因网络,即GO网络。我们研究了LP方法和CNM方法对斑马鱼(Zebrafish)GO基因网络的功能模块的探知能力。我们讨论了得到的基因群体结构的生物学特性,并揭示了群体结构划分方法对于基因功能认知的重要意义。 在第五章中,我们首先介绍了现有的各种比较(对于同一个集合的)多个划分的量化指标,以及“单点转移距离”指标的已知结果。出于实际需要,我们提出了“子集转移距离”这种新指标,随后用组合分析的方法,分四个区间完整地确定了该指标的上界,并构造了达到上界的特例。上界的确定使得我们能够将该指标正则化,从而更加有效的利用这种指标。这不论是对于评估网络群体结构的结果,还是对于比较群体结构划分方法,均具有十分重要的意义。

目录

文摘

英文文摘

声明

Chapter 1 Introduction

1.1 Background

1.2 Definitions and notations

1.3 Overview of known results

1.4 Outline of this thesis

Chapter 2 Linear-Programming Based Approach Towards Detecting Community Structures in Networks

2.1 Introduction

2.2 Forming cliques

2.3 A linear programming approach

2.4 Feasibility of our method

2.5 Theoretical foundation and interpretation

2.6 Practical improvements

2.7 Remarks

Chapter 3 Reliability Estimation of Our Method

3.1 Existing technique

3.2 Experiments on real-world networks

3.3 Perturbation tests

3.4 Experiments on other artificial networks

3.5 Conclusions and remarks

Chapter 4 Detecting Community Structures in Gene Networks

4.1 Introduction

4.2 Construction of Gene-Ontology annotation network

4.3 Detecting communities in the gene network

4.4 Conclusions

Chapter 5 Measures for Comparing Community Results and Their Bound

5.1 Introduction

5.2 Transfer distance and known bounds

5.3 Subset transfer distance

5.4 Upper bound for subset transfer distance

5.5 Partitions achieving the bounds

5.6 Maximum distance with upper-bounded number of classes

5.7 Conclusions

Bibliography

致谢

个人简介