更改
跳到导航
跳到搜索
第178行：
第178行： − + + + + + + + + + +
→Percolatio中心
其中<math>{\displaystyle L(j)=\sum _{i}a_{ji}}</math>，j是与节点相邻节点的数目(或者有向图中向外链接的数量)。相比于特征向量中心性和Katz 中心性，一个主要的不同之处是标度因子L(j).。另一个不同是PageRank和特征向量中心性是， PageRank向量是特征向量的左边 (注意<math>a_{ji}</math>下标可以轮换)。<ref>[http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf How does Google rank webpages?] {{webarchive | url= https://web.archive.org/web/20120131083328/http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf |date=January 31, 2012 }} 20Q: About Networked Life</ref>
其中<math>{\displaystyle L(j)=\sum _{i}a_{ji}}</math>，j是与节点相邻节点的数目(或者有向图中向外链接的数量)。相比于特征向量中心性和Katz 中心性，一个主要的不同之处是标度因子L(j).。另一个不同是PageRank和特征向量中心性是， PageRank向量是特征向量的左边 (注意<math>a_{ji}</math>下标可以轮换)。<ref>[http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf How does Google rank webpages?] {{webarchive | url= https://web.archive.org/web/20120131083328/http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf |date=January 31, 2012 }} 20Q: About Networked Life</ref>
===Percolatio中心===
===渗流中心性===
渗流中心性是加权介数中心性的一种特殊情况，它在计算其权重时考虑了每条最短路径的源节点与目标节点的“状态”。 在复杂网络中，许多情景都会发生“感染”并进行渗流。 例如，众所周知，在接触网络中细菌或病毒的感染可以在人群的[[社会网络]]中传播。也可以将疾病的传播抽象化，认为一个城镇或人群聚集地是由公路、铁路或航空的连接而构成的网络。[[计算机病毒]]可能通过[[计算机网络]]传播。关于商业报价和交易的传闻或新闻也可以经由人群的社交网络传播。 在所有这些情景下，一个“感染”可在复杂网络中通过连接传播，并伴随着节点“状态”的改变，如受到感染或感染后恢复到原状态。例如，在一个流行病的情景下，个体在感染传播时会将状态由“易感染”变为“已感染”。 在上述例子中，各个节点在传播时可能的状态可以是二元的（已受到/未受到感染）、离散的（易感染/已感染/已恢复）乃至连续的（如城镇中受感染者的比例）。 在所有这些情景中，常见的特征是传染病的传播使网络中节点状态发生变化。 以上这些有关渗流中心性(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>\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之间的值则表示部分渗透状态（例如，在一个城镇网络中，这表示城镇受感染人群的百分比）。
渗流路径的权重取决于源节点的渗流水平，如果源节点的渗流水平越高，那么来自该节点的路径影响力更大。 因此在源节点为高渗透作用节点的最短路径上的节点更有可能受到渗流影响。渗流中心性的定义还可以扩展到也包括目标节点的权重。 渗流中心性的计算可采用Brandes快速算法有效实现，其[[时间复杂度]]为[[大O符号|<math>O(NM)</math>]]。如果计算需要考虑目标节点的权重，最坏情况的时间复杂度为 [[大O符号|<math>O(N^3)</math>]]。
===Cross-clique中心===
===Cross-clique中心===