论文部分内容阅读
摘 要：该文研究了现实网络中的渗流现象，该现象的研究可以用于分析现实中的网络系统，诸如互联网系统遭受攻击以及疾病在人类接触网络中的传播等一系列问题。该文的主要思路是将Karrer等人提出的信息传播算法应用于两个具体的网络，即E-R随机图和美国供电网络，采用迭代法求解方程得出上述网络经历结点打击之后，极大点聚占整网比例的估计值。此后，将该文计算的预测值与现实网络进行对比，并且分析了该算法出现偏差的主要原因。
关键词：渗流 复杂网络 信息传播算法 迭代法
中图分类号：P64 文献标识码：A 文章编号：1674-098X（2017）06（b）-0166-03
渗流，即以相同的概率p对格子或者复杂网络中的边或者点进行随机占据，研究格子或者整网的连通性问题，是统计物理学中最好研究的过程之一。它被用作多孔介质[1]，颗粒和复合材料[2]，电阻网络[3]，森林火灾[4]以及许多其他科学系统的模型。Karrer等人提出了一种新颖的方法，作为输入给定网络的详细拓扑结构，以预测渗流强度的值（和其他宏观观测值，如边占据概率和点占据概率的函数[5]，特别是他们阐明了特定网络的边渗流临界值是非回溯矩阵的最大特征值。Hamilton和Pryadko基于相同的理论方法研究了孤立网络中的点渗流现象[6]，Radicchi[5]分析相了依网络中边和点的渗流模型[7]。该文将Karrer等人提出的信息传播算法应用于两个具体的网络，即E-R随机图和美国供电网络，采用迭代法求解方程得出上述网络经历结点打击之后，极大点聚占整网比例的估计值。此后，将该文计算的预测值与现实网络进行对比，并且分析了该算法出现偏差的主要原因。
1 主要模型
该文主要分析点渗流模型。我们通常使用一个0-1矩阵来描述任何现实网络的拓扑结构，假设一个图总共有N个节点和E条边，（即，如果点i和j相连，则矩阵元素Ai，j =1，否则Ai，j =0）。如果是无向图，则该矩阵是沿主对角线对称的，也就有Ai，j=Aj，i，这样我们可以只用一半的矩阵元素来描述该网络拓扑结构，此外，我们将Ai，i设置为零，这样邻接矩阵的对角线元素都是0，该文所研究的网络全部为无向图。
渗流模型关注的另外一个关键概念即为点聚，假设有两个结点，如果它们之间至少存在一条路径，从其中一个结点出发，沿着该路径可以到达另外一个结点，则这样两个结点同属于一个点距，而整个网络中拥有最大结点数量的点聚，则是渗流模型关注的重点。
在通常的点渗透模型中，每个点都以概率P被激活，也可以理解为P概率表示该点被保留，以1-P的概率被删除，这代表了一种比较普遍的网络打击现象，例如，对互联网中所有的网站都以相同的概率就行攻击，社交网络中以相同的概率删除结点，等等。对于具体的保留概率P而言，P=0，没有节点处于激活状态，因此整个网络中没有任何的点距。对于P=1，所有结点都是激活的，网络中相当于没有结点被删除。
而Karrer等人[5]提出了信息传播算法则着重考虑了上述激活概率，该方法需要对现实网络中的每一条边列出方程，参见图1。现在我们假设对任何一条边，i->j，来表示该边导向的点聚不属于极大点聚的概率，则依据图1；我们有
（1）
特殊的如果j是叶子结点，则我们有。这样，全图E条边总共有2E个方程。这2E个方程可以通过迭代解出来，如果j不是叶子结点，则的迭代初始值设定为0。
在此基础上我们使用来表述结点j不属于极大点聚的概率，此时我们有
（2）
而对于我们关注任意抽取一点，它经历结点打击之后，属于极大点距的概率即为
（3）
2 模型应用
这里选择两个具体的网络来应用Karrer等人提出的算法，第一网络是一个ER随机图，该包括10000个结点，并且任意结点之间出现一条连接的概率是0.0005，这意味着该网络的每一个结点度平均值大致上是5。第二网络是美国供电网络，该网络拥有4941个结点，该网络的数据直接来源于文献[8]。
从图2和图3的对比分析我们发现在ER随机网络中，信息传播算法关于极大点聚占整网全部结点比例的预期值和实际值高度吻合，而在美国供电网络中，信息传播算法的预期值要高于实际值。因而，可以得信息传播算法的预期计算只有在某些网络中非常准确，而在其他网络中则不那么准确。而该算法到底在哪些网络中预期准确，究竟哪些因素造成了该算法的误差，则成为本文下面研究的重点问题。
图2为随机ER图中信息传播算法预期结果与真实结果的对比。其中，S代表在网络中随机抽取一点，该点在经历结点打击之后属于极大点聚的概率。P代表结点激活或者保留概率。图中的实线代表预期值，而圆圈实线代表真实结果。关于真实结果的计算，我们按照1-P在图中随机删除结点，点数剩余图中的极大子组所含的结点数量占原图所有结点的比例。这种删除和计算被重复进行了100次，得出的均值作为真实值。
图3为美国供电网络中信息传播算法预期结果与真实结果的对比。其中，S代表在网络中随机抽取一点，该点在经历结点打击之后属于极大点聚的概率。P代表结点激活或者保留概率。图中的实线代表预期值，而圆圈实线代表真实结果。关于真实结果的计算，我们按照1-P在图中随机删除结点，点数剩余图中的极大子组所含的结点数量占原图所有结点的比例。这种删除和计算被重复进行了100次，得出的均值作为真实值。
3 模型誤差来源讨论
关于信息传播算法，其算法创造者Karrer等人[5]曾经指出，树型结构的网络或者本地近似树型结构的网络中应用该算法的误差最小，或者更为直白地说，当网络中的环数量非常少的时候，该算法应用的效果更好，至于为什么环会导致算法预测的不精确并没有详尽地说明。
该文在研究信息传播算法极其迭代算法时，首先观察了，当P=1的情况，此时，网络未经任何结点删除，可以认为是原始网络、如果该算法对原始网络极大点聚的估计值存在偏差，这种偏差一定会带到结点删除之后，导致结点删除之后的预期值也不准确。此时，公式（1）变成 （4）
按照該算法的代入规则，即如果j是叶子结点，则我们设定 否则设定其初始值为0，我们发现对于所有不存在环的点聚，我们将迭代得出所有以及所有的，这样该点聚所有点不属于极大点聚概率为1，这也意味着该点聚内所有结点都不属于极大点聚。而对于有环的点聚，我们通过迭代得出来导向叶子结点的其他的而整个子组的这意味着该点聚所有结点都属于极大点聚。
这样的一种设置，使得该模型对于两种类型的网络预测效果不佳，第一张情况是整个网络的极大点聚不存在任何的环，这样真实的极大点聚将被当做非极大点聚来处理，计算的误差此时会非常大。第二种情况就非极大点聚的点聚中许多都含有环，此时，这些非极大点聚都会被当成极大点聚来处理，从而导致预期值计算误差增大。
而讲过对两个具体网络拓扑结构的观察我们发现，在随机ER图中，非极大点聚中的环非常少，而极大点聚中确实存在着一定数量的环，因而可以解释ER随机网络中，信息传播算法预期值和真实值的接近程度非常高。而在美国供电网络中环的数量比较多，经过结点打击之后，许多环都散步到非极大点聚当中，这就使得概算在p的某些取值之下显得不够准确。
5 结语
最后我们来讨论一下信息传播算法的应用以及该文的一点小小的贡献。信息传播算法的优势在于对于任何现实存在的具体网络，通过将其拓扑结构作为输入，我们可以预测一下在特定结点保存比例之下，经历结点打击会的网络极大点聚规模。因为现实中这种预测可以发生在实际结点打击之前，使我们对未来打击发生之后网络连通性有一定的预估。与此同时，极大点聚本身代表了某个网络中信息传递的最大范围，对其进行估计显然也有一定意义。由于其他一些研究已经证明了对于结点数量庞大的网络，环出现在非极大子组的概率非常小，这一定程度上保证了这种算法预测效果。而本文的一点贡献在于明确分析得出该算法使用环境，并且对预测误差的产生有了较为清晰的剖析，从而提示后续研究在使用这一算法时，应该首先观察网络拓扑结构是否出现该文提出的两种不适宜采用这种方法的情况，从而更加合理地使用这一方法。
参考文献
[1] J. Machta， Phase transition in fractal porous media[J].Phys. Rev. Lett.1991，66，169-172.
[2] T.Odagaki and S.Toyofuku，Properties of percolationclusters in a model granular system in two dimensions.J.Phys.Cond. Mat.1998，10：6447-6452.
[3] L.de Arcangelis， S. Redner， and A. Coniglio，Anomalousvoltage distribution of random resistor networks and anew model for the backbone at the percolation threshold[J].Phys. Rev. B，1985，31：4725-4728.
[4] C.L.Henley，Statics of a self-organized percolationmodel[J].Phys.Rev.Lett.1993，71：2741-2744.
[5] B.Karrer，M.E.J.Newman， and L. Zdeborov_a， Phys.Rev.Lett.2014，113.
[6] K. E. Hamilton and L.P.Pryadko，Phys.Rev.Lett.2014，113：208701.
[7] F.Radicchi，Nature Phys.2015（11）：597.
[8] D.J.Watts and S.H.Strogatz，Collective dynamics of’small-world’networks[J].Nature.1998（393）：440-442.
关键词：渗流 复杂网络 信息传播算法 迭代法
中图分类号：P64 文献标识码：A 文章编号：1674-098X（2017）06（b）-0166-03
渗流，即以相同的概率p对格子或者复杂网络中的边或者点进行随机占据，研究格子或者整网的连通性问题，是统计物理学中最好研究的过程之一。它被用作多孔介质[1]，颗粒和复合材料[2]，电阻网络[3]，森林火灾[4]以及许多其他科学系统的模型。Karrer等人提出了一种新颖的方法，作为输入给定网络的详细拓扑结构，以预测渗流强度的值（和其他宏观观测值，如边占据概率和点占据概率的函数[5]，特别是他们阐明了特定网络的边渗流临界值是非回溯矩阵的最大特征值。Hamilton和Pryadko基于相同的理论方法研究了孤立网络中的点渗流现象[6]，Radicchi[5]分析相了依网络中边和点的渗流模型[7]。该文将Karrer等人提出的信息传播算法应用于两个具体的网络，即E-R随机图和美国供电网络，采用迭代法求解方程得出上述网络经历结点打击之后，极大点聚占整网比例的估计值。此后，将该文计算的预测值与现实网络进行对比，并且分析了该算法出现偏差的主要原因。
1 主要模型
该文主要分析点渗流模型。我们通常使用一个0-1矩阵来描述任何现实网络的拓扑结构，假设一个图总共有N个节点和E条边，（即，如果点i和j相连，则矩阵元素Ai，j =1，否则Ai，j =0）。如果是无向图，则该矩阵是沿主对角线对称的，也就有Ai，j=Aj，i，这样我们可以只用一半的矩阵元素来描述该网络拓扑结构，此外，我们将Ai，i设置为零，这样邻接矩阵的对角线元素都是0，该文所研究的网络全部为无向图。
渗流模型关注的另外一个关键概念即为点聚，假设有两个结点，如果它们之间至少存在一条路径，从其中一个结点出发，沿着该路径可以到达另外一个结点，则这样两个结点同属于一个点距，而整个网络中拥有最大结点数量的点聚，则是渗流模型关注的重点。
在通常的点渗透模型中，每个点都以概率P被激活，也可以理解为P概率表示该点被保留，以1-P的概率被删除，这代表了一种比较普遍的网络打击现象，例如，对互联网中所有的网站都以相同的概率就行攻击，社交网络中以相同的概率删除结点，等等。对于具体的保留概率P而言，P=0，没有节点处于激活状态，因此整个网络中没有任何的点距。对于P=1，所有结点都是激活的，网络中相当于没有结点被删除。
而Karrer等人[5]提出了信息传播算法则着重考虑了上述激活概率，该方法需要对现实网络中的每一条边列出方程，参见图1。现在我们假设对任何一条边，i->j，来表示该边导向的点聚不属于极大点聚的概率，则依据图1；我们有
（1）
特殊的如果j是叶子结点，则我们有。这样，全图E条边总共有2E个方程。这2E个方程可以通过迭代解出来，如果j不是叶子结点，则的迭代初始值设定为0。
在此基础上我们使用来表述结点j不属于极大点聚的概率，此时我们有
（2）
而对于我们关注任意抽取一点，它经历结点打击之后，属于极大点距的概率即为
（3）
2 模型应用
这里选择两个具体的网络来应用Karrer等人提出的算法，第一网络是一个ER随机图，该包括10000个结点，并且任意结点之间出现一条连接的概率是0.0005，这意味着该网络的每一个结点度平均值大致上是5。第二网络是美国供电网络，该网络拥有4941个结点，该网络的数据直接来源于文献[8]。
从图2和图3的对比分析我们发现在ER随机网络中，信息传播算法关于极大点聚占整网全部结点比例的预期值和实际值高度吻合，而在美国供电网络中，信息传播算法的预期值要高于实际值。因而，可以得信息传播算法的预期计算只有在某些网络中非常准确，而在其他网络中则不那么准确。而该算法到底在哪些网络中预期准确，究竟哪些因素造成了该算法的误差，则成为本文下面研究的重点问题。
图2为随机ER图中信息传播算法预期结果与真实结果的对比。其中，S代表在网络中随机抽取一点，该点在经历结点打击之后属于极大点聚的概率。P代表结点激活或者保留概率。图中的实线代表预期值，而圆圈实线代表真实结果。关于真实结果的计算，我们按照1-P在图中随机删除结点，点数剩余图中的极大子组所含的结点数量占原图所有结点的比例。这种删除和计算被重复进行了100次，得出的均值作为真实值。
图3为美国供电网络中信息传播算法预期结果与真实结果的对比。其中，S代表在网络中随机抽取一点，该点在经历结点打击之后属于极大点聚的概率。P代表结点激活或者保留概率。图中的实线代表预期值，而圆圈实线代表真实结果。关于真实结果的计算，我们按照1-P在图中随机删除结点，点数剩余图中的极大子组所含的结点数量占原图所有结点的比例。这种删除和计算被重复进行了100次，得出的均值作为真实值。
3 模型誤差来源讨论
关于信息传播算法，其算法创造者Karrer等人[5]曾经指出，树型结构的网络或者本地近似树型结构的网络中应用该算法的误差最小，或者更为直白地说，当网络中的环数量非常少的时候，该算法应用的效果更好，至于为什么环会导致算法预测的不精确并没有详尽地说明。
该文在研究信息传播算法极其迭代算法时，首先观察了，当P=1的情况，此时，网络未经任何结点删除，可以认为是原始网络、如果该算法对原始网络极大点聚的估计值存在偏差，这种偏差一定会带到结点删除之后，导致结点删除之后的预期值也不准确。此时，公式（1）变成 （4）
按照該算法的代入规则，即如果j是叶子结点，则我们设定 否则设定其初始值为0，我们发现对于所有不存在环的点聚，我们将迭代得出所有以及所有的，这样该点聚所有点不属于极大点聚概率为1，这也意味着该点聚内所有结点都不属于极大点聚。而对于有环的点聚，我们通过迭代得出来导向叶子结点的其他的而整个子组的这意味着该点聚所有结点都属于极大点聚。
这样的一种设置，使得该模型对于两种类型的网络预测效果不佳，第一张情况是整个网络的极大点聚不存在任何的环，这样真实的极大点聚将被当做非极大点聚来处理，计算的误差此时会非常大。第二种情况就非极大点聚的点聚中许多都含有环，此时，这些非极大点聚都会被当成极大点聚来处理，从而导致预期值计算误差增大。
而讲过对两个具体网络拓扑结构的观察我们发现，在随机ER图中，非极大点聚中的环非常少，而极大点聚中确实存在着一定数量的环，因而可以解释ER随机网络中，信息传播算法预期值和真实值的接近程度非常高。而在美国供电网络中环的数量比较多，经过结点打击之后，许多环都散步到非极大点聚当中，这就使得概算在p的某些取值之下显得不够准确。
5 结语
最后我们来讨论一下信息传播算法的应用以及该文的一点小小的贡献。信息传播算法的优势在于对于任何现实存在的具体网络，通过将其拓扑结构作为输入，我们可以预测一下在特定结点保存比例之下，经历结点打击会的网络极大点聚规模。因为现实中这种预测可以发生在实际结点打击之前，使我们对未来打击发生之后网络连通性有一定的预估。与此同时，极大点聚本身代表了某个网络中信息传递的最大范围，对其进行估计显然也有一定意义。由于其他一些研究已经证明了对于结点数量庞大的网络，环出现在非极大子组的概率非常小，这一定程度上保证了这种算法预测效果。而本文的一点贡献在于明确分析得出该算法使用环境，并且对预测误差的产生有了较为清晰的剖析，从而提示后续研究在使用这一算法时，应该首先观察网络拓扑结构是否出现该文提出的两种不适宜采用这种方法的情况，从而更加合理地使用这一方法。
参考文献
[1] J. Machta， Phase transition in fractal porous media[J].Phys. Rev. Lett.1991，66，169-172.
[2] T.Odagaki and S.Toyofuku，Properties of percolationclusters in a model granular system in two dimensions.J.Phys.Cond. Mat.1998，10：6447-6452.
[3] L.de Arcangelis， S. Redner， and A. Coniglio，Anomalousvoltage distribution of random resistor networks and anew model for the backbone at the percolation threshold[J].Phys. Rev. B，1985，31：4725-4728.
[4] C.L.Henley，Statics of a self-organized percolationmodel[J].Phys.Rev.Lett.1993，71：2741-2744.
[5] B.Karrer，M.E.J.Newman， and L. Zdeborov_a， Phys.Rev.Lett.2014，113.
[6] K. E. Hamilton and L.P.Pryadko，Phys.Rev.Lett.2014，113：208701.
[7] F.Radicchi，Nature Phys.2015（11）：597.
[8] D.J.Watts and S.H.Strogatz，Collective dynamics of’small-world’networks[J].Nature.1998（393）：440-442.