网络中心性 - 版本历史

薄荷：/* 渗滤中心性 Percolation centrality（PC） */

2022-02-26T13:25:43Z

渗滤中心性 Percolation centrality（PC）

薄荷：/* 使用邻接矩阵发现特征向量中心性 Eigenvector centrality */

2022-02-26T13:25:03Z

使用邻接矩阵发现特征向量中心性 Eigenvector centrality

薄荷：/* 中介中心性 Betweenness centrality */

2022-02-26T13:24:05Z

中介中心性 Betweenness centrality

薄荷：/* 渗滤中心性 Percolation centrality（PC） */

2022-02-26T13:23:45Z

渗滤中心性 Percolation centrality（PC）

薄荷：/* 扩展 */

2021-08-01T05:53:13Z

扩展

薄荷：/* 中介中心性 Betweenness centrality */

2021-08-01T05:52:29Z

中介中心性 Betweenness centrality

薄荷：/* 特征向量中心性 Eigenvector centrality' */

2021-08-01T05:44:59Z

特征向量中心性 Eigenvector centrality'

薄荷：/* 行走结构特征 */

2021-08-01T05:44:10Z

行走结构特征

2021年8月1日 (日) 05:42 薄荷

2021-08-01T05:42:52Z

2021年8月1日 (日) 05:41 薄荷

2021-08-01T05:41:46Z

显示更改

←上一版本		2022年2月26日 (六) 13:25的版本
第264行：		第264行：
	==渗滤中心性 Percolation centrality（PC）==		==渗滤中心性 Percolation centrality（PC）==

−	在复杂网络中，存在大量的中心性度量来确定单个节点的“重要性”。然而，这些度量单纯从拓扑学的角度来量化节点的重要性，节点的值并不以任何方式依赖于节点的状态。不管网络动态如何，它都保持不变。即使对于加权的两者之间的度量也是如此。然而，一个节点可能很好地位于中介中心性或其他中心性度量的中心位置，但可能不是位于有渗滤的网络的上下文中的中心位置。在许多情况下，复杂网络中都会出现“传染”的渗滤现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，随着传染的扩散，每个节点可以采取的状态可以是二进制的（例如接收/没有接收到一条新闻）、离散的（易感/受感染/康复），甚至是连续的（例如一个城镇中受感染的人的比例）。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。'''渗滤中心性 Percolation centrality''就是基于这个思想而提出的，它特别地度量了节点在协助网络渗滤方面的重要性。这种度量是由皮拉维南 piraveanan等人提出的。<ref name="piraveenan2013">{{cite journal \|last1 = Piraveenan \|first1 = M. \|last2 = Prokopenko \|first2 = M.\|last3 = Hossain\|first3 = L. \|year=2013\| title = Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks \| journal = PLOS One \| volume=8 \| issue=1 \| doi=10.1371/journal.pone.0053095 \| pages=e53095 \| pmid=23349699 \| pmc=3551907\| bibcode=2013PLoSO...853095P }}</ref>	+	在复杂网络中，存在大量的中心性度量来确定单个节点的“重要性”。然而，这些度量单纯从拓扑学的角度来量化节点的重要性，节点的值并不以任何方式依赖于节点的状态。不管网络动态如何，它都保持不变。即使对于加权的两者之间的度量也是如此。然而，一个节点可能很好地位于中介中心性或其他中心性度量的中心位置，但可能不是位于有渗滤的网络的上下文中的中心位置。在许多情况下，复杂网络中都会出现“传染”的渗滤现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，随着传染的扩散，每个节点可以采取的状态可以是二进制的（例如接收/没有接收到一条新闻）、离散的（易感/受感染/康复），甚至是连续的（例如一个城镇中受感染的人的比例）。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。'''渗滤中心性 Percolation centrality'''就是基于这个思想而提出的，它特别地度量了节点在协助网络渗滤方面的重要性。这种度量是由皮拉维南 piraveanan等人提出的。<ref name="piraveenan2013">{{cite journal \|last1 = Piraveenan \|first1 = M. \|last2 = Prokopenko \|first2 = M.\|last3 = Hossain\|first3 = L. \|year=2013\| title = Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks \| journal = PLOS One \| volume=8 \| issue=1 \| doi=10.1371/journal.pone.0053095 \| pages=e53095 \| pmid=23349699 \| pmc=3551907\| bibcode=2013PLoSO...853095P }}</ref>

←上一版本		2022年2月26日 (六) 13:25的版本
第222行：		第222行：


−	一般情况下，存在许多不同的特征值<math>\lambda</math>，对于这些特征值存在一个非零特征向量解。由于邻接矩阵中的项是非负的，所以由佩龙-弗罗贝尼乌斯 Perron- Frobenius定理得出，它有一个唯一的正实数最大特征值。由这个最大的特征值得出期望的中心性度量。<ref>{{cite journal \| author = M. E. J. Newman \| title = The mathematics of networks \| url = http://www-personal.umich.edu/~mejn/papers/palgrave.pdf \| accessdate = 2006-11-09}}</ref>相关特征向量的~~</ref> The~~ <math>v^{th}</math>分量给出了网络中顶点<math>v</math>的相对中心性评分。特征向量只定义了一个公共因子，所以只有顶点中心性的比例是明确定义的。要定义一个绝对分数，必须对特征向量进行标准化，例如，使所有顶点的和为1或顶点的总数n。幂迭代是许多特征值算法之一，可以用来找到这个主要特征向量。<ref name="ams" />此外，这推广，使得 A中的项可以是表示连接强度的实数，就像在[[随机矩阵]]中一样。	+	一般情况下，存在许多不同的特征值<math>\lambda</math>，对于这些特征值存在一个非零特征向量解。由于邻接矩阵中的项是非负的，所以由佩龙-弗罗贝尼乌斯 Perron- Frobenius定理得出，它有一个唯一的正实数最大特征值。由这个最大的特征值得出期望的中心性度量。<ref>{{cite journal \| author = M. E. J. Newman \| title = The mathematics of networks \| url = http://www-personal.umich.edu/~mejn/papers/palgrave.pdf \| accessdate = 2006-11-09}}</ref>相关特征向量的<math>v^{th}</math>分量给出了网络中顶点<math>v</math>的相对中心性评分。特征向量只定义了一个公共因子，所以只有顶点中心性的比例是明确定义的。要定义一个绝对分数，必须对特征向量进行标准化，例如，使所有顶点的和为1或顶点的总数n。幂迭代是许多特征值算法之一，可以用来找到这个主要特征向量。<ref name="ams" />此外，这推广，使得 A中的项可以是表示连接强度的实数，就像在[[随机矩阵]]中一样。
−

	==卡兹中心性 Katz centrality==		==卡兹中心性 Katz centrality==

@@ 第184行： / 第184行： @@
 #对于每一对顶点(''s'',''t'')，计算它们之间的最短路径。
 #对于每对顶点(''s'',''t'') ，确定通过该顶点（这里是顶点 ''v''）的最短路径的分数。
 #对所有顶点对(''s'',''t'')求这个分数的和。

@@ 第276行： / 第276行： @@
-其中<math>\sigma_{sr}</math>是从节点<math>s</math>到节点<math>r</math>的最短路径的总数，<math>\sigma_{sr}(v)</math>是通过<math>v</math>的路径的总数。在时间 < math > t </math > 时，节点< math > i</math >的渗滤状态用<math>{x^t}_i</math>表示，两个特殊情况是当<math>{x^t}_i=0</math>表示在时间上是非渗滤状态，而当<math>{x^t}_i=1</math>表示在时间上是完全渗滤状态。两者之间的值表示部分渗滤状态（例如，在一个城镇网络中，这是该城镇感染者的百分比）。
+其中<math>\sigma_{sr}</math>是从节点<math>s</math>到节点<math>r</math>的最短路径的总数，<math>\sigma_{sr}(v)</math>是通过<math>v</math>的路径的总数。在时间 <math> t </math> 时，节点<math> i</math>的渗滤状态用<math>{x^t}_i</math>表示，两个特殊情况是当<math>{x^t}_i=0</math>表示在时间上是非渗滤状态，而当<math>{x^t}_i=1</math>表示在时间上是完全渗滤状态。两者之间的值表示部分渗滤状态（例如，在一个城镇网络中，这是该城镇感染者的百分比）。
 渗流路径的权重取决于分配给源节点的渗滤水平，前提是源节点的渗滤水平越高，源节点的路径就越重要。因此，位于源自高渗滤节点的最短路径上的节点可能对渗滤更为重要。PC 的定义也可以扩展到包括目标节点的权重。渗滤中心性计算运行在<math>O(NM)</math>时间，高效的实现采用了布兰德斯快速算法，如果计算需要考虑目标节点的权重，最坏情况下时间为<math>O(N^3)</math>。
 ==跨团中心性 Cross-clique centrality==

←上一版本		2021年8月1日 (日) 05:53的版本
第338行：		第338行：


−	中心性的概念也扩展到了群体层次。例如，组间的中介中心性显示了连接穿过组的成对非组成员的测地线的比例。<ref name="group1">Everett, M. G. and Borgatti, S. P. (2005). Extending centrality. In P. J. Carrington, J. Scott and S. Wasserman (Eds.), ''Models and methods in social network analysis'' (pp. 57–76). New York: Cambridge University Press.</ref><ref name="group2">Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009).[http://necsi.edu/affiliates/braha/Internet_Research_Anonimity.pdf Collaborative attack on Internet users’ anonymity] ~~{{Webarchive\|url=https://web.archive.org/web/20131207133417/http://necsi.edu/affiliates/braha/Internet_Research_Anonimity.pdf \|date=2013-12-07 }}~~, ''Internet Research'' '''19'''(1)</ref>	+	中心性的概念也扩展到了群体层次。例如，组间的中介中心性显示了连接穿过组的成对非组成员的测地线的比例。<ref name="group1">Everett, M. G. and Borgatti, S. P. (2005). Extending centrality. In P. J. Carrington, J. Scott and S. Wasserman (Eds.), ''Models and methods in social network analysis'' (pp. 57–76). New York: Cambridge University Press.</ref><ref name="group2">Puzis, R., Yagil, D., Elovici, Y., Braha, D. (2009).[http://necsi.edu/affiliates/braha/Internet_Research_Anonimity.pdf Collaborative attack on Internet users’ anonymity], ''Internet Research'' '''19'''(1)</ref>

		+	<br>

	==另见==		==另见==

@@ 第176行： / 第176行： @@
 ==中介中心性 Betweenness centrality==
-[[File:Graph betweenness.svg|240px|right|thumb|色调（从红色 = 0到蓝色 = max）表示节点中介性]]
+[[File:Graph_betweenness.svg.png|240px|right|thumb|色调（从红色 = 0到蓝色 = max）表示节点中介性]]
 中介性是图中顶点的中心性度量（也有边中介性，这里没有讨论）。中介中心性量化了一个节点沿着其他两个节点之间的最短路径充当桥梁的次数。在Linton Freeman<ref name="freeman1977">{{cite journal |last1 = Freeman |first1 = Linton | year=1977| title = A set of measures of centrality based upon betweenness | journal = Sociometry| volume=40|issue = 1 | pages=35–41 | doi=10.2307/3033543|jstor = 3033543 }}</ref>的概念中，它是作为一种量化一个人对社交网络中其他人之间交流控制的度量被引入的，在两个随机选择的顶点之间随机选择的最短路径上出现概率高的顶点具有很高的中介性。
@@ 第202行： / 第202行： @@
 从计算的角度来看，图中所有顶点的中介中心性和紧密中心性都涉及到计算图中所有顶点对之间的最短路径，采用<math>O(V^3)</math>时间和 弗洛伊德-沃肖尔 Floyd-Warshall算法。然而，对于稀疏图，约翰逊 Johnson算法的效率可能更高，采用<math>O(V^2 \log V + V E)</math>时间。在不加权图的情况下，可以用布兰德斯 Brandes 的算法进行计算<ref name=brandes/>，该算法需要  <math>O(V E)</math>时间。一般情况下，这些算法假定图是无向的，并且连通图中允许有圈和多条边。当专门处理网络图时，图通常没有环或多条边来维持简单的关系（其中的边表示两个人或顶点之间的联系）。在这种情况下，使用 Brandes 的算法将最终的中心性分数除以2来计算每条被重复计算的最短路径。<ref name="brandes" />
 ==特征向量中心性 Eigenvector centrality==

@@ 第203行： / 第203行： @@
-==特征向量中心性 Eigenvector centrality'==
+==特征向量中心性 Eigenvector centrality==
 特征向量中心性（也称为特征中心性）是对网络中节点影响的一种度量。它将相对得分分配给网络中的所有节点，这是基于这样一个概念: 连接得分高的节点比连接得分低的节点对得分贡献更大。<ref>{{cite journal|title = The mathematics of networks|url = http://www-personal.umich.edu/~mejn/papers/palgrave.pdf|author = M. E. J. Newman|accessdate = 2006-11-09}}</ref><ref name="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. 2018 E12201--E12208"/>谷歌的网页排名和卡兹中心性是特征向量中心性的变体。<ref name="ams">{{Cite web | url=http://www.ams.org/samplings/feature-column/fcarc-pagerank | title=American Mathematical Society}}</ref>
 ==使用[[邻接矩阵]]发现特征向量中心性 Eigenvector centrality==

@@ 第31行： / 第31行： @@
-同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的'''接近中心性 Closeness centrality'''，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。
+同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的接近中心性 Closeness centrality，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。
 Borgatti和Everett提出，这种类型为如何最好地比较中心性度量提供了见解。在这个2×2分类中，放在同一盒子中的中心性足够相似，可以做出合理的选择; 人们可以合理地比较哪个对于给定的应用更好。然而，不同盒子中的度量方法是截然不同的。只有在预先确定哪个类别更适用的情况下，对相对适应性的评估才会发生，这使得比较变得毫无意义。<ref name=Borgatti2006/>
 ===光谱上存在的径向量中心===

←上一版本		2021年8月1日 (日) 05:42的版本
第31行：		第31行：


−	同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的'''~~<font color="#ff8000"> 接近中心性Closeness~~ centrality~~</font>~~'''，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。	+	同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的'''接近中心性 Closeness centrality'''，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。


第79行：		第79行：


−	同样，权限分配的解决方案<ref>{{cite journal \|last=Hu \|first=Xingwei \|first2=Lloyd \|last2=Shapley \|title=On Authority Distributions in Organizations \|journal=Games and Economic Behavior \|volume=45 \|pages=132–170 \|year=2003 \| doi = 10.1016/s0899-8256(03)00130-1 }}</ref>~~</font>'''~~采用 Shapley-Shubik 幂指数，而不是 Shapley 值来衡量参与者之间的双边直接影响。这种分布确实是一种产生特征向量中心性的类型。它用于对 Hu (2020)中的大数据对象进行排序<ref>{{cite journal\|last=Hu\|first=Xingwei\|year=2020\|volume=7\|title=Sorting big data by revealed preference with application to college ranking \|journal=Journal of Big Data\|doi=10.1186/s40537-020-00300-1\|doi-access=free}}</ref>，比如美国大学排名。	+	同样，权限分配的解决方案<ref>{{cite journal \|last=Hu \|first=Xingwei \|first2=Lloyd \|last2=Shapley \|title=On Authority Distributions in Organizations \|journal=Games and Economic Behavior \|volume=45 \|pages=132–170 \|year=2003 \| doi = 10.1016/s0899-8256(03)00130-1 }}</ref>采用 Shapley-Shubik 幂指数，而不是 Shapley 值来衡量参与者之间的双边直接影响。这种分布确实是一种产生特征向量中心性的类型。它用于对 Hu (2020)中的大数据对象进行排序<ref>{{cite journal\|last=Hu\|first=Xingwei\|year=2020\|volume=7\|title=Sorting big data by revealed preference with application to college ranking \|journal=Journal of Big Data\|doi=10.1186/s40537-020-00300-1\|doi-access=free}}</ref>，比如美国大学排名。