7,129
个编辑
更改
跳到导航
跳到搜索
第91行：
第91行： − − 第126行：
第124行： + 第131行：
第130行： + 第136行：
第136行： + 第142行：
第143行： − ===接近中心度=== + 第154行：
第155行： − − + + − 第179行：
第179行： + + + − 在图论中，特征向量中心性 eigenvector centrality是测量节点对网络影响的一种方式。针对连接数相同的节点，相邻节点分数更高的节点会比相邻节点分数更低的节点分数高，依据此原则给所有节点分配对应的分数。特征向量得分较高意味着该节点与许多自身得分较高的节点相连接。<ref>{{Cite journal|title=The mathematics of networks|url=http://www-personal.umich.edu/~mejn/papers/palgrave.pdf|last=M. E. J. Newman|accessdate=2006-11-09|format=PDF}}</ref><ref>{{Cite journal|title=Eigenvector centrality for characterization of protein allosteric pathways|url=https://www.pnas.org/content/115/52/E12201|last=Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista.|journal=Proceedings of the National Academy of Sciences|doi=10.1073/pnas.1810452115|year=2018|volume=115|pages=E12201--E12208}} − </ref> − 谷歌的PageRank和Katz中心性是特征向量中心性的变形。<ref name="ams">{{Cite web|url=http://www.ams.org/samplings/feature-column/fcarc-pagerank|title=How Google Finds Your Needle in the Web's Haystack|author=David Austin|publisher=AMS}}</ref> 第191行：
第191行： + 第196行：
第197行： + + + − Katz 中心性<ref>Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.</ref>是广义的度中心性。度中心性测量紧邻的数量，Katz 中心性测量可以被路径连接的节点数量，同时连接距离远的节点的影响减弱。数学上，它的定义为，+ − :<math>x_i = \sum_{k=1}^{\inf}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math>+ − − Katz 中心性可以看作是特征向量中心性的变形 。 Katz 中心性的另外一种形式是 − 对比特征向量中心性<math>x_{j}</math>被<math>{ x_{j}+1}</math>替代 − 由下文信息可证明<ref>{{cite journal | last1 = Bonacich | first1 = P | year = 1991 | title = Simultaneous group and individual centralities | url = | journal = Social Networks | volume = 13 | issue = 2| pages = 155–168 | doi=10.1016/0378-8733(91)90018-o}}</ref>，当<math>\alpha</math>接近<math>{\displaystyle {\tfrac {1}{\lambda }}}</math>时，主特征向量（邻接矩阵A最大的特征值）是Katz 中心性的极限+ + − + − − − 其中 + − :<math>{\displaystyle L(j)=\sum _{i}a_{ji}}</math> + − − 第240行：
第238行： +
→重要局限
==重要局限==
==重要局限==
中心指数有两个重要的局限性，一个是明显的，另一个是隐含的。 明显的局限性是，一种应用而言的最佳中心性通常对于另一应用不是最佳的。 确实，如果不是这样，我们将不需要那么多不同的中心。 Krackhardt风筝图提供了这种现象的说明，针对该现象，三个不同的中心性概念给出了最中心顶点的三个不同选择。
中心指数有两个重要的局限性，一个是明显的，另一个是隐含的。 明显的局限性是，一种应用而言的最佳中心性通常对于另一应用不是最佳的。 确实，如果不是这样，我们将不需要那么多不同的中心。 Krackhardt风筝图提供了这种现象的说明，针对该现象，三个不同的中心性概念给出了最中心顶点的三个不同选择。
:<math>H= \sum^{|Y|}_{j=1} [C_D(y*)-C_D(y_j)]</math>
:<math>H= \sum^{|Y|}_{j=1} [C_D(y*)-C_D(y_j)]</math>
对应的，图<math>G</math>的度中心如下:
对应的，图<math>G</math>的度中心如下:
:<math>{\displaystyle C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v{^*})-C_D(v_i)]}{H}}</math>
:<math>{\displaystyle C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v{^*})-C_D(v_i)]}{H}}</math>
当图<math>X</math>包含一个与其他节点都相连的中心点 (星图)时 <math>H</math>的值最大, 此时
当图<math>X</math>包含一个与其他节点都相连的中心点 (星图)时 <math>H</math>的值最大, 此时
:<math>H=(n-1)\cdot((n-1)-1)=n^2-3n+2.</math>
:<math>H=(n-1)\cdot((n-1)-1)=n^2-3n+2.</math>
所以对于任意图 :<math>{\displaystyle G:=(V,E)}</math>,
所以对于任意图 :<math>{\displaystyle G:=(V,E)}</math>,
:<math>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2}</math>
:<math>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2}</math>
===接近中心度===
在一个连接图中，节点的归一化的接近中心性（或者接近）是节点与其他图中节点之间的最短路径的平均长度。因此，一个可能成为中心的节点与其他的节点连接更近。
在一个连接图中，节点的归一化的接近中心性（或者接近）是节点与其他图中节点之间的最短路径的平均长度。因此，一个可能成为中心的节点与其他的节点连接更近。
接近被Alex Bavelas (1950) 定义为距离远的程度的倒数，<ref>Alex Bavelas. Communication patterns in task-oriented groups. ''J. Acoust. Soc. Am'', '''22'''(6):725–730, 1950.</ref><ref>{{cite journal|year=1966|title=The centrality index of a graph|url=|journal=Psychometrika|volume=31|issue=4|pages=581–603|doi=10.1007/bf02289527|pmid=5232444|last1=Sabidussi|first1=G}}</ref>即:
接近被Alex Bavelas (1950) 定义为距离远的程度的倒数，<ref>Alex Bavelas. Communication patterns in task-oriented groups. ''J. Acoust. Soc. Am'', '''22'''(6):725–730, 1950.</ref><ref>{{cite journal|year=1966|title=The centrality index of a graph|url=|journal=Psychometrika|volume=31|issue=4|pages=581–603|doi=10.1007/bf02289527|pmid=5232444|last1=Sabidussi|first1=G}}</ref>即:
====和谐中心度====
====和谐中心度====
在一个图中（不一定是连接图），和谐中心度定义为接近中心度倒数和求和运算的拟运算
在一个图中（不一定是连接图），和谐中心度定义为接近中心度倒数和求和运算的拟运算
:<math>{\displaystyle H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}}</math>
:<math>{\displaystyle H(x)=\sum _{y\neq x}{\frac {1}{d(y,x)}}}</math>
其中<math>{\displaystyle 1/d(y,x)=0}</math>如果没有路径从y到x。和谐中心度可以通过除以N-1归一化，其中N是图中的节点数。
其中<math>{\displaystyle 1/d(y,x)=0}</math>如果没有路径从y到x。和谐中心度可以通过除以N-1归一化，其中N是图中的节点数。
和谐中心度是Marchiori 和 Latora (2000)<ref name="marchiorilatora2000">{{citation| journal = Physica A: Statistical Mechanics and its Applications | last1 = Marchiori | first1 = Massimo | last2 = Latora | first2 = Vito | year = 2000 | volume = 285 | issue = 3–4 | pages = 539–546 | title = Harmony in the small-world | doi=10.1016/s0378-4371(00)00311-3| arxiv = cond-mat/0008357 | bibcode = 2000PhyA..285..539M }}</ref>提出的，随后 Dekker (2005)取名为“价值中心度 valued centrality"<ref>{{cite journal|first1=Anthony|last1=Dekker|title=Conceptual Distance in Social Network Analysis|journal=Journal of Social Structure|volume=6|issue=3|year=2005|url=http://www.cmu.edu/joss/content/articles/volume6/dekker/index.html}}</ref>， Rochat (2009)也提出过类似的概念.<ref>{{cite conference | author = Yannick Rochat | title = Closeness centrality extended to unconnected graphs: The harmonic centrality index | conference = Applications of Social Network Analysis, ASNA 2009 | url = http://infoscience.epfl.ch/record/200525/files/%5bEN%5dASNA09.pdf }}</ref>
和谐中心度是Marchiori 和 Latora (2000)<ref name="marchiorilatora2000">{{citation| journal = Physica A: Statistical Mechanics and its Applications | last1 = Marchiori | first1 = Massimo | last2 = Latora | first2 = Vito | year = 2000 | volume = 285 | issue = 3–4 | pages = 539–546 | title = Harmony in the small-world | doi=10.1016/s0378-4371(00)00311-3| arxiv = cond-mat/0008357 | bibcode = 2000PhyA..285..539M }}</ref>提出的，随后 Dekker (2005)取名为“价值中心度 valued centrality"<ref>{{cite journal|first1=Anthony|last1=Dekker|title=Conceptual Distance in Social Network Analysis|journal=Journal of Social Structure|volume=6|issue=3|year=2005|url=http://www.cmu.edu/joss/content/articles/volume6/dekker/index.html}}</ref>， Rochat (2009)也提出过类似的概念.<ref>{{cite conference | author = Yannick Rochat | title = Closeness centrality extended to unconnected graphs: The harmonic centrality index | conference = Applications of Social Network Analysis, ASNA 2009 | url = http://infoscience.epfl.ch/record/200525/files/%5bEN%5dASNA09.pdf }}</ref>
===介数中心性===
===介数中心性===
[[File:Color.png|400px|thumb|right|色相（从红色= 0到蓝色=最大）显示节点之间的间隔。]]
[[File:Color.png|400px|thumb|right|色相（从红色= 0到蓝色=最大）显示节点之间的间隔。]]
在图论中，介数中心性 Betweenness Centrality是基于最短路径针对网络图中心性的衡量标准之一。针对全连接网络图，其中任意两个节点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个节点的介数中心性即为这些最短路径穿过该节点的次数。
在图论中，介数中心性 Betweenness Centrality是基于最短路径针对网络图中心性的衡量标准之一。针对全连接网络图，其中任意两个节点均至少存在一个最短路径，在无权重网络图中该最短路径是路径包含边的数量求和，加权网络图中该最短路径则是路径包含边的权重求和。每个节点的介数中心性即为这些最短路径穿过该节点的次数。
<math>{\displaystyle (N-1)(N-2)}</math> ，而无向图需除以<math>{\displaystyle (N-1)(N-2)/2}</math>，其中 N是网络图中节点数量的集合。该比例代表的是最高可能计算值，即某节点与其他所有节点都通过单一的最短路径相连接，不过以上情况通常不会发生。标准化的过程并不会使计算的精准度受到影响。<math> {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}</math>可求解得：<math>{\displaystyle \max(normal)=1}</math>，<math>{\displaystyle \min(normal)=0}</math>
<math>{\displaystyle (N-1)(N-2)}</math> ，而无向图需除以<math>{\displaystyle (N-1)(N-2)/2}</math>，其中 N是网络图中节点数量的集合。该比例代表的是最高可能计算值，即某节点与其他所有节点都通过单一的最短路径相连接，不过以上情况通常不会发生。标准化的过程并不会使计算的精准度受到影响。<math> {\mbox{normal}}(g(v))={\frac {g(v)-\min(g)}{\max(g)-\min(g)}}</math>可求解得：<math>{\displaystyle \max(normal)=1}</math>，<math>{\displaystyle \min(normal)=0}</math>
,由公式可知，计算结果将始终是一个从较小范围到更大范围的比例，因此没有精准度的损失。
,由公式可知，计算结果将始终是一个从较小范围到更大范围的比例，因此没有精准度的损失。
===特征向量中心性===
===特征向量中心性===
在图论中，特征向量中心性 eigenvector centrality是测量节点对网络影响的一种方式。针对连接数相同的节点，相邻节点分数更高的节点会比相邻节点分数更低的节点分数高，依据此原则给所有节点分配对应的分数。特征向量得分较高意味着该节点与许多自身得分较高的节点相连接。<ref>{{Cite journal|title=The mathematics of networks|url=http://www-personal.umich.edu/~mejn/papers/palgrave.pdf|last=M. E. J. Newman|accessdate=2006-11-09|format=PDF}}</ref><ref>{{Cite journal|title=Eigenvector centrality for characterization of protein allosteric pathways|url=https://www.pnas.org/content/115/52/E12201|last=Christian F. A. Negre, Uriel N. Morzan, Heidi P. Hendrickson, Rhitankar Pal, George P. Lisi, J. Patrick Loria, Ivan Rivalta, Junming Ho, Victor S. Batista.|journal=Proceedings of the National Academy of Sciences|doi=10.1073/pnas.1810452115|year=2018|volume=115|pages=E12201--E12208}}
</ref>谷歌的PageRank和Katz中心性是特征向量中心性的变形。<ref name="ams">{{Cite web|url=http://www.ams.org/samplings/feature-column/fcarc-pagerank|title=How Google Finds Your Needle in the Web's Haystack|author=David Austin|publisher=AMS}}</ref>
==== 利用邻接矩阵求特征向量中心性 ====
==== 利用邻接矩阵求特征向量中心性 ====
给定一个节点集合为<math>|V|</math>的图<math>G=(V,E)</math>，定义其邻接矩阵:<math>A = (a_{v,t})</math>，当<math>v</math>与<math>t</math>相连时<math>a_{v,t} = 1</math>，否则<math>a_{v,t} = 0</math>。则节点<math>v</math>中心性:<math>x</math>的分数其求解公式为：
给定一个节点集合为<math>|V|</math>的图<math>G=(V,E)</math>，定义其邻接矩阵:<math>A = (a_{v,t})</math>，当<math>v</math>与<math>t</math>相连时<math>a_{v,t} = 1</math>，否则<math>a_{v,t} = 0</math>。则节点<math>v</math>中心性:<math>x</math>的分数其求解公式为：
:<math>x_v = \frac {1}{ \lambda} \sum_{t \in M(v)} x_t = \frac {1}{ \lambda} \sum_{t \in G} a_{v,t} x_t </math>
:<math>x_v = \frac {1}{ \lambda} \sum_{t \in M(v)} x_t = \frac {1}{ \lambda} \sum_{t \in G} a_{v,t} x_t </math>
其中:<math>M(v)</math>是节点<math>v</math>的相邻节点集合，<math>\lambda</math>是一个常数。经过一系列变形，该公式可变换为如下所示的特征向量方程：
其中:<math>M(v)</math>是节点<math>v</math>的相邻节点集合，<math>\lambda</math>是一个常数。经过一系列变形，该公式可变换为如下所示的特征向量方程：
:<math>\mathbf{Ax} = \lambda \mathbf{x}</math>
:<math>\mathbf{Ax} = \lambda \mathbf{x}</math>
通常来说，有许多不同的特征值:<math>\lambda</math>能使得一个特征方程有非零解存在。然而，考虑到特征向量中的所有项均为非负值，根据[[佩伦-弗罗贝尼乌斯定理]]，只有特征值最大时才能测量出想要的中心性。然后通过计算网络中的节点<math>v</math> 其特征向量的相关分量<math>v^\text{th}</math>便能得出其对应的中心性的分数。特征向量的定义只有一个公因子，因此各节点中心性的比例可以很好确定。为了确定一个绝对分数，必须将其中一个特征值标准化，例如所有节点评分之和为1或者节点数 ''n''。幂次迭代是许多特征值算法中的一种，该算法可以用来寻找这种主导特征向量。此外，以上方法可以推广，使得矩阵''A''中每个元素可以是表示连接强度的实数，例如随机矩阵。
通常来说，有许多不同的特征值:<math>\lambda</math>能使得一个特征方程有非零解存在。然而，考虑到特征向量中的所有项均为非负值，根据[[佩伦-弗罗贝尼乌斯定理]]，只有特征值最大时才能测量出想要的中心性。然后通过计算网络中的节点<math>v</math> 其特征向量的相关分量<math>v^\text{th}</math>便能得出其对应的中心性的分数。特征向量的定义只有一个公因子，因此各节点中心性的比例可以很好确定。为了确定一个绝对分数，必须将其中一个特征值标准化，例如所有节点评分之和为1或者节点数 ''n''。幂次迭代是许多特征值算法中的一种，该算法可以用来寻找这种主导特征向量。此外，以上方法可以推广，使得矩阵''A''中每个元素可以是表示连接强度的实数，例如随机矩阵。
===Katz中心性===
===Katz中心性===
Katz 中心性<ref>Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.</ref>是广义的度中心性。度中心性测量紧邻的数量，Katz 中心性测量可以被路径连接的节点数量，同时连接距离远的节点的影响减弱。数学上，它的定义为，
:<math>x_i = \sum_{k=1}^{\inf}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math>
其中<math>\alpha</math>是（0,1）之间的衰减因子。Katz 中心性可以看作是特征向量中心性的变形。Katz 中心性的另外一种形式是
其中<math>\alpha</math>是（0,1）之间的衰减因子。
:<math>{ x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j} +1)}</math>。
:<math>{ x_{i}=\alpha \sum _{j=1}^{N}a_{ij}(x_{j} +1)}</math>。
对比特征向量中心性<math>x_{j}</math>被<math>{ x_{j}+1}</math>替代。由下文信息可证明<ref>{{cite journal | last1 = Bonacich | first1 = P | year = 1991 | title = Simultaneous group and individual centralities | url = | journal = Social Networks | volume = 13 | issue = 2| pages = 155–168 | doi=10.1016/0378-8733(91)90018-o}}</ref>，当<math>\alpha</math>接近<math>{\displaystyle {\tfrac {1}{\lambda }}}</math>时，主特征向量（邻接矩阵A最大的特征值）是Katz 中心性的极限
===PageRank中心性===
===PageRank中心性===
PageRank 满足下面的公式：
PageRank 满足下面的公式
:<math>{\displaystyle x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},}</math>
:<math>{\displaystyle x_{i}=\alpha \sum _{j}a_{ji}{\frac {x_{j}}{L(j)}}+{\frac {1-\alpha }{N}},}</math>
其中，<math>{\displaystyle L(j)=\sum _{i}a_{ji}}</math>
<math>{j}</math>是与节点相邻节点的数目(或者有向图中向外链接的数量)。相比于特征向量中心性和Katz 中心性，一个主要的不同之处是标度因子<math>{L(j)}</math>。另一个不同是PageRank和特征向量中心性是， PageRank向量是特征向量的左边 (注意<math>a_{ji}</math>下标可以轮换)。<ref>[http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf How does Google rank webpages?] January 31, 2012, at the Wayback Machine 20Q: About Networked Life</ref>
<math>{j}</math>是与节点相邻节点的数目(或者有向图中向外链接的数量)。相比于特征向量中心性和Katz 中心性，一个主要的不同之处是标度因子<math>{L(j)}</math>。另一个不同是PageRank和特征向量中心性是， PageRank向量是特征向量的左边 (注意<math>a_{ji}</math>下标可以轮换)。<ref>[http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf How does Google rank webpages?] January 31, 2012, at the Wayback Machine 20Q: About Networked Life</ref>
===渗流中心性===
===渗流中心性===
渗流中心性是加权介数中心性的一种特殊情况，它在计算其权重时考虑了每条最短路径的源节点与目标节点的“状态”。 在复杂网络中，许多情景都会发生“感染”并进行渗流。 例如，众所周知，在接触网络中细菌或病毒的感染可以在人群的[[社会网络]]中传播。也可以将疾病的传播抽象化，认为一个城镇或人群聚集地是由公路、铁路或航空的连接而构成的网络。计算机病毒可能通过[[计算机网络]]传播。关于商业报价和交易的传闻或新闻也可以经由人群的社交网络传播。 在所有这些情景下，一个“感染”可在复杂网络中通过连接传播，并伴随着节点“状态”的改变，如受到感染或感染后恢复到原状态。例如，在一个流行病的情景下，个体在感染传播时会将状态由“易感染”变为“已感染”。 在上述例子中，各个节点在传播时可能的状态可以是二元的（已受到/未受到感染）、离散的（易感染/已感染/已恢复）乃至连续的（如城镇中受感染者的比例）。 在所有这些情景中，常见的特征是传染病的传播使网络中节点状态发生变化。 以上这些有关渗流中心性(PC)的概念由Piraveenan et al.等人提出，这对具体地测量节点在网络渗透中的重要性很有帮助。<ref name="piraveenan2013">{{Cite journal|title=Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks|last=Piraveenan|first=Mahendra|journal=PLOS ONE|issue=1|doi=10.1371/journal.pone.0053095|year=2013|volume=8|pages=e53095|bibcode=2013PLoSO...853095P|pmc=3551907|pmid=23349699}}</ref>
渗流中心性是加权介数中心性的一种特殊情况，它在计算其权重时考虑了每条最短路径的源节点与目标节点的“状态”。 在复杂网络中，许多情景都会发生“感染”并进行渗流。 例如，众所周知，在接触网络中细菌或病毒的感染可以在人群的[[社会网络]]中传播。也可以将疾病的传播抽象化，认为一个城镇或人群聚集地是由公路、铁路或航空的连接而构成的网络。计算机病毒可能通过[[计算机网络]]传播。关于商业报价和交易的传闻或新闻也可以经由人群的社交网络传播。 在所有这些情景下，一个“感染”可在复杂网络中通过连接传播，并伴随着节点“状态”的改变，如受到感染或感染后恢复到原状态。例如，在一个流行病的情景下，个体在感染传播时会将状态由“易感染”变为“已感染”。 在上述例子中，各个节点在传播时可能的状态可以是二元的（已受到/未受到感染）、离散的（易感染/已感染/已恢复）乃至连续的（如城镇中受感染者的比例）。 在所有这些情景中，常见的特征是传染病的传播使网络中节点状态发生变化。 以上这些有关渗流中心性(PC)的概念由Piraveenan et al.等人提出，这对具体地测量节点在网络渗透中的重要性很有帮助。<ref name="piraveenan2013">{{Cite journal|title=Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks|last=Piraveenan|first=Mahendra|journal=PLOS ONE|issue=1|doi=10.1371/journal.pone.0053095|year=2013|volume=8|pages=e53095|bibcode=2013PLoSO...853095P|pmc=3551907|pmid=23349699}}</ref>
:<math>PC^t(v)= \frac{1}{N-2}\sum_{s \neq v \neq r}\frac{\sigma_{sr}(v)}{\sigma_{sr}}\frac{{x^t}_s}{{\sum {[{x^t}_i}]}-{x^t}_v}</math>
:<math>PC^t(v)= \frac{1}{N-2}\sum_{s \neq v \neq r}\frac{\sigma_{sr}(v)}{\sigma_{sr}}\frac{{x^t}_s}{{\sum {[{x^t}_i}]}-{x^t}_v}</math>
其中，<math>\sigma_{sr}</math> 是从节点<math>s</math>到节点 <math>r</math>最短路径数之和，<math>\sigma_{sr}(v)</math>这些路径中通过 <math>v</math>的次数。 节点<math>i</math>在时间 :<math>t</math>的渗流状态由<math>{x^t}_i</math>决定，其中有两个临界值，<math>{x^t}_i=0</math>时表示在时间<math>t</math>的时候没有渗透状态，<math>{x^t}_i=1</math>时表示在时间 <math>t</math>的时候为完全渗流状态。0到1之间的值则表示部分渗透状态（例如，在一个城镇网络中，这表示城镇受感染人群的百分比）。
其中，<math>\sigma_{sr}</math> 是从节点<math>s</math>到节点 <math>r</math>最短路径数之和，<math>\sigma_{sr}(v)</math>这些路径中通过 <math>v</math>的次数。 节点<math>i</math>在时间 :<math>t</math>的渗流状态由<math>{x^t}_i</math>决定，其中有两个临界值，<math>{x^t}_i=0</math>时表示在时间<math>t</math>的时候没有渗透状态，<math>{x^t}_i=1</math>时表示在时间 <math>t</math>的时候为完全渗流状态。0到1之间的值则表示部分渗透状态（例如，在一个城镇网络中，这表示城镇受感染人群的百分比）。