马尔可夫链方法随机图

文摘

马尔可夫链方法研究随机增长图表和应用提出了一些流行的模型,发现在生物学和其他地方使用。对于大多数随机增长图表用于生物学,目前尚不清楚的图形或属性图收敛(在某种意义上)作为顶点的数量变大。特别是,我们的研究程度的行为序列,即顶点的数量与程度在大型图表,并将结果应用于部分复制模型。我们进一步说明结果应用到真实的数据。

1。介绍

在过去的十年里,网络发挥了突出的作用在许多不同的学科包括理论物理、技术、生物学和社会学(1- - - - - -9]。尤其是在生物学、网络已经成为基本的描述复杂的数据结构。至少在一定程度上,网络的吸引力可能是由于这样的事实,除了基于严格的数学基础(10- - - - - -14),他们还提供了一种方便的图形表示的数据允许目视判读。复杂的数据结构的例子,可以被网络包括生态食物链,性伴侣网络社会学、生物学和蛋白质相互作用网络。

规范化模型在随机图论Erdos-Renyi随机图,在每一个固定数量的顶点Poisson-distributed数量的链接到其他顶点。一个泊松了的链接数几乎是许多现实的经验观察到网络,和其他模型建议容纳之间的差异理论和观察。巴巴斯和艾伯特(2)提出了一个简单的随机模型,优惠附件(PA)模型,网络逐渐建立了通过添加一个顶点,直到网络到达所需的大小。这个模型能够解释无尺度观察到一些经验网络度分布,但不是很多的其他特性和图案中发现真正的网络(例如,15- - - - - -18])。因此,对于数学和统计分析网络数据,许多其他随机模型被提出,特别是模型类随机增长的图表(下降RGGs;见下一节的定义)的财产份额的PA模型逐步增长。概述不同的模型和它们的属性可以在找到13,16,19,20.]。

虽然PA模型已经严密数学审查(例如,20.),其他RGGs治疗更广泛(例如,[19,21])的上下文中,主要考虑连续时间近似原始离散时间马尔可夫过程(例如,13,22,23])。在这篇文章中,我们具体地址的问题行为的顶点度随着顶点的数量大。针对一类RGGs(包括PA模型),限制程度分布的存在已被证明和分析的形式派生(21]。然而,对于大多数RGGs应用于生物学,尚不清楚是否存在一个极限分布,让它的形式。

生物,这是极大的兴趣知道网络稳定增长,还是程度分布网络的大小是一个函数,即使对大型网络的大小。相关的质疑网络进化的角度达到一个平衡,这样添加新的顶点并没有改变整个网络的连通性。例如,与蛋白质相互作用网络中顶点代表蛋白质和边缘代表物理之间的相互作用蛋白质,这两个场景似乎先天的可能。蛋白质可以进行无限的交互,或者相互作用的数量可能受很多因素限制,如空间,时间,和蛋白质生产速度。随着统计分析复杂生物网络的兴趣对进化和功能性质1,5,9,13,14,24),它也变得感兴趣的理解模型的数学性质。

我们研究一类大型RGGs,允许一个简单的建设,但time-inhomogeneous,马尔可夫链。对于一个给定的RGG,相应的马尔可夫链对RGG可以用来解决问题,例如,关于学位分布的问题。特别是,我们专注于一个特殊的RGG,部分复制模型,它最近被用于生物蛋白质相互作用网络的研究(16,18,25,26),形成了新的和更多的基础生物学上现实的模型(例如,(16,27])。部分重复模型有两个参数(和),我们给链遍历或瞬态的条件。此外,time-inhomogeneous马尔可夫链的基础上,我们定义了一个time-homogeneous马尔可夫链和连续时间,time-homogeneous马尔可夫过程,证明这些,一般来说,更容易学习和应用比原来的链。证明依靠一般理论的离散马尔可夫过程,这使得它很容易为其他RGGs证明相似的结果。

最后,我们应用我们的结果真正的蛋白质相互作用数据的集合。

2。RGGs

一个RGG是一个马尔可夫链等无向图正好有顶点,顶点的集合是顶点的集合的一个子集的对所有。请注意,我们所做的不需要的边的集合的边的集合的一个子集。

表示由预期的程度的顶点数在时间。因为,通过假设,图正好有顶点,顶点的预期相对频率的学位在时间是。对于许多RGGs,可以推出一个递归公式,通常称为主方程(13]。在这里,我们考虑一个非常通用的类的主方程 在哪里对所有是一个真正无限矩阵为等所有列和相同数量。此外,假设为合适的实数那 与为。后者条件保证顶点最多只能增加一个程度。通过建设,为,因此实际上是一个矩阵。我们假设条目(2。2在这个子矩阵)是积极的。

一个特定的模型满足上面的条件是部分复制模型(细节部分中找到4)。是由主方程 对于其他几个模型,主方程采用了类似的形式。在这些模型是duplication-divergence模型(16),一个近似duplication-mutation模型(22,23],[讨论的模型21)在一个合适的修改(见部分5.2)。一般来说,(2。1时)是实现预期的一个顶点变化程度取决于程度,而不是另一个顶点的度。

它紧跟着从(2。1), 在哪里的转置,假设所有行总和为。由此可见, 也就是说,和矩阵描述一个马尔可夫链转移概率随时间变化。

命题2.1。假设对所有。如果逐点的所有,然后满足

证明。的第二部分费托引理的命题是一个简单的应用程序。通过使用(2。4)的定义,,接下去 对于一些实数,还有待证明。请注意, 通过使用采查罗引理,我们得到的

考虑到跳链相应的马尔可夫链,马尔可夫链的转移概率为,除非在这种情况下,概率是0。跳链的概率由长期有效的过渡 和对所有。如果,然后。偶尔,我们考虑一个稍微修改跳链与定态跃迁概率(仍然)是允许在同一个国家有积极的概率。

如果一个平稳分布跳链的存在,它满足 假设并将。然后我们获得 因此方程的解的命题2。1。此外,我们可能正常化得到一个分布,因此(2.11)和(2.12)可用于传输跳链的平稳分布的极限time-inhomogeneous马尔可夫链,反之亦然。

在我们的主要例子,部分复制模型(见部分4细节)和 因此假设是实现如果。

3所示。一个连续时间近似

在本节中,我们表明,time-inhomogeneous连续时间马尔可夫链收敛,time-homogeneous马尔可夫过程在一个合适的时间转换。

表示由的时间th跳time-inhomogeneous链中的一个给定的时间后,让它跳跃状态。集和链时的状态。进一步简化符号,介绍和。

请注意,在时间,在状态的概率是。特别是,如果我们让,然后 对于大型和。现在考虑转换。由此可见, 作为。也就是说,在极限情况下,转换后的等待时间是指数分布的参数。

命题3.1。让,,time-inhomogeneous马尔可夫链的价值,在那里和表示的整数部分。在时刻0,。固定,这个过程收敛于一个连续时间,time-homogeneous马尔可夫过程。

证明。显然,这个过程,,马尔可夫链的定义。让的时间th跳,和在上面的符号。它遵循从(3.2), 为。(下标在用于强调隐式依赖项的)。回忆的过渡概率(2.10)在原始跳链。它紧跟着, 在哪里。结合(3.3)这表明,极限,跳的速度从是。更准确地说,它证明了这一点,,time-homogeneous收敛于一个连续时间马尔可夫过程和转移率矩阵给出的为,。这笔钱确实是有限的,因为假设为(见部分2)。

注意,一个静止的方程连续时间马尔可夫链满足方程的命题2。1与取而代之的是。

4所示。部分重复的模型

考虑到模型,在那里是一个简单的图顶点,是获得在以下方式:介绍一个新的顶点并选择均匀。的概率,连接和。是彼此独立的,每个邻居的连接来的概率。

在本节中,我们在前一节中列出的路径。也就是说,我们首先找到相对应的跳链部分复制模型。正如我们已经提到的部分1是由,主方程

可以看出在以下方式:第一项对应于一个顶点的度的情况保持其学位,是这种情况,除非发生的两件事之一:(i)顶点复制和收到的链接新的顶点,或(ii)它收到一个链接,因为它的一个邻居复制。这两个事件的概率和,分别。同样,第三项对应于一个顶点的度的情况得到一个新的链接在上述的方法之一。剩下的两个术语对应新顶点度的情况。新顶点的程度当一个顶点的度复制和接收链接的邻居顶点,没有链接复制到复制的顶点,或者如果一个顶点的度复制和收到的链接复制顶点到底是什么复制的邻居顶点的链接。

的情况下和研究了在19,26),分别。但是请注意,主方程给出了(26)是不正确的。对于一般,讨论的模型18]。它紧跟着, 我们,为了简化符号,定义 从(4所示。2),我们可以读出的描述矩阵。满足其条目 和否则。一个简单的计算显示 从它,从状态的概率是 出于这个公式,我们允许跳链保持状态的概率,它遵循过渡概率在修改后的跳链满足 和否则。

特别是,链是不可约当且仅当。如果,0是吸收,如果,0是不可以从任何其他国家。如果状态0将被忽略,结果链是不可约的。

4.1。分类的状态

我们首先回忆起一个定理从[28]。这个定理是新配方在[29日),我们将使用配方。如果,然后我们忽略状态0,因为在这种情况下为零,下面定理中的条件规定保持不变。

定理4.1。让是一个马尔可夫链。如果存在一个非负实数序列和一个整数这样 然后链最终复发。

应用于部分重复模式定理指出,如果有一个序列的非负实数这样 然后,如果,最终吸收0的概率是1。如果这个定理的结论是,所有国家都是持久的。

解决方案的日志表示自然对数,被称为ω不变,我们表示了。我们有。

命题4.2。让在部分复制模型。如果,最终吸收0的概率是1,如果马尔可夫链是持久的。

在[26据称,存在一个极限分布不同于我们找到。

证明。让。然后是一个非负实数序列,因此它可以表明,选择的和在命题,序列满足(4所示。9)。自是一个凹函数,詹森不等式意味着对于一个积极的随机变量。特别是,使用此二项分布的随机变量,我们得到的 因此我们只需要证明不等式的右边是小于或等于为。今年5月,被重写为 这前两个条件收敛到,而剩下的两个条件收敛和,分别。在这里我们使用 注意,因为假设,我们有,因此不平等(4.11适用于所有。

由于零是唯一吸收状态,它遵循的,极限分布形式,。推断出其他值的马尔可夫链的行为,我们首先回忆结果证明(30.]。

定理4.3。让是一个不可约,非周期的马尔可夫链。如果存在一个正实数序列和一个整数与 链是短暂的。

让表示黄金比例共轭。也就是说,独特的正实数吗令人满意的,。我们有。

命题4.4。让在部分复制模型。马尔可夫链是短暂的。

证明。把对所有。然后对所有,。因此,为了应用定理4所示。3,我们只需要确认是一个解决方案的不平等(4所示。9)。
它遵循一个简单的计算 这样是一个解决方案如果这个不等式的右边是小于或等于为。这相当于 和左边是收敛的作为。自,接下去,因此不平等(4.15适用于所有。

让这样链是不可约的。你可以问的链遍历。由命题4所示。4,一个必要条件。然而,正如我们将看到的,这可能是不够的。看到这,我们首先回忆起另一个定理(28]。

定理4.5。让是一个不可约,非周期的马尔可夫链。如果存在一个和一个非负序列这样的实数 然后遍历链。

在部分复制模型中,第二个条件的定理以来总是应验了为。让表示链时的状态。如果存在和这样 那么这个,加上在定理,将工作4所示。5。这是在[指出28]。

命题4.6。让。马尔可夫链是遍历。

证明。我们发现 请注意,意味着,因此对于所有足够小。也就是说,大,(4.17)是实现。

一般来说,这不是一项容易的任务才能真正发现跳链的平稳分布或time-inhomogeneous马尔可夫链。为,一个试图解决(2。4)取得了19]。他们认为收敛和显示,在这种假设下,限制()有一个幂律的尾巴。然而,这并不是建立一个平稳分布的存在。此外,他们提供的幂律事实上不是一个分布。在特殊的情况下,平稳分布为。

很自然的问的值会发生什么不包括在上面的命题。总体而言,这是很困难的。然而,如果不是命题的最大上限吗4所示。2必须的特定选择,罪魁祸首。的确,詹森不等式的使用提供的损失并不严重。这可能是在以下方式:表示的中央的二项分布的随机变量与参数和。从[31日),我们得到,通过扩大作为一个泰勒级数,接下去。

4.2。应用蛋白质相互作用网络

我们使用计算机程序开发(18)来估计局部复制模型下的参数不同的蛋白质相互作用网络。的恶性疟原虫(恶性疟原虫)获得数据集(32),剩下的数据从数据库下载的相互作用蛋白(http://dip.doe-mbi.ucla.edu)。奇怪的是,我们注意到,根据命题4所示。6,所有对和对应于各态历经的马尔可夫链,这表明网络稳定顶点数量增加。

为一个网络,恶性疟原虫50,我们进行了一些进一步的实验网络模拟与相同数量的顶点恶性疟原虫(1271)和度分布计算。所有模拟都开始从最初的网络连接的两个顶点的边缘。此外,1271年相应的马尔可夫链进行运行,和度分布进行了计算和比较,从模拟获得网络的度分布。在这里,马尔可夫链的初始状态是1。的长度不一,如图1。

模拟表明,马尔可夫链方法可以用来近似程度分布。这是特别有用的内存使用方面的大型网络的仿真;存储顶点之间的联系需要内存容量成正比的顶点次数平均连接数。相应的马尔可夫链模拟需要内存容量成正比的当前值链。

经验分布程度恶性疟原虫显示部分复制模型并没有提供一个完美的健康。例如,不包含在零度顶点数据集(实验者的选择),这需要纳入模型。

5。其他模型

我们有其他模型应用马尔可夫链的方法,并在本节中,我们简要介绍一些结果。

5.1。Duplication-Divergence模型

的duplication-divergence模型是一个部分的复制模型的扩展,它已被用于分析蛋白质相互作用网络的(15,16,27,33]。然而,该模型比部分复制模型稍微复杂,和它有三个参数,,。一步在这个模型如下:选择一个顶点图中均匀,添加一个新的顶点。连接和的概率,并创建一个边之间的和每当有一个优势之间的顶点和。现在修改对在以下方式:彼此独立的概率,保持边缘;否则,概率,保持和删除和概率,保持和删除。

可以推出一个主方程,经过修改后的跳链的建设。在这种情况下,转换概率满足 和否则。在这里,的二项概率(4所示。3),取而代之的是。

为了应用定理4所示。1,我们把。它遵循从简单的计算,再次利用詹森不等式是一个解决方案(4所示。9)如果和满足 注意,在特殊的情况下和左边的不平等可以减少早些时候,一样的不平等。实际上,对于模型部分复制模型。也就是说,只要或,解决方案(5.2)必须satisfty。为一个确切的上限很难获得。这些值的,解决方案小于和达到最小为。

5.2。另一个类的模型

我们相信,马尔可夫链的方法提出了可用于推断其他类的行为模型。在[21),简单的模型与主方程的形式 在哪里和都是非负的数字,进行了研究。由此产生的主方程的相对频率可以用矩阵形式 在哪里,和所有的数字组成的列向量和,分别。矩阵是由

注意,分块矩阵的列(5.4)和。也就是说,当除以这个矩阵的转置,代表一个马尔可夫链转移概率随时间变化。我们确定了州的可数集人工的状态账户的第一行和第一列分块矩阵。

我们可以计算出相应的跳跃过程,事实证明,其转移概率是长期有效的。我们可以摆脱通过简单地忘记我们花的时间。也就是说,对于,我们替换的总和,这导致一个马尔可夫链与过渡给出的概率

这些跳链实际上是所有遍历,time-inhomogeneous平稳分布的马尔可夫链在[派生21]。

5.3。其他的延续

还是其他模型不属于本文介绍的条件和假设。例如,主方程的最一般形式的duplication-mutation模型(22,23)取决于条款的列不要总和相同的号码吗因为术语,因为需求为不满足。

其中的一些问题可能会绕过的成本更多的技术和复杂的博览会,但往往结果需要规定限制的结果。例如,如果列的不要总和相同数量,跳链(2.10)应该被认为是新兴的极限。

此外,你可以选择忽略的秩序在主方程。作为,高阶项的影响往往变得微不足道,证明这样的一个近似。例如,这是duplication-mutation模型。

确认

m·克努曾支持中心在自然科学理论,奥尔胡斯大学。支持c Wiuf丹麦癌症协会和丹麦研究委员会。他们想感谢匿名审稿人的宝贵的建议,改善纸的明确性。