更改

Bonacich's family of measures does not transform the adjacency matrix. Alpha centrality replaces the adjacency matrix with its resolvent. Subgraph centrality replaces the adjacency matrix with its trace. A startling conclusion is that regardless of the initial transformation of the adjacency matrix, all such approaches have common limiting behavior. As <math>\beta</math> approaches zero, the indices converge to degree centrality. As <math>\beta</math> approaches its maximal value, the indices converge to eigenvalue centrality.

Bonacich's family of measures does not transform the adjacency matrix. Alpha centrality replaces the adjacency matrix with its resolvent. Subgraph centrality replaces the adjacency matrix with its trace. A startling conclusion is that regardless of the initial transformation of the adjacency matrix, all such approaches have common limiting behavior. As <math>\beta</math> approaches zero, the indices converge to degree centrality. As <math>\beta</math> approaches its maximal value, the indices converge to eigenvalue centrality.

===Game-theoretic centrality===

===Game-theoretic centrality===

For example, consider the problem of stopping an epidemic. Looking at above image of network, which nodes should we vaccinate? Based on previously described measures, we want to recognize nodes that are the most important in disease spreading. Approaches based only on centralities, that focus on individual features of nodes, may not be good idea. Nodes in the red square, individually cannot stop disease spreading, but considering them as a group, we clearly see that they can stop disease if it has started in nodes <math>v_1</math>, <math>v_4</math>, and <math>v_5</math>. Game-theoretic centralities try to consult described problems and opportunities, using tools from game-theory. The approach proposed in  uses the Shapley value. Because of the time-complexity hardness of the Shapley value calculation, most efforts in this domain are driven into implementing new algorithms and methods which rely on a peculiar topology of the network or a special character of the problem. Such an approach may lead to reducing time-complexity from exponential to polynomial.

For example, consider the problem of stopping an epidemic. Looking at above image of network, which nodes should we vaccinate? Based on previously described measures, we want to recognize nodes that are the most important in disease spreading. Approaches based only on centralities, that focus on individual features of nodes, may not be good idea. Nodes in the red square, individually cannot stop disease spreading, but considering them as a group, we clearly see that they can stop disease if it has started in nodes <math>v_1</math>, <math>v_4</math>, and <math>v_5</math>. Game-theoretic centralities try to consult described problems and opportunities, using tools from game-theory. The approach proposed in  uses the Shapley value. Because of the time-complexity hardness of the Shapley value calculation, most efforts in this domain are driven into implementing new algorithms and methods which rely on a peculiar topology of the network or a special character of the problem. Such an approach may lead to reducing time-complexity from exponential to polynomial.

例如，考虑阻止流行病的问题。看看上面的网络图像，我们应该给哪些节点接种疫苗？基于前面描述的措施，我们希望识别在疾病传播中最重要的节点。仅仅基于中心的方法，即关注节点的个别特性，可能不是一个好主意。红色方块中的节点，单独不能阻止疾病的传播，但把它们作为一个群体来考虑，我们清楚地看到，如果疾病在节点 < math > v _ 1 </math > 、 < math > v _ 4 </math > 和 < math > v _ 5 </math > 中开始，它们就能阻止疾病的传播。博弈论中心性试图利用博弈论中的工具来研究所描述的问题和机会。本文提出的方法使用了 Shapley 值。由于 Shapley 值计算的时间复杂性，这一领域的大部分工作都集中在实现新的算法和方法，这些算法和方法依赖于网络的特殊拓扑结构或问题的特殊性质。这种方法可以将时间复杂度从指数降低到多项式。

例如，考虑阻止流行病的问题。看看上面的网络图像，我们应该给哪些节点接种疫苗？基于前面描述的措施，我们希望识别在疾病传播中最重要的节点。仅仅基于中心的方法，即关注节点的个别特性，可能不是一个好主意。红色方块中的节点，单独不能阻止疾病的传播，但把它们作为一个群体来考虑，我们清楚地看到，如果疾病在节点 < math > v _ 1 </math > 、 < math > v _ 4 </math > 和 < math > v _ 5 </math > 中开始，它们就能阻止疾病的传播。博弈论中心性试图利用博弈论中的工具来研究所描述的问题和可能性。本文提出的方法使用了 Shapley 值。由于 Shapley 值计算的时间复杂性，这一领域的大部分工作都集中在实现新的算法和方法，这些算法和方法依赖于网络的特殊拓扑结构或问题的特殊性质。这种方法可以将时间复杂度从指数降低到多项式。

Similarly, the solution concept authority distribution () applies the Shapley-Shubik power index, rather than the Shapley value, to measure the bilateral direct influence between the players. The distribution is indeed a type of engenvector centrality. It is used to sort big data objects in Hu (2020), such as ranking U.S. colleges.

Similarly, the solution concept authority distribution () applies the Shapley-Shubik power index, rather than the Shapley value, to measure the bilateral direct influence between the players. The distribution is indeed a type of engenvector centrality. It is used to sort big data objects in Hu (2020), such as ranking U.S. colleges.

同样，解概念权威分布()采用 Shapley-Shubik 幂指数，而不是 Shapley 值来衡量双方之间的直接影响。分布确实是一种产生向量中心性的类型。它用于对 Hu (2020)中的大数据对象进行排序，比如美国大学排名。

同样，求解  概念权威分布() 采用 Shapley-Shubik 幂指数，而不是 Shapley 值来衡量双方之间的直接影响。这一分布确实是向量中心性的一种类型。它用于对 Hu (2020)中的大数据对象进行排序，比如美国大学排名。

== Important limitations ==

== Important limitations ==

Historically first and conceptually simplest is degree centrality, which is defined as the number of links incident upon a node (i.e., the number of ties that a node has). The degree can be interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (such as a virus, or some information). In the case of a directed network (where ties have direction), we usually define two separate measures of degree centrality, namely indegree and outdegree. Accordingly, indegree is a count of the number of ties directed to the node and outdegree is the number of ties that the node directs to others. When ties are associated to some positive aspects such as friendship or collaboration, indegree is often interpreted as a form of popularity, and outdegree as gregariousness.

Historically first and conceptually simplest is degree centrality, which is defined as the number of links incident upon a node (i.e., the number of ties that a node has). The degree can be interpreted in terms of the immediate risk of a node for catching whatever is flowing through the network (such as a virus, or some information). In the case of a directed network (where ties have direction), we usually define two separate measures of degree centrality, namely indegree and outdegree. Accordingly, indegree is a count of the number of ties directed to the node and outdegree is the number of ties that the node directs to others. When ties are associated to some positive aspects such as friendship or collaboration, indegree is often interpreted as a form of popularity, and outdegree as gregariousness.

历史上最简单的概念是度中心性，它定义为一个节点上发生的链接数量(即一个节点拥有的关系数量)。度可以根据节点捕获流经网络的任何东西(例如病毒或某些信息)的直接风险来解释。在有向网络的情况下(其中联系有方向) ，我们通常定义两个独立的度量度量度量度量度量，即 indegree 和 outdegree。因此，indegree 是指向该节点的关系数，outdegree 是指该节点指向其他节点的关系数。当关系与一些积极的方面如友谊或合作有关时，不受欢迎通常被解释为流行的一种形式，而超过程度则被解释为合群。

历史上最简单的概念是度中心性，它定义为一个节点上发生的链接数量(即一个节点拥有的连接数量)。度可以根据节点捕获流经网络的任何东西(例如病毒或某些信息)的直接风险来解释。在有向网络的情况下(其中连接有方向) ，我们通常定义两个独立的度量，即 入度indegree 和出度 outdegree。因此，入度indegree 是指向该节点的连接数，出度outdegree 是指该节点指向其他节点的连接数。当连接与一些积极的方面如友谊或合作有关时，入度通常被解释为一种形式的受欢迎，而出度则被解释为合群性。

The definition of centrality on the node level can be extended to the whole graph, in which case we are speaking of graph centralization. Let <math>v*</math> be the node with highest degree centrality in <math>G</math>. Let <math>X:=(Y,Z)</math> be the <math>|Y|</math>-node connected graph that maximizes the following quantity (with <math>y*</math> being the node with highest degree centrality in <math>X</math>):

The definition of centrality on the node level can be extended to the whole graph, in which case we are speaking of graph centralization. Let <math>v*</math> be the node with highest degree centrality in <math>G</math>. Let <math>X:=(Y,Z)</math> be the <math>|Y|</math>-node connected graph that maximizes the following quantity (with <math>y*</math> being the node with highest degree centrality in <math>X</math>):

节点级中心性的定义可以扩展到整个图，在这种情况下，我们说的是图的集中性。设 < math > v </math > 为 < math > g </math > 中度中心性最高的节点。让 < math > x: = (y，z) </math > 是 < math > | y | </math > 节点连接图，最大化下列数量(< math > y * </math > 是 < math > 中度最高的节点) :

节点级中心性的定义可以扩展到整个图，在这种情况下，我们说的是图的中心性。设 < math > v </math > 为 < math > g </math > 中度中心性最高的节点。让 < math > x: = (y，z) </math > 是 < math > | y | </math > 节点连接图，最大化下列数量(< math > y * </math > 是 < math > 中度最高的节点) :

Correspondingly, the degree centralization of the graph <math>G</math> is as follows:

Correspondingly, the degree centralization of the graph <math>G</math> is as follows:

相应地，图形 < math > g </math > 的度集中性如下:

相应地，图形 < math > g </math > 的度中心性如下:

==Closeness centrality==

==Closeness centrality==

{{Main|Closeness centrality}}In a [[Connected component (graph theory)|connected]] [[Graph (discrete mathematics)|graph]], the [[Normalization (statistics)|normalized]] '''closeness centrality''' (or '''closeness''') of a node is the average length of the [[Shortest path problem|shortest path]] between the node and all other nodes in the graph. Thus the more central a node is, the closer it is to all other nodes.

{{Main|Closeness centrality}}In a [[Connected component (graph theory)|connected]] [[Graph (discrete mathematics)|graph]], the [[Normalization (statistics)|normalized]] '''closeness centrality''' (or '''closeness''') of a node is the average length of the [[Shortest path problem|shortest path]] between the node and all other nodes in the graph. Thus the more central a node is, the closer it is to all other nodes.

In a connected graph, the normalized closeness centrality (or closeness) of a node is the average length of the shortest path between the node and all other nodes in the graph. Thus the more central a node is, the closer it is to all other nodes.

In a connected graph, the normalized closeness centrality (or closeness) of a node is the average length of the shortest path between the node and all other nodes in the graph. Thus the more central a node is, the closer it is to all other nodes.

在连通图中，节点的归一化贴近中心性(或贴近性)是节点与图中所有其他节点之间最短路径的平均长度。因此，一个节点越是中心，它就越接近所有其他节点。

在连通图中，节点的归一化贴近中心性(或紧密性)是节点与图中所有其他节点之间最短路径的平均长度。因此，一个节点越是中心，它就越接近所有其他节点。

Closeness was defined by Alex Bavelas (1950) as the reciprocal of the farness, that is:

Closeness was defined by Alex Bavelas (1950) as the reciprocal of the farness, that is:

亚历克斯 · 巴维拉斯(1950)将亲密度定义为相对于距离的倒数，即:

亚历克斯 · 巴维拉斯(1950)将紧密度定义为相对于距离的倒数，即:

where <math>d(y,x)</math> is the distance between vertices <math>x</math> and <math>y</math>. However, when speaking of closeness centrality, people usually refer to its normalized form, generally given by the previous formula multiplied by <math>N-1</math>, where <math>N</math> is the number of nodes in the graph. This adjustment allows comparisons between nodes of graphs of different sizes.

where <math>d(y,x)</math> is the distance between vertices <math>x</math> and <math>y</math>. However, when speaking of closeness centrality, people usually refer to its normalized form, generally given by the previous formula multiplied by <math>N-1</math>, where <math>N</math> is the number of nodes in the graph. This adjustment allows comparisons between nodes of graphs of different sizes.

其中 < math > d (y，x) </math > 是顶点 < math > x </math > 和 < math > y </math > 之间的距离。然而，当谈到亲密中心性时，人们通常会提到它的规范化形式，一般是以前的公式乘以 < math > N-1 </math > ，其中 < math > n </math > 是图中的节点数。这种调整允许比较不同大小图形的节点。

其中 < math > d (y，x) </math > 是顶点 < math > x </math > 和 < math > y </math > 之间的距离。然而，当谈到紧密中心性时，人们通常会提到它的规范化形式，一般是以前的公式乘以 < math > N-1 </math > ，其中 < math > n </math > 是图中的节点数。这种调整允许比较不同大小图形的节点。

Taking distances from or to all other nodes is irrelevant in undirected graphs, whereas it can produce totally different results in directed graphs (e.g. a website can have a high closeness centrality from outgoing link, but low closeness centrality from incoming links).

Taking distances from or to all other nodes is irrelevant in undirected graphs, whereas it can produce totally different results in directed graphs (e.g. a website can have a high closeness centrality from outgoing link, but low closeness centrality from incoming links).

从所有其他节点或到所有其他节点的距离在无向图中是不相关的，但是在有向图中可能产生完全不同的结果(例如:一个网站可以从传出链接获得高度的亲密度中心性，而从传入链接获得的亲密度中心性低)。

在无向图中，来自于所有其他节点或去往所有其他节点的距离是不相关的，但是在有向图中可能产生完全不同的结果(例如:一个网站可以从传出链接获得高的紧密度中心性，而从传入链接获得低的紧密度中心性)。

===Harmonic centrality===

===Harmonic centrality===

In a (not necessarily connected) graph, the '''harmonic centrality''' reverses the sum and reciprocal operations in the definition of closeness centrality:

In a (not necessarily connected) graph, the '''harmonic centrality''' reverses the sum and reciprocal operations in the definition of closeness centrality:

In a (not necessarily connected) graph, the harmonic centrality reverses the sum and reciprocal operations in the definition of closeness centrality:

In a (not necessarily connected) graph, the harmonic centrality reverses the sum and reciprocal operations in the definition of closeness centrality:

在一个(不一定是连通的)图中，调和中心性反转了封闭中心性定义中的和互反运算:

在一个(不一定是连通的)图中，调和中心性反转了紧密中心性定义中的和互反运算:

Betweenness is a centrality measure of a vertex within a graph (there is also edge betweenness, which is not discussed here). Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by Linton Freeman In his conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.

Betweenness is a centrality measure of a vertex within a graph (there is also edge betweenness, which is not discussed here). Betweenness centrality quantifies the number of times a node acts as a bridge along the shortest path between two other nodes. It was introduced as a measure for quantifying the control of a human on the communication between other humans in a social network by Linton Freeman In his conception, vertices that have a high probability to occur on a randomly chosen shortest path between two randomly chosen vertices have a high betweenness.

介于性是图中顶点的中心性度量(也有边介于性，这里没有讨论)。中间中心性量化了一个节点沿着其他两个节点之间的最短路径充当桥梁的次数。在林顿 · 弗里曼的概念中，在两个随机选择的顶点之间随机选择的最短路径上出现概率高的顶点具有很高的中间性。

中介性是图中顶点的中心性度量(也有边中介性，这里没有讨论)。中介中心性量化了一个节点沿着其他两个节点之间的最短路径充当桥梁的次数。在林顿 · 弗里曼的概念中，在两个随机选择的顶点之间随机选择的最短路径上出现概率高的顶点具有很高的中介性。

where <math>\sigma_{st}</math> is total number of shortest paths from node <math>s</math> to node <math>t</math> and <math>\sigma_{st}(v)</math> is the number of those paths that pass through <math>v</math>.  The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is <math>(n-1)(n-2)</math> and for undirected graphs is <math>(n-1)(n-2)/2</math>.  For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of <math>(n-1)(n-2)/2</math> (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0.

where <math>\sigma_{st}</math> is total number of shortest paths from node <math>s</math> to node <math>t</math> and <math>\sigma_{st}(v)</math> is the number of those paths that pass through <math>v</math>.  The betweenness may be normalised by dividing through the number of pairs of vertices not including v, which for directed graphs is <math>(n-1)(n-2)</math> and for undirected graphs is <math>(n-1)(n-2)/2</math>.  For example, in an undirected star graph, the center vertex (which is contained in every possible shortest path) would have a betweenness of <math>(n-1)(n-2)/2</math> (1, if normalised) while the leaves (which are contained in no shortest paths) would have a betweenness of 0.

其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math > 和 < math > sigma { st }(v) </math > 是通过 < math > v </math > 的路径数。有向图是 < math > (n-1)(n-2) </math > ，无向图是 < math > (n-1)(n-2)/2 </math > 。例如，在一个无向星图中，中心顶点(包含在每个可能的最短路径中)的中间性为 < math > (n-1)(n-2)/2 </math > (1，如果标准化) ，而叶子(包含在没有最短路径中)的中间性为0。

其中 < math > sigma { st } </math > 是从节点 < math > s </math > 到节点 < math > t </math > 和 < math > sigma { st }(v) </math > 是通过 < math > v </math > 的路径数。有向图是 < math > (n-1)(n-2) </math > ，无向图是 < math > (n-1)(n-2)/2 </math > 。例如，在一个无向星图中，中心顶点(包含在每个可能的最短路径中)的中介性为 < math > (n-1)(n-2)/2 </math > (1，如果标准化) ，而叶子(包含在没有最短路径中)的中介性为0。

==Eigenvector centrality==

==Eigenvector centrality==

{{main|Eigenvector centrality}}

{{main|Eigenvector centrality}}

In general, there will be many different eigenvalues <math>\lambda</math> for which a non-zero eigenvector solution exists. Since the entries in the adjacency matrix are non-negative, there is a unique largest eigenvalue, which is real and positive, by the Perron–Frobenius theorem. This greatest eigenvalue results in the desired centrality measure. The <math>v^{th}</math> component of the related eigenvector then gives the relative centrality score of the vertex <math>v</math> in the network. The eigenvector is only defined up to a common factor, so only the ratios of the centralities of the vertices are well defined. To define an absolute score one must normalise the eigenvector, e.g., such that the sum over all vertices is 1 or the total number of vertices n. Power iteration is one of many eigenvalue algorithms that may be used to find this dominant eigenvector. Furthermore, this can be generalized so that the entries in A can be real numbers representing connection strengths, as in a stochastic matrix.

In general, there will be many different eigenvalues <math>\lambda</math> for which a non-zero eigenvector solution exists. Since the entries in the adjacency matrix are non-negative, there is a unique largest eigenvalue, which is real and positive, by the Perron–Frobenius theorem. This greatest eigenvalue results in the desired centrality measure. The <math>v^{th}</math> component of the related eigenvector then gives the relative centrality score of the vertex <math>v</math> in the network. The eigenvector is only defined up to a common factor, so only the ratios of the centralities of the vertices are well defined. To define an absolute score one must normalise the eigenvector, e.g., such that the sum over all vertices is 1 or the total number of vertices n. Power iteration is one of many eigenvalue algorithms that may be used to find this dominant eigenvector. Furthermore, this can be generalized so that the entries in A can be real numbers representing connection strengths, as in a stochastic matrix.

一般情况下，存在许多不同的特征值，对于这些特征值存在一个非零特征向量解。由于邻接矩阵中的条目是非负的，所以有一个唯一的最大特征值，它是实的和正的，由 Perron-弗罗贝尼乌斯定理提供。这个最大的特征值导致期望的中心性度量。相关特征向量的 < math > v ^ { th } </math > 分量给出了网络中顶点 < math > v </math > 的相对中心性评分。特征向量只定义了一个公共因子，所以只有顶点中心的比例是明确定义的。要定义一个绝对分数，必须对特征向量进行规范化，例如，使所有顶点的和为1或顶点的总数。此外，这可以通用化，使得 a 中的条目可以是真实的数字，表示连接强度，就像转移矩阵一样。

一般情况下，存在许多不同的特征值，对于这些特征值存在一个非零特征向量解。由于邻接矩阵中的条目非负，所以由 Perron-弗罗贝尼乌斯定理得出，有一个实的和正的唯一最大特征值。由这个最大的特征值得出期望的中心性度量。相关特征向量的 < math > v ^ { th } </math > 分量给出了网络中顶点 < math > v </math > 的相对中心性评分。特征向量只定义了一个公共因子，所以只有顶点中心的比例是明确定义的。要定义一个绝对分数，必须对特征向量进行标准化，例如，使所有顶点的和为1或顶点的总数n。此外，这可以通用，使得 a 中的条目可以是表示连接强度的真实数字，就像随机矩阵一样。

==Katz centrality==

==Katz centrality==

{{main|Katz centrality}}

{{main|Katz centrality}}

Katz centrality is a generalization of degree centrality. Degree centrality measures the number of direct neighbors, and Katz centrality measures the number of all nodes that can be connected through a path, while the contributions of distant nodes are penalized. Mathematically, it is defined as

Katz centrality is a generalization of degree centrality. Degree centrality measures the number of direct neighbors, and Katz centrality measures the number of all nodes that can be connected through a path, while the contributions of distant nodes are penalized. Mathematically, it is defined as

Katz 中心性是程度中心性的推广。程度中心性度量的是直接邻居的数量，Katz 中心性度量的是通过一条路径可以连接的所有节点的数量，而远处节点的贡献会受到惩罚。在数学上，它被定义为

Katz 中心性是度中心性的推广。度中心性度量的是直接邻居的数量，Katz 中心性度量的是通过一条路径可以连接的所有节点的数量，而远处节点的贡献会受到（惩罚？）削弱。在数学上，它被定义为

==Percolation centrality==

==Percolation centrality==

A slew of centrality measures exist to determine the ‘importance’ of a single node in a complex network. However, these measures quantify the importance of a node in purely topological terms, and the value of the node does not depend on the ‘state’ of the node in any way. It remains constant regardless of network dynamics. This is true even for the weighted betweenness measures. However, a node may very well be centrally located in terms of betweenness centrality or another centrality measure, but may not be ‘centrally’ located in the context of a network in which there is percolation. Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by Piraveenan et al.<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>

A slew of centrality measures exist to determine the ‘importance’ of a single node in a complex network. However, these measures quantify the importance of a node in purely topological terms, and the value of the node does not depend on the ‘state’ of the node in any way. It remains constant regardless of network dynamics. This is true even for the weighted betweenness measures. However, a node may very well be centrally located in terms of betweenness centrality or another centrality measure, but may not be ‘centrally’ located in the context of a network in which there is percolation. Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by Piraveenan et al.<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>

A slew of centrality measures exist to determine the ‘importance’ of a single node in a complex network. However, these measures quantify the importance of a node in purely topological terms, and the value of the node does not depend on the ‘state’ of the node in any way. It remains constant regardless of network dynamics. This is true even for the weighted betweenness measures. However, a node may very well be centrally located in terms of betweenness centrality or another centrality measure, but may not be ‘centrally’ located in the context of a network in which there is percolation. Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by Piraveenan et al.

A slew of centrality measures exist to determine the ‘importance’ of a single node in a complex network. However, these measures quantify the importance of a node in purely topological terms, and the value of the node does not depend on the ‘state’ of the node in any way. It remains constant regardless of network dynamics. This is true even for the weighted betweenness measures. However, a node may very well be centrally located in terms of betweenness centrality or another centrality measure, but may not be ‘centrally’ located in the context of a network in which there is percolation. Percolation of a ‘contagion’ occurs in complex networks in a number of scenarios. For example, viral or bacterial infection can spread over social networks of people, known as contact networks. The spread of disease can also be considered at a higher level of abstraction, by contemplating a network of towns or population centres, connected by road, rail or air links. Computer viruses can spread over computer networks. Rumours or news about business offers and deals can also spread via social networks of people. In all of these scenarios, a ‘contagion’ spreads over the links of a complex network, altering the ‘states’ of the nodes as it spreads, either recoverably or otherwise. For example, in an epidemiological scenario, individuals go from ‘susceptible’ to ‘infected’ state as the infection spreads. The states the individual nodes can take in the above examples could be binary (such as received/not received a piece of news), discrete (susceptible/infected/recovered), or even continuous (such as the proportion of infected people in a town), as the contagion spreads. The common feature in all these scenarios is that the spread of contagion results in the change of node states in networks. Percolation centrality (PC) was proposed with this in mind, which specifically measures the importance of nodes in terms of aiding the percolation through the network. This measure was proposed by Piraveenan et al.

在复杂网络中，存在大量的中心性度量来确定单个节点的“重要性”。然而，这些度量单纯从拓扑学的角度来量化节点的重要性，节点的值并不以任何方式依赖于节点的状态。不管网络动态如何，它都保持不变。即使对于加权的两者之间的度量也是如此。然而，一个节点可能很好地位于中间中心性或其他中心性度量的中心位置，但可能不是位于有过滤的网络的上下文中的中心位置。在许多情况下，复杂网络中都会出现“传染”现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，每个节点可以采取的状态可以是二进制的(例如接收/没有接收到一条新闻)、离散的(易感/受感染/康复) ，甚至是连续的(例如一个城镇中受感染的人的比例) ，随着传染的扩散。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。渗滤中心性(PC)就是基于这个思想而提出的，它特别地衡量了节点在协助网络渗滤方面的重要性。这项措施是由 piraveanan 等人提出的。

在复杂网络中，存在大量的中心性度量来确定单个节点的“重要性”。然而，这些度量单纯从拓扑学的角度来量化节点的重要性，节点的值并不以任何方式依赖于节点的状态。不管网络动态如何，它都保持不变。即使对于加权的两者之间的度量也是如此。然而，一个节点可能很好地位于中介中心性或其他中心性度量的中心位置，但可能不是位于有过滤的网络的上下文中的中心位置。在许多情况下，复杂网络中都会出现“传染”现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，随着传染的扩散，每个节点可以采取的状态可以是二进制的(例如接收/没有接收到一条新闻)、离散的(易感/受感染/康复) ，甚至是连续的(例如一个城镇中受感染的人的比例) 。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。渗滤中心性(PC)就是基于这个思想而提出的，它特别地衡量了节点在协助网络渗滤方面的重要性。这项措施是由 piraveanan 等人提出的。

Percolation centrality is defined for a given node, at a given time, as the proportion of ‘percolated paths’ that go through that node. A ‘percolated path’ is a shortest path between a pair of nodes, where the source node is percolated (e.g., infected). The target node can be percolated or non-percolated, or in a partially percolated state.

Percolation centrality is defined for a given node, at a given time, as the proportion of ‘percolated paths’ that go through that node. A ‘percolated path’ is a shortest path between a pair of nodes, where the source node is percolated (e.g., infected). The target node can be percolated or non-percolated, or in a partially percolated state.

过滤中心性定义为在给定时间内一个给定节点的过滤路径的比例。“渗滤路径”是一对节点之间的最短路径，其中源节点被渗滤(例如，被感染)。目标节点可以是过滤的或非过滤的，或处于部分过滤状态。

渗滤中心性定义为在给定时间内一个给定节点的过滤路径的比例。“渗滤路径”是一对节点之间的最短路径，其中源节点被渗滤(例如，被感染)。目标节点可以是过滤的或非过滤的，或处于部分过滤状态。

The attached weights to the percolation paths depend on the percolation levels assigned to the source nodes, based on the premise that the higher the percolation level of a source node is, the more important are the paths that originate from that node. Nodes which lie on shortest paths originating from highly percolated nodes are therefore potentially more important to the percolation. The definition of PC may also be extended to include target node weights as well. Percolation centrality calculations run in <math>O(NM)</math> time with an efficient implementation adopted from Brandes' fast algorithm and if the calculation needs to consider target nodes weights, the worst case time is <math>O(N^3)</math>.

The attached weights to the percolation paths depend on the percolation levels assigned to the source nodes, based on the premise that the higher the percolation level of a source node is, the more important are the paths that originate from that node. Nodes which lie on shortest paths originating from highly percolated nodes are therefore potentially more important to the percolation. The definition of PC may also be extended to include target node weights as well. Percolation centrality calculations run in <math>O(NM)</math> time with an efficient implementation adopted from Brandes' fast algorithm and if the calculation needs to consider target nodes weights, the worst case time is <math>O(N^3)</math>.

渗流路径的权重取决于分配给源节点的渗流水平，前提是源节点的渗流水平越高，源节点的路径就越重要。因此，位于源自高渗滤节点的最短路径上的节点可能对渗滤更为重要。PC 的定义也可以扩展到包括目标节点的权重。逾渗中心性计算运行在 < math > o (NM) </math > 时间，采用了 Brandes 快速算法的有效实现，如果计算需要考虑目标节点的权重，最坏情况下时间为 < math > o (n ^ 3) </math > 。

渗流路径的权重取决于分配给源节点的渗流水平，前提是源节点的渗流水平越高，源节点的路径就越重要。因此，位于源自高渗滤节点的最短路径上的节点可能对渗滤更为重要。PC 的定义也可以扩展到包括目标节点的权重。渗滤中心性计算运行在 < math > o (NM) </math > 时间，采用了 Brandes 快速算法的有效实现，如果计算需要考虑目标节点的权重，最坏情况下时间为 < math > o (n ^ 3) </math > 。

==Cross-clique centrality==

==Cross-clique centrality==

'''Cross-clique centrality''' of a single node in a complex graph determines the connectivity of a node to different [[clique (graph theory)|clique]]s. A node with high cross-clique connectivity facilitates the propagation of information or disease in a graph. Cliques are subgraphs in which every node is connected to every other node in the clique. The cross-clique connectivity of a node <math>v</math> for a given graph <math>G:=(V,E)</math> with <math>|V|</math> vertices and <math>|E|</math> edges, is defined as <math>X(v)</math> where <math>X(v)</math> is the number of cliques to which vertex <math>v</math> belongs.  This measure was used in <ref name="xssworms">{{cite journal |last1 = Faghani|first1 = Mohamamd Reza| year=2013| title = A Study of XSS Worm Propagation and Detection Mechanisms in Online Social Networks | journal = IEEE Transactions on Information Forensics and Security|volume = 8|issue = 11|pages = 1815–1826|doi = 10.1109/TIFS.2013.2280884}}</ref> but was first proposed by Everett and Borgatti in 1998 where they called it clique-overlap centrality.

'''Cross-clique centrality''' of a single node in a complex graph determines the connectivity of a node to different [[clique (graph theory)|clique]]s. A node with high cross-clique connectivity facilitates the propagation of information or disease in a graph. Cliques are subgraphs in which every node is connected to every other node in the clique. The cross-clique connectivity of a node <math>v</math> for a given graph <math>G:=(V,E)</math> with <math>|V|</math> vertices and <math>|E|</math> edges, is defined as <math>X(v)</math> where <math>X(v)</math> is the number of cliques to which vertex <math>v</math> belongs.  This measure was used in <ref name="xssworms">{{cite journal |last1 = Faghani|first1 = Mohamamd Reza| year=2013| title = A Study of XSS Worm Propagation and Detection Mechanisms in Online Social Networks | journal = IEEE Transactions on Information Forensics and Security|volume = 8|issue = 11|pages = 1815–1826|doi = 10.1109/TIFS.2013.2280884}}</ref> but was first proposed by Everett and Borgatti in 1998 where they called it clique-overlap centrality.