7,129
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由水流心不竞初译，未经审校，带来阅读不便，请见谅。已由Bai审校。+ + + + + − + − + − In [[graph theory]] and [[network theory|network analysis]], indicators of '''centrality''' identify the most important [[vertex (graph theory)|vertices]] within a graph. Applications include identifying the most influential person(s) in a [[social network]], key infrastructure nodes in the [[Internet]] or [[urban network]]s, and [[super-spreader]]s of disease. Centrality concepts were first developed in [[social network analysis]], and many of the terms used to measure centrality reflect their [[sociology|sociological]] origin.<ref name="NewmanNetworks">Newman, M.E.J. 2010. ''Networks: An Introduction.'' Oxford, UK: Oxford University Press.</ref> − − In graph theory and network analysis, indicators of centrality identify the most important vertices within a graph. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, and super-spreaders of disease. Centrality concepts were first developed in , and many of the terms used to measure centrality reflect their sociological origin. − − They should not be confused with [[node influence metric]]s, which seek to quantify the influence of every node in the network. − − They should not be confused with node influence metrics, which seek to quantify the influence of every node in the network. − − 在'''<font color="#ff8000">图论 graph theory </font>'''和'''<font color="#ff8000">网络分析 network analysis </font>'''中，'''<font color="#ff8000">中心性 centrality </font>'''指标用于识别图中最重要的顶点。其应用包括在社交网络中识别出最有影响力的个人，在因特网或城市网络中识别出最为关键的基础设施节点，以及识别疾病的超级传播者。中心性的概念最初是在'''<font color="#ff8000">社交网络分析 social network analysis</font>'''中发展起来的，许多用于衡量中心性的术语都反映出了它们的社会学起源。<ref name="NewmanNetworks">Newman, M.E.J. 2010. ''Networks: An Introduction.'' Oxford, UK: Oxford University Press.</ref>中心性不应与节点影响度相混淆，后者意在量化网络中每个节点的影响。 − − ==中心性指数的定义与特性Definition and characterization of centrality indices== − − Centrality indices are answers to the question "What characterizes an important vertex?" The answer is given in terms of a real-valued function on the vertices of a graph, where the values produced are expected to provide a ranking which identifies the most important nodes.<ref name="Bonacich1987">{{cite journal |last1= Bonacich |first1= Phillip|year= 1987 |title= Power and Centrality: A Family of Measures | journal=American Journal of Sociology |volume= 92|issue= 5|pages= 1170–1182|doi=10.1086/228631 |url= }}<!--|accessdate=July 11, 2014--></ref><ref name="Borgatti2005">{{cite journal |last1= Borgatti |first1= Stephen P.|year= 2005 |title= Centrality and Network Flow |journal=Social Networks |volume= 27|issue= |pages= 55–71|doi=10.1016/j.socnet.2004.11.008 |url= |citeseerx= 10.1.1.387.419}}<!--|accessdate= July 11, 2014--></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">{{cite journal |author = 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.|title = Eigenvector centrality for characterization of protein allosteric pathways|journal = Proceedings of the National Academy of Sciences|volume = 115|number = 52|pages = E12201–E12208|year = 2018|doi = 10.1073/pnas.1810452115|pmid = 30530700|pmc = 6310864}}</ref> − − Centrality indices are answers to the question "What characterizes an important vertex?" The answer is given in terms of a real-valued function on the vertices of a graph, where the values produced are expected to provide a ranking which identifies the most important nodes. − − '''<font color="#ff8000">中心性指数 centrality indices</font>'''是对“重要顶点的特征是什么？”这一问题的回答。这个回答是以图中顶点的实值函数的形式给出的，可根据产生的函数值排序以确定最为重要的节点。<ref name="Bonacich1987">{{cite journal |last1= Bonacich |first1= Phillip|year= 1987 |title= Power and Centrality: A Family of Measures | journal=American Journal of Sociology |volume= 92|issue= 5|pages= 1170–1182|doi=10.1086/228631 |url= }}<!--|accessdate=July 11, 2014--></ref><ref name="Borgatti2005">{{cite journal |last1= Borgatti |first1= Stephen P.|year= 2005 |title= Centrality and Network Flow |journal=Social Networks |volume= 27|issue= |pages= 55–71|doi=10.1016/j.socnet.2004.11.008 |url= |citeseerx= 10.1.1.387.419}}<!--|accessdate= July 11, 2014--></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">{{cite journal |author = 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.|title = Eigenvector centrality for characterization of protein allosteric pathways|journal = Proceedings of the National Academy of Sciences|volume = 115|number = 52|pages = E12201–E12208|year = 2018|doi = 10.1073/pnas.1810452115|pmid = 30530700|pmc = 6310864}}</ref> − − The word "importance" has a wide number of meanings, leading to many different definitions of centrality. Two categorization schemes have been proposed. − − The word "importance" has a wide number of meanings, leading to many different definitions of centrality. Two categorization schemes have been proposed. − "Importance" can be conceived in relation to a type of flow or transfer across the network. This allows centralities to be classified by the type of flow they consider important.<ref name=Borgatti2005/> "Importance" can alternatively be conceived as involvement in the cohesiveness of the network. This allows centralities to be classified based on how they measure cohesiveness.<ref name="Borgatti2006">{{cite journal |last1= Borgatti |first1= Stephen P.|last2= Everett |first2= Martin G.|year= 2006 |title= A Graph-Theoretic Perspective on Centrality |journal=Social Networks |volume= 28|issue= 4|pages= 466–484|doi=10.1016/j.socnet.2005.11.005 |url= }}<!--|accessdate= July 11, 2014--></ref> Both of these approaches divide centralities in distinct categories. A further conclusion is that a centrality which is appropriate for one category will often "get it wrong" when applied to a different category.<ref name=Borgatti2005/> − + − “重要性”可以被设想为与网络中的某种流动或传输有关。这允许根据重要的流动的类型对中心性进行分类。<ref name=Borgatti2005/> “重要性”也可以被设想为与网络的'''<font color="#ff8000">内聚力 cohesiveness</font>'''有关。这允许根据内聚力的度量方式对中心性进行分类。<ref name="Borgatti2006">{{cite journal |last1= Borgatti |first1= Stephen P.|last2= Everett |first2= Martin G.|year= 2006 |title= A Graph-Theoretic Perspective on Centrality |journal=Social Networks |volume= 28|issue= 4|pages= 466–484|doi=10.1016/j.socnet.2005.11.005 |url= }}<!--|accessdate= July 11, 2014--></ref>这两种方法在不同类别中划分了中心性。进一步的结论是，适用于某一类别的中心性在应用于另一类别时往往会“出错”。<ref name=Borgatti2005/> − When centralities are categorized by their approach to cohesiveness, it becomes apparent that the majority of centralities inhabit one category. The count of the number of walks starting from a given vertex differs only in how walks are defined and counted. Restricting consideration to this group allows for a soft characterization which places centralities on a spectrum from walks of length one ([[Centrality#Degree centrality|degree centrality]]) to infinite walks ([[Centrality#Eigenvector centrality|eigenvalue centrality]]).<ref name=Bonacich1987/><ref name="Benzi2013">{{cite journal | last1=Benzi | first1=Michele | last2=Klymko| first2=Christine | year=2013 |title= A matrix analysis of different centrality measures |arxiv=1312.6722 | doi=10.1137/130950550 | volume=36 | issue=2 | journal=SIAM Journal on Matrix Analysis and Applications | pages=686–706}}</ref> The observation that many centralities share this familial relationships perhaps explains the high rank correlations between these indices.+ − When centralities are categorized by their approach to cohesiveness, it becomes apparent that the majority of centralities inhabit one category. The count of the number of walks starting from a given vertex differs only in how walks are defined and counted. Restricting consideration to this group allows for a soft characterization which places centralities on a spectrum from walks of length one (degree centrality) to infinite walks (eigenvalue centrality). The observation that many centralities share this familial relationships perhaps explains the high rank correlations between these indices. − 当根据内聚力方法对中心性进行分类时，很明显大多数中心性都将被划分于同一类别。起始于给定顶点的步数总和仅取决于步数的定义以及计数方式。这种分类方式的不足表现为它仅能较弱的描绘中心性特征，即按照一步步长（'''<font color="#ff8000">度中心性 degree centrality</font>'''）到无穷步步长（'''<font color="#ff8000">特征向量中心性 eigenvalue centrality</font>'''）的方式将中心性置于一种光谱状的分类中。<ref name=Bonacich1987/><ref name="Benzi2013">{{cite journal | last1=Benzi | first1=Michele | last2=Klymko| first2=Christine | year=2013 |title= A matrix analysis of different centrality measures |arxiv=1312.6722 | doi=10.1137/130950550 | volume=36 | issue=2 | journal=SIAM Journal on Matrix Analysis and Applications | pages=686–706}}</ref>观察到许多中心性共享这种家庭关系，这或许能解释这些指数之间的高阶相关性。+ − − ===网络流特征Characterization by network flows=== − − A network can be considered a description of the paths along which something flows. This allows a characterization based on the type of flow and the type of path encoded by the centrality. A flow can be based on transfers, where each indivisible item goes from one node to another, like a package delivery going from the delivery site to the client's house. A second case is serial duplication, in which an item is replicated so that both the source and the target have it. An example is the propagation of information through gossip, with the information being propagated in a private way and with both the source and the target nodes being informed at the end of the process. The last case is parallel duplication, with the item being duplicated to several links at the same time, like a radio broadcast which provides the same information to many listeners at once.<ref name=Borgatti2005/> − − A network can be considered a description of the paths along which something flows. This allows a characterization based on the type of flow and the type of path encoded by the centrality. A flow can be based on transfers, where each indivisible item goes from one node to another, like a package delivery going from the delivery site to the client's house. A second case is serial duplication, in which an item is replicated so that both the source and the target have it. An example is the propagation of information through gossip, with the information being propagated in a private way and with both the source and the target nodes being informed at the end of the process. The last case is parallel duplication, with the item being duplicated to several links at the same time, like a radio broadcast which provides the same information to many listeners at oe. − + − Likewise, the type of path can be constrained to [[Distance (graph theory)|geodesics]] (shortest paths), [[Glossary of graph theory terms#path|paths]] (no vertex is visited more than once), [[Glossary of graph theory terms#trail|trails]] (vertices can be visited multiple times, no edge is traversed more than once), or [[Glossary of graph theory terms#walk|walks]] (vertices and edges can be visited/traversed multiple times).<ref name=Borgatti2005/> − − Likewise, the type of path can be constrained to geodesics (shortest paths), paths (no vertex is visited more than once), trails (vertices can be visited multiple times, no edge is traversed more than once), or walks (vertices and edges can be visited/traversed multiple times). − − 同样，路径类型可以被限定为'''<font color="#ff8000"> 测地线geodesics </font>'''(最短路径)、路径(对顶点的访问不超过一次)、小径(可以访问多次顶点，没有边被访问超过一次)或者步子(可以多次访问/穿过多次顶点和边)。 − − ===行走结构特征Characterization by walk structure=== − − An alternative classification can be derived from how the centrality is constructed. This again splits into two classes. Centralities are either ''radial'' or ''medial.'' Radial centralities count walks which start/end from the given vertex. The [[Centrality#Degree centrality|degree]] and [[Centrality#Eigenvector centrality|eigenvalue]] centralities are examples of radial centralities, counting the number of walks of length one or length infinity. Medial centralities count walks which pass through the given vertex. The canonical example is Freeman's [[Centrality#Betweenness centrality|betweenness]] centrality, the number of shortest paths which pass through the given vertex.<ref name=Borgatti2006/> − − An alternative classification can be derived from how the centrality is constructed. This again splits into two classes. Centralities are either radial or medial. Radial centralities count walks which start/end from the given vertex. The degree and eigenvalue centralities are examples of radial centralities, counting the number of walks of length one or length infinity. Medial centralities count walks which pass through the given vertex. The canonical example is Freeman's betweenness centrality, the number of shortest paths which pass through the given vertex. − − 可以从中心性的构造方式推导出另一种分类方法。这又分成了两个类。中心性可以是径向的，也可以是中间的。径向中心性计算从给定顶点开始/结束的步数。度中心性和特征向量中心性是'''<font color="#ff8000"> 径向中心性Radial centralities</font>'''的例子，计算长度为一或无穷大的步数。'''<font color="#ff8000"> 中间中心性Medial centralities</font>'''计算通过给定顶点的步数。典型的例子是弗里曼 Freeman的'''<font color="#ff8000"> 中介中心性Betweenness centrality,</font>'''，即通过给定顶点的最短路径的数量。<ref name=Borgatti2006/> − − − − − Likewise, the counting can capture either the ''volume'' or the ''length'' of walks. Volume is the total number of walks of the given type. The three examples from the previous paragraph fall into this category. Length captures the distance from the given vertex to the remaining vertices in the graph. Freeman's [[Centrality#Closeness centrality|closeness]] centrality, the total geodesic distance from a given vertex to all other vertices, is the best known example.<ref name=Borgatti2006/> Note that this classification is independent of the type of walk counted (i.e. walk, trail, path, geodesic). − − Likewise, the counting can capture either the volume or the length of walks. Volume is the total number of walks of the given type. The three examples from the previous paragraph fall into this category. Length captures the distance from the given vertex to the remaining vertices in the graph. Freeman's closeness centrality, the total geodesic distance from a given vertex to all other vertices, is the best known example. Note that this classification is independent of the type of walk counted (i.e. walk, trail, path, geodesic). − − 同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的'''<font color="#ff8000"> 接近中心性Closeness centrality</font>'''，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型(即：步行，小道，路径，测地线)。 − − Borgatti and Everett propose that this typology provides insight into how best to compare centrality measures. Centralities placed in the same box in this 2×2 classification are similar enough to make plausible alternatives; one can reasonably compare which is better for a given application. Measures from different boxes, however, are categorically distinct. Any evaluation of relative fitness can only occur within the context of predetermining which category is more applicable, rendering the comparison moot.<ref name=Borgatti2006/>+ + − Borgatti and Everett propose that this typology provides insight into how best to compare centrality measures. Centralities placed in the same box in this 2×2 classification are similar enough to make plausible alternatives; one can reasonably compare which is better for a given application. Measures from different boxes, however, are categorically distinct. Any evaluation of relative fitness can only occur within the context of predetermining which category is more applicable, rendering the comparison moot. − 博尔加蒂 Borgatti和埃弗雷特 Everett提出，这种类型为如何最好地比较中心性度量提供了见解。在这个2×2分类中，放在同一盒子中的中心性足够相似，可以做出合理的选择; 人们可以合理地比较哪个对于给定的应用更好。然而，不同盒子中的度量方法是截然不同的。只有在预先确定哪个类别更适用的情况下，对相对适应性的评估才会发生，这使得比较变得毫无意义。<ref name=Borgatti2006/>+ − ===光谱上存在的径向量中心Radial-volume centralities exist on a spectrum=== − The characterization by walk structure shows that almost all centralities in wide use are radial-volume measures. These encode the belief that a vertex's centrality is a function of the centrality of the vertices it is associated with. Centralities distinguish themselves on how association is defined.+ − The characterization by walk structure shows that almost all centralities in wide use are radial-volume measures. These encode the belief that a vertex's centrality is a function of the centrality of the vertices it is associated with. Centralities distinguish themselves on how association is defined.+ − Bonacich showed that if association is defined in terms of [[Glossary of graph theory terms#walk|walks]], then a family of centralities can be defined based on the length of walk considered.<ref name="Bonacich1987"/> [[Centrality#Degree centrality|Degree centrality]] counts walks of length one, while [[Centrality#Eigenvector centrality|eigenvalue centrality]] counts walks of length infinity. Alternative definitions of association are also reasonable. [[Alpha centrality]] allows vertices to have an external source of influence. Estrada's subgraph centrality proposes only counting closed paths (triangles, squares, etc.). − − Bonacich showed that if association is defined in terms of walks, then a family of centralities can be defined based on the length of walk considered. Degree centrality counts walks of length one, while eigenvalue centrality counts walks of length infinity. Alternative definitions of association are also reasonable. Alpha centrality allows vertices to have an external source of influence. Estrada's subgraph centrality proposes only counting closed paths (triangles, squares, etc.). − 博纳奇 Bonacich指出，如果联想是根据行走来定义的，那么可以根据考虑的行走长度来定义一个中心性家族。<ref name="Bonacich1987"/>度中心性计算长度为1的行走，特征向量中心性计算长度为无穷大的行走。关联的其他定义也是合理的。'''<font color="#ff8000"> 阿尔法中心性Alpha centrality</font>'''允许顶点有一个外部影响源。埃斯特拉达 Estrada的'''<font color="#ff8000"> 子图中心性Subgraph centrality </font>'''提出只计算封闭路径(三角形、正方形等)。).+ − The heart of such measures is the observation that powers of the graph's adjacency matrix gives the number of walks of length given by that power. Similarly, the matrix exponential is also closely related to the number of walks of a given length. An initial transformation of the adjacency matrix allows a different definition of the type of walk counted. Under either approach, the centrality of a vertex can be expressed as an infinite sum, either − − The heart of such measures is the observation that powers of the graph's adjacency matrix gives the number of walks of length given by that power. Similarly, the matrix exponential is also closely related to the number of walks of a given length. An initial transformation of the adjacency matrix allows a different definition of the type of walk counted. Under either approach, the centrality of a vertex can be expressed as an infinite sum, either − − 这些度量方法的核心是这种现象：图中'''<font color="#ff8000"> 邻接矩阵 adjacency matrix </font>'''的幂给出了由该幂给出的步长的数目。同样，'''<font color="#ff8000"> 矩阵指数Matrix exponential</font>'''也与给定步长的数目密切相关。邻接矩阵的初始转换允许对步行计数的类型进行不同的定义。无论采用哪种方法，顶点的中心性都可以表示为无穷和 + − <math>\sum_{k=0}^\infty A_{R}^{k} \beta^k </math> − − < math > sum _ { k = 0} ^ infty a _ { r } ^ { k } beta ^ k </math > − − − for matrix powers or − − for matrix powers or − − <math>\sum_{k=0}^\infty \frac{(A_R \beta)^k}{k!}</math> − − < math > sum { k = 0} ^ infty frac {(a _ r beta) ^ k }{ k！{/math > − − − − for matrix exponentials, where − − for matrix exponentials, where + + + − * <math>k</math> is walk length, − − * <math>A_R</math> is the transformed adjacency matrix, and − − * <math>\beta</math> is a discount parameter which ensures convergence of the sum. − − K为步长，A_R是邻接矩阵的转秩，\beta是保证收敛的折扣参数。 − − Bonacich's family of measures does not transform the adjacency matrix. [[Alpha centrality]] replaces the adjacency matrix with its [[resolvent formalism|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 [[Centrality#Degree centrality|degree centrality]]. As <math>\beta</math> approaches its maximal value, the indices converge to [[Centrality#Eigenvector centrality|eigenvalue centrality]].<ref name=Benzi2013/> − − 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的一系列度量并没有改变邻接矩阵。阿尔法中心性用它的解决方案替代了邻接矩阵。子图中心性用它的踪迹取代了邻接矩阵。一个令人吃惊的结论是，不管邻接矩阵最初的转变是什么，所有这些方法都有共同的限制行为。随着贝塔系数趋近于零，指数收敛到度中心性。随着贝塔系数接近其最大值，指数收敛到特征向量中心性。<ref name=Benzi2013/> + − ===博弈论中心性Game-theoretic centrality=== − The common feature of most of the aforementioned standard measures is that they assess the importance of a node by focusing only on the role that a node plays by itself. However, in many applications such an approach is inadequate because of synergies that may occur+ − − The common feature of most of the aforementioned standard measures is that they assess the importance of a node by focusing only on the role that a node plays by itself. However, in many applications such an approach is inadequate because of synergies that may occur − if the functioning of nodes is considered in groups. − − if the functioning of nodes is considered in groups. − + − Example of game-theoretic centrality+ − '''<font color="#ff8000"> 博弈论中心性 Game-theoretic centrality</font>'''的例子 + − 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 <ref>Michalak, Aadithya, Szczepański, Ravindran, & Jennings {{ArXiv|1402.0567}}</ref> 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 > 中开始，它们就能阻止疾病的传播。博弈论中心性试图利用博弈论中的工具来研究所描述的问题和机会。本文提出的方法<ref>Michalak, Aadithya, Szczepański, Ravindran, & Jennings {{ArXiv|1402.0567}}</ref>使用了 Shapley 值。由于 Shapley 值计算的时间复杂性，这一领域的大部分工作都集中在实现新的算法和方法，这些算法和方法依赖于网络的特殊拓扑结构或问题的特殊性质。这种方法可以将时间复杂度从指数级降低到多项式级。 − − − − Similarly, the solution concept [[authority distribution]] (<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>) 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)<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>, 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. − − 同样，权限分配的解决方案()<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>，比如美国大学排名。 − − == 重要限制Important limitations == − − Centrality indices have two important limitations, one obvious and the other subtle. The obvious limitation is that a centrality which is optimal for one application is often sub-optimal for a different application. Indeed, if this were not so, we would not need so many different centralities. An illustration of this phenomenon is provided by the [[Krackhardt kite graph]], for which three different notions of centrality give three different choices of the most central vertex.<ref>{{cite journal|title=Assessing the Political Landscape: Structure, Cognition, and Power in Organizations|first=David|last=Krackhardt|authorlink=David Krackhardt|journal=Administrative Science Quarterly|volume=35|issue=2|date=June 1990|pages=342–369|doi=10.2307/2393394|jstor=2393394}}</ref> − − Centrality indices have two important limitations, one obvious and the other subtle. The obvious limitation is that a centrality which is optimal for one application is often sub-optimal for a different application. Indeed, if this were not so, we would not need so many different centralities. An illustration of this phenomenon is provided by the Krackhardt kite graph, for which three different notions of centrality give three different choices of the most central vertex. + + − The more subtle limitation is the commonly held fallacy that vertex centrality indicates the relative importance of vertices. Centrality indices are explicitly designed to produce a ranking which allows indication of the most important vertices.<ref name=Bonacich1987/><ref name=Borgatti2005/> This they do well, under the limitation just noted. They are not designed to measure the influence of nodes in general. Recently, network physicists have begun developing [[node influence metric]]s to address this problem. − The more subtle limitation is the commonly held fallacy that vertex centrality indicates the relative importance of vertices. Centrality indices are explicitly designed to produce a ranking which allows indication of the most important vertices. This they do well, under the limitation just noted. They are not designed to measure the influence of nodes in general. Recently, network physicists have begun developing node influence metrics to address this problem.+ − 更不易察觉的限制是通常会错误地认为顶点中心性表示顶点的相对重要性。中心性指数被明确地设计来产生一个指出最重要顶点的排名。<ref name=Bonacich1987/><ref name=Borgatti2005/>在刚才提到的限制下，他们做得很好。它们通常不用来度量节点的影响力。最近，网络物理学家已经开始开发'''<font color="#ff8000">节点影响力度量Node influence metrics </font>'''来解决这个问题。 − − − − The error is two-fold. Firstly, a ranking only orders vertices by importance, it does not quantify the difference in importance between different levels of the ranking. This may be mitigated by applying [[Centrality#Freeman centralization|Freeman centralization]] to the centrality measure in question, which provide some insight to the importance of nodes depending on the differences of their centralization scores. Furthermore, Freeman centralization enables one to compare several networks by comparing their highest centralization scores.<ref name="Freeman1979"/> This approach, however, is seldom seen in practice.{{citation needed|reason=I've come across quite some theoretical studies that indicate otherwise. My suggestion is to remove this sentence, if reasonable citation is not provided.|date=September 2015}} − − The error is two-fold. Firstly, a ranking only orders vertices by importance, it does not quantify the difference in importance between different levels of the ranking. This may be mitigated by applying Freeman centralization to the centrality measure in question, which provide some insight to the importance of nodes depending on the differences of their centralization scores. Furthermore, Freeman centralization enables one to compare several networks by comparing their highest centralization scores. This approach, however, is seldom seen in practice. − − 错误有两方面。首先，一个排名只根据顶点的重要性排序，它并不对节点重要性的不同水平进行量化区分。这可以通过将 '''<font color="#ff8000"> 弗里曼中心度Freeman centralization</font>'''应用到中心性度量来缓解，这可以根据节点的中心度得分差异对节点的重要性提供一些见解。此外，弗里曼中心度使人们能够通过比较几个网络的最高中心度得分来比较它们。<ref name="Freeman1979"/>然而，这种方法在实践中很少见到。{{citation needed|reason=I've come across quite some theoretical studies that indicate otherwise. My suggestion is to remove this sentence, if reasonable citation is not provided.|date=September 2015}} − − − − − Secondly, the features which (correctly) identify the most important vertices in a given network/application do not necessarily generalize to the remaining vertices. − − Secondly, the features which (correctly) identify the most important vertices in a given network/application do not necessarily generalize to the remaining vertices. − For the majority of other network nodes the rankings may be meaningless.<ref name="Lawyer2015" /><ref name="daSilva2012">{{cite journal | last1=da Silva|first1=Renato |last2=Viana|first2=Matheus|last3=da F. Costa |first3=Luciano| title=Predicting epidemic outbreak from individual features of the spreaders| journal=J. Stat. Mech.: Theory Exp. | year=2012|volume=2012|pages=P07005|number=7 | doi=10.1088/1742-5468/2012/07/p07005|arxiv=1202.0024|bibcode=2012JSMTE..07..005A}}</ref><ref name="Bauer2012">{{cite journal | last1=Bauer|first1=Frank | last2=Lizier|first2=Joseph|title=Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach| journal=Europhys Lett | year=2012| volume=99| pages=68007|number=6 | doi=10.1209/0295-5075/99/68007|arxiv=1203.0502|bibcode=2012EL.....9968007B}}</ref><ref name="Sikic2013">{{ cite journal| last1= Sikic| first1=Mile|last2=Lancic|first2=Alen|last3=Antulov-Fantulin|first3=Nino|last4=Stefanic|first4=Hrvoje| title = Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes? |journal = The European Physical Journal B |volume=86 |number=10 |pages=1–13 |year=2013 | doi=10.1140/epjb/e2013-31025-5|arxiv=1110.2558 | bibcode=2013EPJB...86..440S}}</ref> This explains why, for example, only the first few results of a Google image search appear in a reasonable order. The pagerank is a highly unstable measure, showing frequent rank reversals after small adjustments of the jump parameter.<ref name="Ghoshal2011">{{cite journal | last1=Ghoshal | first1= G. | last2= Barabsi |first2= A L | title = Ranking stability and super-stable nodes in complex networks. | journal = Nat Commun | volume =2 | page = 394| year= 2011 | doi=10.1038/ncomms1396 | pmid= 21772265 | bibcode=2011NatCo...2..394G | doi-access= free }}</ref> − − For the majority of other network nodes the rankings may be meaningless. This explains why, for example, only the first few results of a Google image search appear in a reasonable order. The pagerank is a highly unstable measure, showing frequent rank reversals after small adjustments of the jump parameter. − − − − − While the failure of centrality indices to generalize to the rest of the network may at first seem counter-intuitive, it follows directly from the above definitions. − − While the failure of centrality indices to generalize to the rest of the network may at first seem counter-intuitive, it follows directly from the above definitions. − Complex networks have heterogeneous topology. To the extent that the optimal measure depends on the network structure of the most important vertices, a measure which is optimal for such vertices is sub-optimal for the remainder of the network.<ref name="Lawyer2015">{{cite journal |last1= Lawyer |first1= Glenn |year= 2015 |title= Understanding the spreading power of all nodes in a network: a continuous-time perspective |journal=Sci Rep |volume=5|pages=8665|doi=10.1038/srep08665 |pmid=25727453 |pmc=4345333|arxiv=1405.6707|bibcode=2015NatSR...5E8665L}}</ref> − − Complex networks have heterogeneous topology. To the extent that the optimal measure depends on the network structure of the most important vertices, a measure which is optimal for such vertices is sub-optimal for the remainder of the network. − − 复杂网络具有异构的拓扑结构。如果最佳度量取决于最重要顶点的网络结构，对于这些顶点最优的度量对于网络的其余部分是次优的。 − − ==Degree centrality== − =='''<font color="#ff8000"> 度中心性Degree centrality</font>'''== − {{Main|Degree (graph theory)}} − − − − [[File:6 centrality measures.png|thumb|right|300px|Examples of A) [[Betweenness centrality]], B) [[Closeness centrality]], C) [[Eigenvector centrality]], D) [[Degree centrality]], E) [[Centrality#Harmonic centrality|Harmonic centrality]] and F) [[Katz centrality]] of the same graph.]] − − Examples of A) [[Betweenness centrality, B) Closeness centrality, C) Eigenvector centrality, D) Degree centrality, E) Harmonic centrality and F) Katz centrality of the same graph.]] − 同一幅图中的实例A中介中心性，B紧密中心性，C特征向量中心性,D度中心性，E调和中心性，F'''<font color="#ff8000">卡兹中心性 Katz centrality </font>'''+ − 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.+ + + − 历史上第一个并且概念上最简单是度中心性，它定义为一个节点上事件的链接数量(即一个节点拥有的关系数量)。度可以解释为节点捕获的任何流经网络的东西(例如病毒或某些信息)的直接风险。在有向网络的情况下(关系有方向) ，我们通常定义两个独立的度中心性的度量，即 '''<font color="#ff8000"> 入度Indegree</font>'''和'''<font color="#ff8000"> 出度 Outdegree</font>'''。因此，入度是指向该节点的关系数，出度是该节点指向其他节点的关系数。当关系与一些积极的方面如友谊或合作有关时，入度通常被解释为一种受欢迎的形式，而出度则被解释为一种合群的形式。 − − − − The degree centrality of a vertex <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 − − The degree centrality of a vertex <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 − − 对于给定的图 g: = (v，e) </math > 与 < math > | v | </math > 顶点和 < math > | e | </math > 边，顶点的度中心性定义为 + − <math>C_D(v)= \deg(v)</math> − − <math>C_D(v)= \deg(v)</math> − − − − Calculating degree centrality for all the nodes in a graph takes [[big theta|<math>\Theta(V^2)</math>]] in a [[dense matrix|dense]] [[adjacency matrix]] representation of the graph, and for edges takes <math>\Theta(E)</math> in a [[sparse matrix]] representation. − Calculating degree centrality for all the nodes in a graph takes <math>\Theta(V^2)</math> in a dense adjacency matrix representation of the graph, and for edges takes <math>\Theta(E)</math> in a sparse matrix representation.+ − 计算一个图中所有节点的度中心性，在图的密集邻接矩阵表示中采用 Theta (v ^ 2) </math > ，在边的稀疏矩阵表示中采用Theta (e) </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''.<ref>Freeman, Linton C. "Centrality in social networks conceptual clarification." Social networks 1.3 (1979): 215–239.</ref> 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>): − − 节点级中心性的定义可以扩展到整个图，在这种情况下，我们指的是图的中心度。<ref>Freeman, Linton C. "Centrality in social networks conceptual clarification." Social networks 1.3 (1979): 215–239.</ref>设 < math > v </math > 为 < math > g </math > 中度中心性最高的节点。让 < math > x: = (y，z) </math > 是 < math > | y | </math > 节点连接图，最大化下列数量(< math > y * </math > 是 < math > 中度最高的节点) : + − <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 > − − − − 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>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)]}{H}</math> − − < math > c _ d (g) = frac { sum ^ { | v | } _ { i = 1}[ c _ d (v *)-c _ d (v _ i)]}{ h } </math > − − − − The value of <math>H</math> is maximized when the graph <math>X</math> contains one central node to which all other nodes are connected (a [[star graph]]), and in this case − − The value of <math>H</math> is maximized when the graph <math>X</math> contains one central node to which all other nodes are connected (a star graph), and in this case − − 当图形 < math > x </math > 包含与一个所有其他节点都连接的中心节点(一个星形图)时，< math > h </math > 的值最大化，在这种情况下 + − <math>H=(n-1)\cdot((n-1)-1)=n^2-3n+2.</math> − − (n-1)-1) = n ^ 2-3n + 2 − − − − So, for any graph <math>G:=(V,E),</math> − − So, for any graph <math>G:=(V,E),</math> − − 所以，对于任意的图 < math > 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 > − − ==Closeness centrality== − =='''<font color="#ff8000"> 紧密中心性Closeness centrality</font>'''== − {{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. − − 在连通图中，节点的标准紧密中心性(或贴近性)是节点与图中所有其他节点之间最短路径的平均长度。因此，一个节点越是中心，它就越接近所有其他节点。 + + − Closeness was defined by [[Alex Bavelas]] (1950) as the [[Multiplicative inverse|reciprocal]] of the '''farness''',<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|hdl=10338.dmlcz/101401|last1=Sabidussi|first1=G|hdl-access=free}}</ref> that is:+ − − Closeness was defined by Alex Bavelas (1950) as the reciprocal of the farness, that is: − − 亚历克斯 · 巴维拉斯 Alex Bavelas (1950)将贴近性定义为相对于距离的倒数，即: − − <math>C(x)= \frac{1}{\sum_y d(y,x)}</math> − C (x) = frac {1}{ sum _ y d (y，x)} </math > + + − where <math>d(y,x)</math> is the [[Distance (graph theory)|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 > 是图中的节点数。这种调整允许比较不同大小图形的节点。 − − − − Taking distances ''from'' or ''to'' all other nodes is irrelevant in undirected graphs, whereas it can produce totally different results in [[directed graph]]s (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). − − 从所有其他节点或到所有其他节点的距离在'''<font color="#ff8000"> 无向图Undirected graphs</font>'''中是不相关的，但是在'''<font color="#ff8000"> 有向图Directed graphs</font>'''中可能产生完全不同的结果(例如:一个网站可以从传出链接获得高的紧密中心性，而从传入链接获得低的紧密中心性）。 − − − − ===Harmonic centrality=== − =='''<font color="#ff8000"> 调和中心性Harmonic centrality</font>'''== − − 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: − − 在一个(不一定是连通的)图中，调和中心性反转了紧密中心性定义中的和互反运算: + − − <math>H(x)= \sum_{y \neq x} \frac{1}{d(y,x)}</math> − − < math > h (x) = sum { y neq x } frac {1}{ d (y，x)} </math > + − where <math>1 / d(y,x) = 0</math> if there is no path from <math>y</math> to <math>x</math>. Harmonic centrality can be normalized by dividing by <math>N-1</math>, where <math>N</math> is the number of nodes in the graph. − where <math>1 / d(y,x) = 0</math> if there is no path from <math>y</math> to <math>x</math>. Harmonic centrality can be normalized by dividing by <math>N-1</math>, where <math>N</math> is the number of nodes in the graph.+ − 其中 < math > 1/d (y，x) = 0 </math > 如果没有来自< math > y </math > to < math > x </math >的路径 。调和中心性可以通过除以 < math > N-1 </math > 来标准化，其中 < math > n </math > 是图中的节点数。 + + + − Harmonic centrality was proposed by [[Massimo Marchiori|Marchiori]] and [[Vito Latora|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> and then independently by Dekker (2005), using the name "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> and by 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>+ − Harmonic centrality was proposed by Marchiori and Latora (2000) and then independently by Dekker (2005), using the name "valued centrality," and by Rochat (2009). − 调和中心性是由马奇奥里 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)以“有价值的中心性”之名独立提出的，<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>+ − ==Betweenness centrality==+ − =='''<font color="#ff8000"> 中介中心性Betweenness centrality</font>'''== − {{Main|Betweenness centrality}} + − [[File:Graph betweenness.svg|240px|right|thumb|Hue (from red = 0 to blue = max) shows the node betweenness.]]+ − − Hue (from red = 0 to blue = max) shows the node betweenness. − − 色调(从红色 = 0到蓝色 = max)表示'''<font color="#ff8000"> 节点中介性node betweenness </font>'''。 − − − − '''Betweenness''' is a centrality measure of a [[vertex (graph theory)|vertex]] within a [[Graph (discrete mathematics)|graph]] (there is also [[edge (graph theory)|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]]<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> In his conception, vertices that have a high probability to occur on a randomly chosen [[shortest path problem|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. − − 中介性是图中顶点的中心性度量(也有边中介性，这里没有讨论)。中介中心性量化了一个节点沿着其他两个节点之间的最短路径充当桥梁的次数。在林顿 · 弗里曼 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>的概念中，它是作为一种量化一个人对社交网络中其他人之间交流控制的度量被引入的，在两个随机选择的顶点之间随机选择的最短路径上出现概率高的顶点具有很高的中介性。 − − − − The betweenness of a vertex <math>v</math> in a graph <math>G:=(V,E)</math> with <math>V</math> vertices is computed as follows: − − The betweenness of a vertex <math>v</math> in a graph <math>G:=(V,E)</math> with <math>V</math> vertices is computed as follows: − − 在一个图 < math > g: = (v，e) </math > 与 < math > v </math > 的顶点中介性计算如下: − − − − # For each pair of vertices (''s'',''t''), compute the [[Shortest path problem|shortest paths]] between them. − − For each pair of vertices (s,t), compute the shortest paths between them. − − 对于每一对顶点(s，t) ，计算它们之间的最短路径。 − − # For each pair of vertices (''s'',''t''), determine the fraction of shortest paths that pass through the vertex in question (here, vertex ''v''). − − For each pair of vertices (s,t), determine the fraction of shortest paths that pass through the vertex in question (here, vertex v). − − 对于每对顶点(s，t) ，确定通过该顶点(这里是顶点 v)的最短路径的分数。 − − # Sum this fraction over all pairs of vertices (''s'',''t''). − − Sum this fraction over all pairs of vertices (s,t). − − 对所有顶点对(s，t)求这个分数的和。 − − − − More compactly the betweenness can be represented as:<ref name="brandes">{{cite journal |last1 = Brandes |first1 = Ulrik | year=2001 |title = A faster algorithm for betweenness centrality | journal = Journal of Mathematical Sociology| volume=25|issue = 2 | pages=163–177| url = http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024 | accessdate = October 11, 2011| format = PDF | doi=10.1080/0022250x.2001.9990249|citeseerx = 10.1.1.11.2024 }}</ref> − − More compactly the betweenness can be represented as: − − 更确切地说，中介性可以表示为: 第481行：
第194行： − <math>C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}}</math> − − { math > c _ b (v) = sum _ { s neq v neq t in v } frac { sigma _ st }(v)}{ sigma _ st } </math > − − − − 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 [[Digraph (mathematics)|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 theory)|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 > 的路径数。中介性也许可以通过除以不包括V的顶点对的数目被规范化，对于有向图是 < math > (n-1)(n-2) </math > ，对于无向图是 < math > (n-1)(n-2)/2 </math > 。例如，在一个无向星图中，中心顶点(包含在每个可能的最短路径中)的中介性为 < math > (n-1)(n-2)/2 </math > (1，如果标准化) ，而叶节点(包含在没有最短路径中)的中介性为0。 − − − − From a calculation aspect, both betweenness and closeness centralities of all vertices in a graph involve calculating the shortest paths between all pairs of vertices on a graph, which requires [[Big O notation|<math>O(V^3)</math>]] time with the [[Floyd–Warshall algorithm]]. However, on sparse graphs, [[Johnson's algorithm]] may be more efficient, taking [[Big O notation|<math>O(V^2 \log V + V E)</math>]] time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm<ref name=brandes/> which takes [[Big O notation|<math>O(V E)</math>]] time. Normally, these algorithms assume that graphs are undirected and connected with the allowance of loops and multiple edges. When specifically dealing with network graphs, often graphs are without loops or multiple edges to maintain simple relationships (where edges represent connections between two people or vertices). In this case, using Brandes' algorithm will divide final centrality scores by 2 to account for each shortest path being counted twice.<ref name="brandes" /> − From a calculation aspect, both betweenness and closeness centralities of all vertices in a graph involve calculating the shortest paths between all pairs of vertices on a graph, which requires <math>O(V^3)</math> time with the Floyd–Warshall algorithm. However, on sparse graphs, Johnson's algorithm may be more efficient, taking <math>O(V^2 \log V + V E)</math> time. In the case of unweighted graphs the calculations can be done with Brandes' algorithm which takes <math>O(V E)</math> time. Normally, these algorithms assume that graphs are undirected and connected with the allowance of loops and multiple edges. When specifically dealing with network graphs, often graphs are without loops or multiple edges to maintain simple relationships (where edges represent connections between two people or vertices). In this case, using Brandes' algorithm will divide final centrality scores by 2 to account for each shortest path being counted twice.+ − 从计算的角度来看，图中所有顶点的中介中心性和紧密中心性都涉及到计算图中所有顶点对之间的最短路径，采用<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== − =='''<font color="#ff8000">特征向量中心性 Eigenvector centrality</font>'''== − {{main|Eigenvector centrality}} − '''Eigenvector centrality''' (also called '''eigencentrality''') is a measure of the influence of a [[node (networking)|node]] in a [[network (mathematics)|network]]. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.<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"/> [[Google]]'s [[PageRank]] and the [[Katz centrality]] are variants of the eigenvector centrality.<ref name="ams">{{Cite web | url=http://www.ams.org/samplings/feature-column/fcarc-pagerank | title=American Mathematical Society}}</ref>+ − Eigenvector centrality (also called eigencentrality) is a measure of the influence of a node in a network. It assigns relative scores to all nodes in the network based on the concept that connections to high-scoring nodes contribute more to the score of the node in question than equal connections to low-scoring nodes.+ − 特征向量中心性 (也称为特征中心性)是对网络中节点影响的一种度量。它将相对得分分配给网络中的所有节点，这是基于这样一个概念: 连接得分高的节点比连接得分低的节点对得分贡献更大。<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> + − + − − === Using the adjacency matrix to find eigenvector centrality == − ==使用'''<font color="#ff8000"> 邻接矩阵The adjacency matrix</font>'''发现'''<font color="#ff8000">特征向量中心性 Eigenvector centrality</font>'''== − − For a given graph <math>G:=(V,E)</math> with <math>|V|</math> number of vertices let <math>A = (a_{v,t})</math> be the [[adjacency matrix]], i.e. <math>a_{v,t} = 1</math> if vertex <math>v</math> is linked to vertex <math>t</math>, and <math>a_{v,t} = 0</math> otherwise. The relative centrality score of vertex <math>v</math> can be defined as: − − For a given graph <math>G:=(V,E)</math> with <math>|V|</math> number of vertices let <math>A = (a_{v,t})</math> be the adjacency matrix, i.e. <math>a_{v,t} = 1</math> if vertex <math>v</math> is linked to vertex <math>t</math>, and <math>a_{v,t} = 0</math> otherwise. The relative centrality score of vertex <math>v</math> can be defined as: − − 对于一个给定的图 g: = (v，e) </math > 与 < math > | v | </math >的顶点数 让 < math > a = (a { v，t }) </math > 成为邻接矩阵。即，如果顶点 < math > > v </math > 与 math > t </math > 相连，而 < math > a { v，t } = 0 </math > 不然。顶点 < math > v </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> − − 在 m (v)} x _ t = frac {1}{ lambda } sum { t in g } a { v，t } x _ t </math > − + − − where <math>M(v)</math> is a set of the neighbors of <math>v</math> and <math>\lambda</math> is a constant. With a small rearrangement this can be rewritten in vector notation as the [[eigenvector]] equation − − where <math>M(v)</math> is a set of the neighbors of <math>v</math> and <math>\lambda</math> is a constant. With a small rearrangement this can be rewritten in vector notation as the eigenvector equation − − 其中 < math > m (v) </math > 是 < math >的相邻集合，而< math > > lambda </math >是一个常量。通过一个小的重新排列，这可以用向量符号重写为特征向量方程。 − <math>\mathbf{Ax} = {\lambda}\mathbf{x}</math> − − [ math > mathbf { Ax } = { lambda } mathbf { x } </math > − − − − In general, there will be many different [[eigenvalue]]s <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.<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> 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 algorithm]]s that may be used to find this dominant eigenvector.<ref name="ams" /> 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. − − 一般情况下，存在许多不同的特征值< 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中的项可以是表示连接强度的实数，就像在'''<font color="#ff8000"> 随机矩阵 Stochastic matrix</font>'''中一样。 − − ==Katz centrality== − =='''<font color="#ff8000"> 卡兹中心性 Katz centrality</font>'''== − {{main|Katz centrality}} − '''Katz centrality'''<ref>Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.</ref> 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 + 第568行：
第229行： − <math>x_i = \sum_{k=1}^{\infin}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math> − [数学][数学]+ − − − where <math>\alpha</math> is an attenuation factor in <math>(0,1)</math>. − − where <math>\alpha</math> is an attenuation factor in <math>(0,1)</math>. − − 其中 < math > alpha </math > 是 < math > (0,1) </math > 中的衰减因子。 − − − − Katz centrality can be viewed as a variant of eigenvector centrality. Another form of Katz centrality is − − Katz centrality can be viewed as a variant of eigenvector centrality. Another form of Katz centrality is − − <math>x_i = \alpha \sum_{j =1}^N a_{ij}(x_j+1).</math> − (x _ j + 1) + + − Compared to the expression of eigenvector centrality, <math>x_j</math> is replaced by <math>x_j+1.</math> − − Compared to the expression of eigenvector centrality, <math>x_j</math> is replaced by <math>x_j+1.</math> − − 与特征向量中心性的表达式相比，< math > x _ j </math > 被 < math > x _ j + 1所代替 − − − − It is shown that<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> the principal eigenvector (associated with the largest eigenvalue of <math>A</math>, the adjacency matrix) is the limit of Katz centrality as <math>\alpha</math> approaches <math>\tfrac{1}{\lambda}</math> from below. − − It is shown that the principal eigenvector (associated with the largest eigenvalue of <math>A</math>, the adjacency matrix) is the limit of Katz centrality as <math>\alpha</math> approaches <math>\tfrac{1}{\lambda}</math> from below. − − 结果表明，<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 > a </math > ，邻接矩阵的最大特征值相关)是卡兹中心性的极限，当 < math > alpha </math > 从下接近 < math > tfrac {1}{ lambda } </math >时 。 − − == PageRank centrality == − =='''<font color="#ff8000"> 网页排名中心性 PageRank centrality </font>'''== − − {{main|PageRank}}'''[[PageRank]]''' satisfies the following equation − − PageRank satisfies the following equation + − − <math>x_i = \alpha \sum_{j } a_{ji}\frac{x_j}{L(j)} + \frac{1-\alpha}{N},</math> − − 1-alpha { n } ，</math > − − − − where − − where − − <math>L(j) = \sum_{i} a_{ji}</math> − − [ math > l (j) = sum { i } a { ji } </math > − − − − is the number of neighbors of node <math>j</math> (or number of outbound links in a directed graph). Compared to eigenvector centrality and Katz centrality, one major difference is the scaling factor <math>L(j)</math>. Another difference between PageRank and eigenvector centrality is that the PageRank vector is a left hand eigenvector (note the factor <math>a_{ji}</math> has indices reversed).<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> − − is the number of neighbors of node <math>j</math> (or number of outbound links in a directed graph). Compared to eigenvector centrality and Katz centrality, one major difference is the scaling factor <math>L(j)</math>. Another difference between PageRank and eigenvector centrality is that the PageRank vector is a left hand eigenvector (note the factor <math>a_{ji}</math> has indices reversed). − − 是节点 < math > j </math > (或有向图中出站链接的数量)的相邻节点数量。与特征向量中心性和卡兹中心性相比，尺度因子 < math > l (j) </math > 是一个主要的区别。网页排名中心性和特征向量中心性的另一个区别是网页排名中心性向量是一个左手特征向量(注意因子 < 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> − − − ==Percolation centrality== − =='''<font color="#ff8000"> 渗滤中心性 Percolation centrality</font>'''== − 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. − 在复杂网络中，存在大量的中心性度量来确定单个节点的“重要性”。然而，这些度量单纯从拓扑学的角度来量化节点的重要性，节点的值并不以任何方式依赖于节点的状态。不管网络动态如何，它都保持不变。即使对于加权的两者之间的度量也是如此。然而，一个节点可能很好地位于中介中心性或其他中心性度量的中心位置，但可能不是位于有渗滤的网络的上下文中的中心位置。在许多情况下，复杂网络中都会出现“传染”的渗滤现象。例如，病毒或细菌感染可以通过人们的社交网络传播，也就是所谓的接触网络。还可以在更高的抽象层次上考虑疾病的传播问题，设想通过公路、铁路或空中连接起来的城镇或人口中心网络。计算机病毒可以通过计算机网络传播。关于商业活动和交易的谣言或新闻也可以通过人们的社交网络传播。在所有这些情况下，一种“传染病”在一个复杂网络的链接上传播，随着它的传播，无论是可恢复的还是不可恢复的，都会改变节点的“状态”。例如，在流行病学方案中，随着感染扩散，个人从”易感”状态转变为”受感染”状态。在上面的例子中，随着传染的扩散，每个节点可以采取的状态可以是二进制的(例如接收/没有接收到一条新闻)、离散的(易感/受感染/康复) ，甚至是连续的(例如一个城镇中受感染的人的比例) 。这些情景的共同特点是，传染的扩散导致网络中节点状态的改变。'''<font color="#ff8000"> 渗滤中心性 Percolation centrality</font>'''（PC)就是基于这个思想而提出的，它特别地度量了节点在协助网络渗滤方面的重要性。这种度量是由皮拉维南 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''' 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. − − 渗滤中心性定义为在给定时间内一个给定节点的渗滤路径的比例。“渗滤路径”是一对节点之间的最短路径，其中源节点被渗滤(例如，被感染)。目标节点可以是渗滤的或非渗滤的，或处于部分渗滤状态。 + − <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> − + + − where <math>\sigma_{sr}</math> is total number of shortest paths from node <math>s</math> to node <math>r</math> and <math>\sigma_{sr}(v)</math> is the number of those paths that pass through <math>v</math>. The percolation state of the node <math>i</math> at time <math>t</math> is denoted by <math>{x^t}_i</math> and two special cases are when <math>{x^t}_i=0</math> which indicates a non-percolated state at time <math>t</math> whereas when <math>{x^t}_i=1</math> which indicates a fully percolated state at time <math>t</math>. The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town). − where <math>\sigma_{sr}</math> is total number of shortest paths from node <math>s</math> to node <math>r</math> and <math>\sigma_{sr}(v)</math> is the number of those paths that pass through <math>v</math>. The percolation state of the node <math>i</math> at time <math>t</math> is denoted by <math>{x^t}_i</math> and two special cases are when <math>{x^t}_i=0</math> which indicates a non-percolated state at time <math>t</math> whereas when <math>{x^t}_i=1</math> which indicates a fully percolated state at time <math>t</math>. The values in between indicate partially percolated states ( e.g., in a network of townships, this would be the percentage of people infected in that town).+ − 其中 < math > σ { 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 </math > i = 1 </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 [[Big O notation|<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 [[Big O notation|<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 > 时间，高效的实现采用了布兰德斯快速算法，如果计算需要考虑目标节点的权重，最坏情况下时间为 < math > o (n ^ 3) </math > 。 − − ==Cross-clique centrality== − =='''<font color="#ff8000">跨团中心性 Cross-clique centrality</font>'''== − '''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 cliques. 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 but was first proposed by Everett and Borgatti in 1998 where they called it clique-overlap centrality. − − 复杂图中单个节点的跨团中心性决定了一个节点与不同团的连通性。具有高度跨团连通性的节点有利于信息或疾病在图中的传播。团是一种'''<font color="#ff8000"> 子图 Subgraphs</font>'''，团中的每个节点都与团中的其他节点相连。对于一个给定的图 g: = (v，e) </math > 与 < math > | v | </math > 顶点和 < math > | e | </math > 边的跨团连通性，定义为 < math > x (v) </math > x (v) </math > 其中 < math > x (v) </math > 是 < math > v </math > 所属的顶点团数。这个度量应用日久，<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>但是在1998年由埃弗莱特 Everett 和博加提 Borgatti 首次提出，他们称之为'''<font color="#ff8000"> 派系重叠中心性 Clique-overlap centrality</font>'''。 − − ==Freeman centralization== − =='''<font color="#ff8000"> 弗里曼中心度Freeman centralization</font>'''== − − The '''centralization''' of any network is a measure of how central its most central node is in relation to how central all the other nodes are.<ref name="Freeman1979">{{citation | journal = Social Networks | last1 = Freeman | first1 = Linton C. | year = 1979 | volume = 1 | issue = 3 | pages = 215–239 | title = centrality in social networks: Conceptual clarification | url = http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | doi = 10.1016/0378-8733(78)90021-7 | citeseerx = 10.1.1.227.9549 | access-date = 2014-07-31 | archive-url = https://web.archive.org/web/20160222033108/http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | archive-date = 2016-02-22 | url-status = dead }}</ref> Centralization measures then (a) calculate the sum in differences in centrality between the most central node in a network and all other nodes; and (b) divide this quantity by the theoretically largest such sum of differences in any network of the same size.<ref name="Freeman1979"/> Thus, every centrality measure can have its own centralization measure. Defined formally, if <math>C_x(p_i)</math> is any centrality measure of point <math>i</math>, if <math>C_x(p_*)</math> is the largest such measure in the network, and if: − − The centralization of any network is a measure of how central its most central node is in relation to how central all the other nodes are. Centralization measures then (a) calculate the sum in differences in centrality between the most central node in a network and all other nodes; and (b) divide this quantity by the theoretically largest such sum of differences in any network of the same size. Thus, every centrality measure can have its own centralization measure. Defined formally, if <math>C_x(p_i)</math> is any centrality measure of point <math>i</math>, if <math>C_x(p_*)</math> is the largest such measure in the network, and if: − − 任何网络的中心度都是衡量其最核心的节点相对于其他所有节点的集聚程度的标准。<ref name="Freeman1979">{{citation | journal = Social Networks | last1 = Freeman | first1 = Linton C. | year = 1979 | volume = 1 | issue = 3 | pages = 215–239 | title = centrality in social networks: Conceptual clarification | url = http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | doi = 10.1016/0378-8733(78)90021-7 | citeseerx = 10.1.1.227.9549 | access-date = 2014-07-31 | archive-url = https://web.archive.org/web/20160222033108/http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | archive-date = 2016-02-22 | url-status = dead }}</ref>中心度的度量方法是: (a)计算网络中最中心的节点与所有其他节点之间的中心性差异之和; (b)将这个数量除以理论上相同规模的任何网络中这种差异之和的最大值。<ref name="Freeman1979"/>因此，每个中心性度量都可以有自己的中心度度量。正式定义，如果 < math > c _ x (p _ i) </math > 是点 < math > i </math > 的中心性度量，如果 < math > c _ x (p _ *) </math > 是网络中最大的中心性度量，如果: + − <math>\max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i)</math> − < math > max sum { i = 1} ^ { n } c _ x (p _ *)-c _ x (p _ i) </math > + − − − − is the largest sum of differences in point centrality <math>C_x</math> for any graph with the same number of nodes, then the centralization of the network is:<ref name="Freeman1979"/> − − is the largest sum of differences in point centrality <math>C_x</math> for any graph with the same number of nodes, then the centralization of the network is: − − 是具有相同节点数的任何图的点中心性的最大差值之和，然后网络中心度是： − <math>C_x=\frac{\sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}{\max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}.</math> − < math > c _ x = frac { sum _ { i = 1} ^ { n } c _ x (p _ *)-c _ x (p _ i)}{ max sum _ { i = 1 ^ { n } c _ x (p _ *)-c _ x (p _ i)} . </math > − − == Dissimilarity based centrality measures == − − [[File:Srep17095-f1.jpg|thumbnail|In the illustrated network, green and red nodes are the most dissimilar because they do not share neighbors between them. So, the green one contributes more to the centrality of the red one than the gray ones, because the red one can access to the blue ones only through the green, and the gray nodes are redundant for the red one, because it can access directly to each gray node without any intermediary.]] − − In the illustrated network, green and red nodes are the most dissimilar because they do not share neighbors between them. So, the green one contributes more to the centrality of the red one than the gray ones, because the red one can access to the blue ones only through the green, and the gray nodes are redundant for the red one, because it can access directly to each gray node without any intermediary. − − In order to obtain better results in the ranking of the nodes of a given network, in <ref>{{Cite journal|title = Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|journal = Scientific Reports|date = 2015-11-25|pmc = 4658528|pmid = 26603652|volume = 5|doi = 10.1038/srep17095|first = A. J.|last = Alvarez-Socorro|first2 = G. C.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz|pages=17095|bibcode = 2015NatSR...517095A}}</ref> are used dissimilarity measures (specific to the theory of classification and data mining) to enrich the centrality measures in complex networks. This is illustrated with [[eigenvector centrality]], calculating the centrality of each node through the solution of the eigenvalue problem − − In order to obtain better results in the ranking of the nodes of a given network, in are used dissimilarity measures (specific to the theory of classification and data mining) to enrich the centrality measures in complex networks. This is illustrated with eigenvector centrality, calculating the centrality of each node through the solution of the eigenvalue problem − − 为了在给定网络节点的排序中获得更好的结果，<ref>{{Cite journal|title = Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|journal = Scientific Reports|date = 2015-11-25|pmc = 4658528|pmid = 26603652|volume = 5|doi = 10.1038/srep17095|first = A. J.|last = Alvarez-Socorro|first2 = G. C.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz|pages=17095|bibcode = 2015NatSR...517095A}}</ref>在复杂网络中使用了相异性度量(特定于分类和数据挖掘理论)来丰富中心性度量。用特征向量中心性来说明，通过求解特征值问题来计算每个节点的中心性。 + − <math>W\mathbf{c}=\lambda \mathbf{c}</math> − − 数学，数学 − − − − where <math>W_{ij}=A_{ij}D_{ij}</math> (coordinate-to-coordinate product) and <math>D_{ij}</math> is an arbitrary [[Matrix similarity|dissimilarity]] matrix, defined through a dissimilitary measure, e.g., [[Jaccard index|Jaccard]] dissimilarity given by − − where <math>W_{ij}=A_{ij}D_{ij}</math> (coordinate-to-coordinate product) and <math>D_{ij}</math> is an arbitrary dissimilarity matrix, defined through a dissimilitary measure, e.g., Jaccard dissimilarity given by − − 这里 < math > w { ij } = a { ij } d { ij } </math > (coordinate-to-coordinate product)和 < math > d { ij } </math > 是一个任意的不相似矩阵，通过一个相异性度量来定义，例如，杰卡德 Jaccard相异性由以下给出。 + − − <math>D_{ij}=1-\dfrac{|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}</math> − − 1-dfrac { | v ^ { + }(i) cap v ^ { + }(j) | }{ | v ^ { + }(i) cup v ^ { + }(j) | } </math > − − − − Where this measure permits us to quantify the topological contribution (which is why is called contribution centrality) of each node to the centrality of a given node, having more weight/relevance those nodes with greater dissimilarity, since these allow to the given node access to nodes that which themselves can not access directly. − − Where this measure permits us to quantify the topological contribution (which is why is called contribution centrality) of each node to the centrality of a given node, having more weight/relevance those nodes with greater dissimilarity, since these allow to the given node access to nodes that which themselves can not access directly. − − 这种度量允许我们量化每个节点对给定节点中心性的拓扑贡献(这就是为什么我们称之为贡献中心性) ，对那些相异性较大的节点有更多的权重/相关性，因为这些节点允许给定的节点访问那些它们自己不能直接访问的节点。 + − Is noteworthy that <math>W</math> is non-negative because <math>A</math> and <math>D</math> are non-negative matrices, so we can use the [[Perron–Frobenius theorem]] to ensure that the above problem has a unique solution for ''λ'' = ''λ<sub>max</sub>'' with '''c''' non-negative, allowing us to infer the centrality of each node in the network. Therefore, the centrality of the i-th node is − Is noteworthy that <math>W</math> is non-negative because <math>A</math> and <math>D</math> are non-negative matrices, so we can use the Perron–Frobenius theorem to ensure that the above problem has a unique solution for λ = λ<sub>max</sub> with c non-negative, allowing us to infer the centrality of each node in the network. Therefore, the centrality of the i-th node is+ − − 值得注意的是，< math > w </math > 是非负的，因为 < math > a </math > 和 < math > d </math > 都是非负矩阵，所以我们可以使用Perron–Frobenius定理来确保上述问题对于 c 非负的 = < sub > max </sub > 有唯一的解，这样我们就可以推断出网络中每个节点的中心性。因此，i-th 节点的中心性为 第794行：
第323行： − <math>c_i=\dfrac{1}{n}\sum_{j=1}^{n}W_{ij}c_{j}, \,\,\,\,\,\, j=1,\cdots,n</math> − 1{ n } sum { j = 1} ^ { n } w { ij } c { j } ，，，，，j = 1，cdots，n </math > + − − where <math>n</math> is the number of the nodes in the network. Several dissimilarity measures and networks were tested in <ref>{{Cite web|url = http://www.nature.com/article-assets/npg/srep/2015/151125/srep17095/extref/srep17095-s1.pdf|title = Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|date = |website = |publisher = Nature Publishing Group|last = Alvarez-Socorro|first = A.J.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz}}</ref> obtaining improved results in the studied cases. − − where <math>n</math> is the number of the nodes in the network. Several dissimilarity measures and networks were tested in obtaining improved results in the studied cases. − − 其中 < math > n </math > 是网络中的节点数。在所研究的案例中，为了获得改进的结果，测试了一些相异性度量和网络被测试。<ref>{{Cite web|url = http://www.nature.com/article-assets/npg/srep/2015/151125/srep17095/extref/srep17095-s1.pdf|title = Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|date = |website = |publisher = Nature Publishing Group|last = Alvarez-Socorro|first = A.J.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz}}</ref> − − ==Extensions== − Empirical and theoretical research have extended the concept of centrality in the context of static networks to dynamic centrality<ref>{{cite journal | last1 = Braha | first1 = D. | last2 = Bar-Yam | first2 = Y. | year = 2006 | title = From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks | url = | journal = Complexity | volume = 12 | issue = 2| pages = 59–63 | doi=10.1002/cplx.20156| arxiv = physics/0611295 | bibcode = 2006Cmplx..12b..59B }}</ref> in the context of time-dependent and temporal networks.<ref>{{cite journal | last1 = Hill | first1 = S.A. | last2 = Braha | first2 = D. | year = 2010 | title = Dynamic Model of Time-Dependent Complex Networks | url = | journal = Physical Review E | volume = 82 | issue = 4| page = 046105 | doi=10.1103/physreve.82.046105| pmid = 21230343 | arxiv = 0901.4407 | bibcode = 2010PhRvE..82d6105H }}</ref><ref>Gross, T. and Sayama, H. (Eds.). 2009. ''Adaptive Networks: Theory, Models and Applications.'' Springer.</ref><ref>Holme, P. and Saramäki, J. 2013. ''Temporal Networks.'' Springer.</ref> − − Empirical and theoretical research have extended the concept of centrality in the context of static networks to dynamic centrality in the context of time-dependent and temporal networks. − − − − − For generalizations to weighted networks, see Opsahl et al. (2010).<ref>{{cite journal | last1 = Opsahl | first1 = Tore | last2 = Agneessens | first2 = Filip | last3 = Skvoretz | first3 = John | title = Node centrality in weighted networks: Generalizing degree and shortest paths | doi = 10.1016/j.socnet.2010.03.006 | year = 2010 | pages = 245–251 | volume = 32 | journal = Social Networks | url = http://toreopsahl.com/2010/04/21/article-node-centrality-in-weighted-networks-generalizing-degree-and-shortest-paths/ | issue = 3 | access-date = 2010-04-23 | archive-url = https://web.archive.org/web/20180226080331/https://toreopsahl.com/2010/04/21/article-node-centrality-in-weighted-networks-generalizing-degree-and-shortest-paths/ | archive-date = 2018-02-26 | url-status = dead }}</ref> − − For generalizations to weighted networks, see Opsahl et al. (2010). − − − − The concept of centrality was extended to a group level as well. For example, '''group betweenness''' centrality shows the proportion of geodesics connecting pairs of non-group members that pass through the group.<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> − − The concept of centrality was extended to a group level as well. For example, group betweenness centrality shows the proportion of geodesics connecting pairs of non-group members that pass through the group. − + − ==又及==+ − + + − * [[Core–periphery structure]] − * [[Distance (graph theory)|Distance in graphs]]+ − *阿尔法中心性+ − *核心—外围结构 − *距离（图理论）图中的距离 − + − {{Reflist}} − − − − ==Further reading== − 拓展阅读 + + + + + + + − [[Category:Graph theory]]+ − − Category:Graph theory − − 分类: 图论 − − [[Category:Graph algorithms]] − − Category:Graph algorithms − − 分类: 图形算法 − + + − Category:Algebraic graph theory+ − 分类: 代数图论+ − + + + − Category:Networks+ + − 分类: 网络+ − [[Category:Network analysis]] − Category:Network analysis+ + + + + + − 分类: 网络分析 − [[Category:Network theory]] − Category:Network theory+ + + − 分类: 网络理论 − <noinclude>+ − <small>This page was moved from [[wikipedia:en:Centrality]]. Its edit history can be viewed at [[网络中心性/edithistory]]</small></noinclude> − + + + + + +
无编辑摘要
{{#seo:
|keywords=图论,中心性,节点
|description=衡量网络内最核心的节点相对于其他所有节点的集聚程度的标准。
}}
在[[图论]]和[[网络分析]]中，中心性 centrality 指标用于识别图中最重要的顶点。其应用包括在社交网络中识别出最有影响力的个人，在因特网或城市网络中识别出最为关键的基础设施节点，以及识别疾病的超级传播者。中心性的概念最初是在社交网络分析中发展起来的，许多用于衡量中心性的术语都反映出了它们的社会学起源。<ref name="NewmanNetworks">Newman, M.E.J. 2010. ''Networks: An Introduction.'' Oxford, UK: Oxford University Press.</ref>中心性不应与节点影响度相混淆，后者意在量化网络中每个节点的影响。
{{for|the statistical concept|Central tendency}}
==中心性指数的定义与特性==
{{Network Science}}
'''中心性指数 centrality indices'''是对“重要顶点的特征是什么？”这一问题的回答。这个回答是以图中顶点的实值函数的形式给出的，可根据产生的函数值排序以确定最为重要的节点。<ref name="Bonacich1987">{{cite journal |last1= Bonacich |first1= Phillip|year= 1987 |title= Power and Centrality: A Family of Measures | journal=American Journal of Sociology |volume= 92|issue= 5|pages= 1170–1182|doi=10.1086/228631 |url= }}<!--|accessdate=July 11, 2014--></ref><ref name="Borgatti2005">{{cite journal |last1= Borgatti |first1= Stephen P.|year= 2005 |title= Centrality and Network Flow |journal=Social Networks |volume= 27|issue= |pages= 55–71|doi=10.1016/j.socnet.2004.11.008 |url= |citeseerx= 10.1.1.387.419}}<!--|accessdate= July 11, 2014--></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">{{cite journal |author = 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.|title = Eigenvector centrality for characterization of protein allosteric pathways|journal = Proceedings of the National Academy of Sciences|volume = 115|number = 52|pages = E12201–E12208|year = 2018|doi = 10.1073/pnas.1810452115|pmid = 30530700|pmc = 6310864}}</ref>
“重要性”的含义十分广泛，因此导致了许多不同的中心性定义方式，我们可以将各种不同的定义方式划分为如下两类。
“重要性”的含义十分广泛，因此导致了许多不同的中心性定义方式，我们可以将各种不同的定义方式划分为如下两类。
"Importance" can be conceived in relation to a type of flow or transfer across the network. This allows centralities to be classified by the type of flow they consider important. "Importance" can alternatively be conceived as involvement in the cohesiveness of the network. This allows centralities to be classified based on how they measure cohesiveness.Both of these approaches divide centralities in distinct categories. A further conclusion is that a centrality which is appropriate for one category will often "get it wrong" when applied to a different category.
“重要性”可以被设想为与网络中的某种流动或传输有关。这允许根据重要的流动的类型对中心性进行分类。<ref name=Borgatti2005/> “重要性”也可以被设想为与网络的内聚力 cohesiveness有关。这允许根据内聚力的度量方式对中心性进行分类。<ref name="Borgatti2006">{{cite journal |last1= Borgatti |first1= Stephen P.|last2= Everett |first2= Martin G.|year= 2006 |title= A Graph-Theoretic Perspective on Centrality |journal=Social Networks |volume= 28|issue= 4|pages= 466–484|doi=10.1016/j.socnet.2005.11.005 |url= }}<!--|accessdate= July 11, 2014--></ref>这两种方法在不同类别中划分了中心性。进一步的结论是，适用于某一类别的中心性在应用于另一类别时往往会“出错”。<ref name=Borgatti2005/>
当根据内聚力方法对中心性进行分类时，很明显大多数中心性都将被划分于同一类别。起始于给定顶点的步数总和仅取决于步数的定义以及计数方式。这种分类方式的不足表现为它仅能较弱的描绘中心性特征，即按照一步步长（度中心性）到无穷步步长（特征向量中心性）的方式将中心性置于一种光谱状的分类中。<ref name=Bonacich1987/><ref name="Benzi2013">{{cite journal | last1=Benzi | first1=Michele | last2=Klymko| first2=Christine | year=2013 |title= A matrix analysis of different centrality measures |arxiv=1312.6722 | doi=10.1137/130950550 | volume=36 | issue=2 | journal=SIAM Journal on Matrix Analysis and Applications | pages=686–706}}</ref>观察到许多中心性共享这种家庭关系，这或许能解释这些指数之间的高阶相关性。
===网络流特征===
一个网络可以被看成是对某种物体流动的路径描述。这允许基于流动的类型和由中心性编码的路径类型进行表征。流可以基于传输，即每个不可分割的项目从一个节点到另一个节点，就像一个包裹从配送站传递到客户的房子。第二种情况是串行复制，在这种情况下，一个项目被复制以便源头和目标节点都拥有它。例如通过流言传播信息，信息以私有方式传播，并在流程结束时通知源节点和目标节点。最后一种情况是并行复制，即项目同时被复制到几个链接，就像无线电广播一次性向多个听众提供相同的信息。<ref name=Borgatti2005/>
一个网络可以被看成是对某种物体流动的路径描述。这允许基于流动的类型和由中心性编码的路径类型进行表征。流可以基于传输，即每个不可分割的项目从一个节点到另一个节点，就像一个包裹从配送站传递到客户的房子。第二种情况是串行复制，在这种情况下，一个项目被复制以便源头和目标节点都拥有它。例如通过流言传播信息，信息以私有方式传播，并在流程结束时通知源节点和目标节点。最后一种情况是并行复制，即项目同时被复制到几个链接，就像无线电广播一次性向多个听众提供相同的信息。<ref name=Borgatti2005/>
同样，路径类型可以被限定为测地线 geodesics（最短路径）、路径（对顶点的访问不超过一次）、小径（可以访问多次顶点，没有边被访问超过一次）或者步子（可以多次访问/穿过多次顶点和边）。
===行走结构特征===
可以从中心性的构造方式推导出另一种分类方法。这又分成了两个类。中心性可以是径向的，也可以是中间的。径向中心性计算从给定顶点开始/结束的步数。度中心性和特征向量中心性是径向中心性 Radial centralities的例子，计算长度为一或无穷大的步数。中间中心性 Medial centralities计算通过给定顶点的步数。典型的例子是Freeman的中介中心性 Betweenness centrality，即通过给定顶点的最短路径的数量。<ref name=Borgatti2006/>
同样地，计数可以记录行走的数量或长度。量是给定类型的总步数。上一段的三个例子就属于这一类。长度则给出从给定顶点到图中其余顶点的距离。Freeman的'''<font color="#ff8000"> 接近中心性Closeness centrality</font>'''，即从一个给定顶点到所有其他顶点的总测地线距离，是最著名的例子。<ref name=Borgatti2006/>请注意，这种分类独立于步行计数的类型（即：步行，小道，路径，测地线）。
Borgatti和Everett提出，这种类型为如何最好地比较中心性度量提供了见解。在这个2×2分类中，放在同一盒子中的中心性足够相似，可以做出合理的选择; 人们可以合理地比较哪个对于给定的应用更好。然而，不同盒子中的度量方法是截然不同的。只有在预先确定哪个类别更适用的情况下，对相对适应性的评估才会发生，这使得比较变得毫无意义。<ref name=Borgatti2006/>
===光谱上存在的径向量中心===
步行结构的特征表明，几乎所有广泛使用的中心性都是径向量的衡量。这得出结论顶点的中心性是与之相关联的顶点中心性的函数。中心性根据如何定义关联而不同。
步行结构的特征表明，几乎所有广泛使用的中心性都是径向量的衡量。这得出结论顶点的中心性是与之相关联的顶点中心性的函数。中心性根据如何定义关联而不同。
Bonacich指出，如果联想是根据行走来定义的，那么可以根据考虑的行走长度来定义一个中心性家族。<ref name="Bonacich1987"/>度中心性计算长度为1的行走，特征向量中心性计算长度为无穷大的行走。关联的其他定义也是合理的。 阿尔法中心性 Alpha centrality允许顶点有一个外部影响源。Estrada的子图中心性 Subgraph centrality提出只计算封闭路径（三角形、正方形等）。
这些度量方法的核心是这种现象：图中[[邻接矩阵]]的幂给出了由该幂给出的步长的数目。同样，矩阵指数也与给定步长的数目密切相关。邻接矩阵的初始转换允许对步行计数的类型进行不同的定义。无论采用哪种方法，顶点的中心性都可以表示为无穷和
:<math>\sum_{k=0}^\infty A_{R}^{k} \beta^k </math>
:<math>\sum_{k=0}^\infty A_{R}^{k} \beta^k </math>
矩阵幂或者
矩阵幂或者
:<math>\sum_{k=0}^\infty \frac{(A_R \beta)^k}{k!}</math>
:<math>\sum_{k=0}^\infty \frac{(A_R \beta)^k}{k!}</math>
矩阵指数，其中
矩阵指数，其中
*<math>k</math>为步长
*<math>A_R</math>是邻接矩阵的转秩
*<math>\beta</math>是保证收敛的折扣参数。
Bonacich的一系列度量并没有改变邻接矩阵。阿尔法中心性用它的解决方案替代了邻接矩阵。子图中心性用它的踪迹取代了邻接矩阵。一个令人吃惊的结论是，不管邻接矩阵最初的转变是什么，所有这些方法都有共同的限制行为。随着<math>\beta</math>系数趋近于零，指数收敛到度中心性。随着<math>\beta</math>系数接近其最大值，指数收敛到特征向量中心性。<ref name=Benzi2013/>
===博弈论中心性 Game-theoretic centrality===
上述大多数标准度量的共同特点是，它们通过只关注一个节点本身所扮演的角色来评估确定节点的重要性。然而, 在许多应用中，这种方法是不充分的，因为可能会发生协同作用
上述大多数标准度量的共同特点是，它们通过只关注一个节点本身所扮演的角色来评估确定节点的重要性。然而, 在许多应用中，这种方法是不充分的，因为可能会发生协同作用
如果将节点的功能分组考虑。
如果将节点的功能分组考虑。
[[File:Game-theoretic centrality.png|Example of game-theoretic centrality]]
[[File:Game-theoretic centrality.png|博弈论中心性的例子]]
例如，考虑阻止流行病的问题。看看上面的网络图像，我们应该给哪些节点接种疫苗？基于前面描述的度量，我们希望识别在疾病传播中最重要的节点。仅仅基于中心性的方法，即关注节点的个别特性，可能不是一个好主意。红色方块中的节点，单独不能阻止疾病的传播，但把它们作为一个群体来考虑，我们清楚地看到，如果疾病在节点 <math>v_1</math>、<math>v_4</math>和<math>v_5</math>中开始，它们就能阻止疾病的传播。博弈论中心性试图利用博弈论中的工具来研究所描述的问题和机会。本文提出的方法<ref>Michalak, Aadithya, Szczepański, Ravindran, & Jennings </ref>使用了 Shapley 值。由于 Shapley 值计算的时间复杂性，这一领域的大部分工作都集中在实现新的算法和方法，这些算法和方法依赖于网络的特殊拓扑结构或问题的特殊性质。这种方法可以将时间复杂度从指数级降低到多项式级。
同样，权限分配的解决方案<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|title=Assessing the Political Landscape: Structure, Cognition, and Power in Organizations|first=David|last=Krackhardt|authorlink=David Krackhardt|journal=Administrative Science Quarterly|volume=35|issue=2|date=June 1990|pages=342–369|doi=10.2307/2393394|jstor=2393394}}</ref>
中心性指标有两个重要的局限性，一个显而易见，另一个则不易察觉。显而易见的局限性是，对于一个应用最优的中心性对于另一个应用常常是次优的。事实上，如果不是这样，我们就不需要这么多不同的中心性。克拉克哈特风筝图为这一现象提供了一个例证，对于这个图，三个不同的中心性概念给出了最中心顶点的三种不同选择。<ref>{{cite journal|title=Assessing the Political Landscape: Structure, Cognition, and Power in Organizations|first=David|last=Krackhardt|authorlink=David Krackhardt|journal=Administrative Science Quarterly|volume=35|issue=2|date=June 1990|pages=342–369|doi=10.2307/2393394|jstor=2393394}}</ref>
更不易察觉的限制是通常会错误地认为顶点中心性表示顶点的相对重要性。中心性指数被明确地设计来产生一个指出最重要顶点的排名。<ref name=Bonacich1987/><ref name=Borgatti2005/>在刚才提到的限制下，他们做得很好。它们通常不用来度量节点的影响力。最近，网络物理学家已经开始开发点影响力度量 Node influence metrics来解决这个问题。
错误有两方面。首先，一个排名只根据顶点的重要性排序，它并不对节点重要性的不同水平进行量化区分。这可以通过将弗里曼中心度 Freeman centralization应用到中心性度量来缓解，这可以根据节点的中心度得分差异对节点的重要性提供一些见解。此外，弗里曼中心度使人们能够通过比较几个网络的最高中心度得分来比较它们。<ref name="Freeman1979"/>然而，这种方法在实践中很少见到。{{citation needed|reason=I've come across quite some theoretical studies that indicate otherwise. My suggestion is to remove this sentence, if reasonable citation is not provided.|date=September 2015}}
其次，用以(正确地)识别给定网络/应用中最重要顶点的特征并不一定适用于其余顶点。
其次，用以(正确地)识别给定网络/应用中最重要顶点的特征并不一定适用于其余顶点。
对于大多数其他网络节点，排名可能是没有意义的。<ref name="Lawyer2015" /><ref name="daSilva2012">{{cite journal | last1=da Silva|first1=Renato |last2=Viana|first2=Matheus|last3=da F. Costa |first3=Luciano| title=Predicting epidemic outbreak from individual features of the spreaders| journal=J. Stat. Mech.: Theory Exp. | year=2012|volume=2012|pages=P07005|number=7 | doi=10.1088/1742-5468/2012/07/p07005|arxiv=1202.0024|bibcode=2012JSMTE..07..005A}}</ref><ref name="Bauer2012">{{cite journal | last1=Bauer|first1=Frank | last2=Lizier|first2=Joseph|title=Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach| journal=Europhys Lett | year=2012| volume=99| pages=68007|number=6 | doi=10.1209/0295-5075/99/68007|arxiv=1203.0502|bibcode=2012EL.....9968007B}}</ref><ref name="Sikic2013">{{ cite journal| last1= Sikic| first1=Mile|last2=Lancic|first2=Alen|last3=Antulov-Fantulin|first3=Nino|last4=Stefanic|first4=Hrvoje| title = Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes? |journal = The European Physical Journal B |volume=86 |number=10 |pages=1–13 |year=2013 | doi=10.1140/epjb/e2013-31025-5|arxiv=1110.2558 | bibcode=2013EPJB...86..440S}}</ref>这就解释了为什么，例如，谷歌图片搜索只有前几个结果以合理的顺序出现。网页排名是一个非常不稳定的度量，在对跳转参数进行小的调整之后显示了频繁的秩逆转。<ref name="Ghoshal2011">{{cite journal | last1=Ghoshal | first1= G. | last2= Barabsi |first2= A L | title = Ranking stability and super-stable nodes in complex networks. | journal = Nat Commun | volume =2 | page = 394| year= 2011 | doi=10.1038/ncomms1396 | pmid= 21772265 | bibcode=2011NatCo...2..394G | doi-access= free }}</ref>
对于大多数其他网络节点，排名可能是没有意义的。<ref name="Lawyer2015" /><ref name="daSilva2012">{{cite journal | last1=da Silva|first1=Renato |last2=Viana|first2=Matheus|last3=da F. Costa |first3=Luciano| title=Predicting epidemic outbreak from individual features of the spreaders| journal=J. Stat. Mech.: Theory Exp. | year=2012|volume=2012|pages=P07005|number=7 | doi=10.1088/1742-5468/2012/07/p07005|arxiv=1202.0024|bibcode=2012JSMTE..07..005A}}</ref><ref name="Bauer2012">{{cite journal | last1=Bauer|first1=Frank | last2=Lizier|first2=Joseph|title=Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: A walk counting approach| journal=Europhys Lett | year=2012| volume=99| pages=68007|number=6 | doi=10.1209/0295-5075/99/68007|arxiv=1203.0502|bibcode=2012EL.....9968007B}}</ref><ref name="Sikic2013">{{ cite journal| last1= Sikic| first1=Mile|last2=Lancic|first2=Alen|last3=Antulov-Fantulin|first3=Nino|last4=Stefanic|first4=Hrvoje| title = Epidemic centrality -- is there an underestimated epidemic impact of network peripheral nodes? |journal = The European Physical Journal B |volume=86 |number=10 |pages=1–13 |year=2013 | doi=10.1140/epjb/e2013-31025-5|arxiv=1110.2558 | bibcode=2013EPJB...86..440S}}</ref>这就解释了为什么，例如，谷歌图片搜索只有前几个结果以合理的顺序出现。网页排名是一个非常不稳定的度量，在对跳转参数进行小的调整之后显示了频繁的秩逆转。<ref name="Ghoshal2011">{{cite journal | last1=Ghoshal | first1= G. | last2= Barabsi |first2= A L | title = Ranking stability and super-stable nodes in complex networks. | journal = Nat Commun | volume =2 | page = 394| year= 2011 | doi=10.1038/ncomms1396 | pmid= 21772265 | bibcode=2011NatCo...2..394G | doi-access= free }}</ref>
虽然中心性指数未能推广到网络的其他部分，乍看起来似乎是违反直觉的，但它直接遵循上述定义。
虽然中心性指数未能推广到网络的其他部分，乍看起来似乎是违反直觉的，但它直接遵循上述定义。
复杂网络具有异构的拓扑结构。如果最佳度量取决于最重要顶点的网络结构，对于这些顶点最优的度量对于网络的其余部分是次优的。<ref name="Lawyer2015">{{cite journal |last1= Lawyer |first1= Glenn |year= 2015 |title= Understanding the spreading power of all nodes in a network: a continuous-time perspective |journal=Sci Rep |volume=5|pages=8665|doi=10.1038/srep08665 |pmid=25727453 |pmc=4345333|arxiv=1405.6707|bibcode=2015NatSR...5E8665L}}</ref>
==度中心性 Degree centrality==
[[File:6 centrality measures.png|thumb|right|300px|同一幅图中的实例A）中介中心性，B）紧密中心性，C）特征向量中心性,D）度中心性，E）调和中心性，F）卡兹中心性]]
历史上第一个并且概念上最简单是度中心性，它定义为一个节点上事件的链接数量（即一个节点拥有的关系数量）。度可以解释为节点捕获的任何流经网络的东西（例如病毒或某些信息）的直接风险。在有向网络的情况下（关系有方向） ，我们通常定义两个独立的度中心性的度量，即 '''入度 Indegree'''和'''出度 Outdegree'''。因此，入度是指向该节点的关系数，出度是该节点指向其他节点的关系数。当关系与一些积极的方面如友谊或合作有关时，入度通常被解释为一种受欢迎的形式，而出度则被解释为一种合群的形式。
对于给定的图<math>G:=(V,E)</math>与<math>|V|</math>顶点和<math>|E|</math>边，顶点的度中心性定义为
:<math>C_D(v)= \deg(v)</math>
:<math>C_D(v)= \deg(v)</math>
计算一个图中所有节点的度中心性，在图的密集邻接矩阵表示中采用<math>\Theta(V^2)</math>，在边的稀疏矩阵表示中采用<math>\Theta(E)</math> 。
节点级中心性的定义可以扩展到整个图，在这种情况下，我们指的是图的中心度。<ref>Freeman, Linton C. "Centrality in social networks conceptual clarification." Social networks 1.3 (1979): 215–239.</ref>设<math>v*</math>为<math>G</math>中度中心性最高的节点。让<math>X:=(Y,Z)</math>是<math>|Y|</math>节点连接图，最大化下列数量(<math>y*</math> 是<math>X</math>中度最高的节点) :
:<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>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)]}{H}</math>
:<math>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)]}{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>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>
==紧密中心性 Closeness centrality==
在连通图中，节点的标准紧密中心性（或贴近性）是节点与图中所有其他节点之间最短路径的平均长度。因此，一个节点越是中心，它就越接近所有其他节点。
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|hdl=10338.dmlcz/101401|last1=Sabidussi|first1=G|hdl-access=free}}</ref> that is:
: <math>C(x)= \frac{1}{\sum_y d(y,x)}</math>
: <math>C(x)= \frac{1}{\sum_y d(y,x)}</math>
其中<math>d(y,x)</math>是顶点<math>x</math>和 <math>y</math>之间的距离。然而，当谈到紧密中心性时，人们通常会提到它的标准化形式，一般是以前的公式乘以<math>N-1</math>，其中<math>N</math> 是图中的节点数。这种调整允许比较不同大小图形的节点。
从所有其他节点或到所有其他节点的距离在[[无向图]]中是不相关的，但是在[[有向图]]中可能产生完全不同的结果(例如:一个网站可以从传出链接获得高的紧密中心性，而从传入链接获得低的紧密中心性）。
==调和中心性 Harmonic centrality==
在一个（不一定是连通的）图中，调和中心性反转了紧密中心性定义中的和互反运算:
: <math>H(x)= \sum_{y \neq x} \frac{1}{d(y,x)}</math>
: <math>H(x)= \sum_{y \neq x} \frac{1}{d(y,x)}</math>
其中<math>1 / d(y,x) = 0</math>如果没有来自<math>y</math>到<math>x</math>的路径 。调和中心性可以通过除以<math>N-1</math>来标准化，其中<math>N</math>是图中的节点数。
调和中心性是由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)以“有价值的中心性”之名独立提出的，<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>
==中介中心性 Betweenness centrality==
[[File:Graph betweenness.svg|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>的概念中，它是作为一种量化一个人对社交网络中其他人之间交流控制的度量被引入的，在两个随机选择的顶点之间随机选择的最短路径上出现概率高的顶点具有很高的中介性。
在一个图<math>G:=(V,E)</math>与<math>V</math>的顶点中介性计算如下:
#对于每一对顶点(''s'',''t'')，计算它们之间的最短路径。
#对于每对顶点(''s'',''t'') ，确定通过该顶点（这里是顶点 ''v''）的最短路径的分数。
#对所有顶点对(''s'',''t'')求这个分数的和。
更确切地说，中介性可以表示为:<ref name="brandes">{{cite journal |last1 = Brandes |first1 = Ulrik | year=2001 |title = A faster algorithm for betweenness centrality | journal = Journal of Mathematical Sociology| volume=25|issue = 2 | pages=163–177| url = http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2024 | accessdate = October 11, 2011| format = PDF | doi=10.1080/0022250x.2001.9990249|citeseerx = 10.1.1.11.2024 }}</ref>
:<math>C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}}</math>
:<math>C_B(v)= \sum_{s \neq v \neq t \in V}\frac{\sigma_{st}(v)}{\sigma_{st}}</math>
其中<math>\sigma_{st}</math>是从节点<math>s</math>到节点<math>t</math>的最短路径总数，<math>\sigma_{st}(v)</math>是通过<math>v</math>的路径数。中介性也许可以通过除以不包括V的顶点对的数目被规范化，对于有向图是<math>(n-1)(n-2)</math>，对于无向图是<math>(n-1)(n-2)/2</math>。例如，在一个无向星图中，中心顶点（包含在每个可能的最短路径中）的中介性为<math>(n-1)(n-2)/2</math> （1，如果标准化） ，而叶节点（包含在没有最短路径中）的中介性为0。
从计算的角度来看，图中所有顶点的中介中心性和紧密中心性都涉及到计算图中所有顶点对之间的最短路径，采用<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'==
特征向量中心性（也称为特征中心性）是对网络中节点影响的一种度量。它将相对得分分配给网络中的所有节点，这是基于这样一个概念: 连接得分高的节点比连接得分低的节点对得分贡献更大。<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==
对于一个给定的图<math>G:=(V,E)</math>与<math>|V|</math>的顶点数 让<math>A = (a_{v,t})</math>成为邻接矩阵。即，如果顶点<math>v</math>与<math>t</math>相连，而 <math>a_{v,t} = 0</math>不然。顶点<math>v</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>\mathbf{Ax} = {\lambda}\mathbf{x}</math>
:<math>\mathbf{Ax} = {\lambda}\mathbf{x}</math>
一般情况下，存在许多不同的特征值<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中的项可以是表示连接强度的实数，就像在[[随机矩阵]]中一样。
==卡兹中心性 Katz centrality==
卡兹中心性<ref>Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.</ref>是度中心性的推广。度中心性度量的是直接相邻节点的数量，卡兹中心性度量的是通过一条路径可以连接的所有节点的数量，而远处节点的贡献会受到削减。在数学上，它被定义为
卡兹中心性<ref>Katz, L. 1953. A New Status Index Derived from Sociometric Index. Psychometrika, 39–43.</ref>是度中心性的推广。度中心性度量的是直接相邻节点的数量，卡兹中心性度量的是通过一条路径可以连接的所有节点的数量，而远处节点的贡献会受到削减。在数学上，它被定义为
:<math>x_i = \sum_{k=1}^{\infin}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math>
:<math>x_i = \sum_{k=1}^{\infin}\sum_{j=1}^N \alpha^k (A^k)_{ji}</math>
其中<math>\alpha</math> 是<math>(0,1)</math> 中的衰减因子。
卡兹中心性可以看作是特征向量中心性的一种变体。卡兹中心性的另一种形式是
卡兹中心性可以看作是特征向量中心性的一种变体。卡兹中心性的另一种形式是
:<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>A</math>，邻接矩阵的最大特征值相关）是卡兹中心性的极限，当<math>\alpha</math>从下接近 <math>\tfrac{1}{\lambda}</math>>时 。
==网页排名中心性 PageRank centrality==
网页排名满足下面的等式
网页排名满足下面的等式
:<math>x_i = \alpha \sum_{j } a_{ji}\frac{x_j}{L(j)} + \frac{1-\alpha}{N},</math>
:<math>x_i = \alpha \sum_{j } a_{ji}\frac{x_j}{L(j)} + \frac{1-\alpha}{N},</math>
其中
其中
:<math>L(j) = \sum_{i} a_{ji}</math>
:<math>L(j) = \sum_{i} a_{ji}</math>
是节点<math>j</math>（或有向图中出站链接的数量）的相邻节点数量。与特征向量中心性和卡兹中心性相比，尺度因子<math>L(j)</math>是一个主要的区别。网页排名中心性和特征向量中心性的另一个区别是网页排名中心性向量是一个左手特征向量（注意因子<math>a_{ji}</math>具有相反的索引）。<ref>[http://scenic.princeton.edu/network20q/lectures/Q3_notes.pdf How does Google rank webpages?]20Q: About Networked Life</ref>
==渗滤中心性 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>
渗滤中心性定义为在给定时间内一个给定节点的渗滤路径的比例。“渗滤路径”是一对节点之间的最短路径，其中源节点被渗滤（例如，被感染）。目标节点可以是渗滤的或非渗滤的，或处于部分渗滤状态。
:<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 > PC ^ t (v) = frac {1}{ N-2} sum { s neq v neq r } frac { sigma { sr }(v)}{ sigma { sr }} frac { x ^ t }{ 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 > 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==
复杂图中单个节点的跨团中心性决定了一个节点与不同团的连通性。具有高度跨团连通性的节点有利于信息或疾病在图中的传播。团是一种子图 Subgraphs，团中的每个节点都与团中的其他节点相连。对于一个给定的图<math>G:=(V,E)</math>与<math>|V|</math>顶点和<math>|E|</math> 边的跨团连通性，定义为 <math>X(v)</math> 其中<math>X(v)</math>是<math>v</math>所属的顶点团数。这个度量应用日久，<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>但是在1998年由埃弗莱特 Everett 和博加提 Borgatti 首次提出，他们称之为'''派系重叠中心性 Clique-overlap centrality'''。
==弗里曼中心度 Freeman centralization==
任何网络的中心度都是衡量其最核心的节点相对于其他所有节点的集聚程度的标准。<ref name="Freeman1979">{{citation | journal = Social Networks | last1 = Freeman | first1 = Linton C. | year = 1979 | volume = 1 | issue = 3 | pages = 215–239 | title = centrality in social networks: Conceptual clarification | url = http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | doi = 10.1016/0378-8733(78)90021-7 | citeseerx = 10.1.1.227.9549 | access-date = 2014-07-31 | archive-url = https://web.archive.org/web/20160222033108/http://leonidzhukov.ru/hse/2013/socialnetworks/papers/freeman79-centrality.pdf | archive-date = 2016-02-22 | url-status = dead }}</ref>中心度的度量方法是: (a)计算网络中最中心的节点与所有其他节点之间的中心性差异之和; (b)将这个数量除以理论上相同规模的任何网络中这种差异之和的最大值。<ref name="Freeman1979"/>因此，每个中心性度量都可以有自己的中心度度量。正式定义，如果 <math>C_x(p_i)</math>是点<math>i</math>的中心性度量，如果<math>C_x(p_*)</math>是网络中最大的中心性度量，如果:
:<math>\max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i)</math>
:<math>\max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i)</math>
是具有相同节点数的任何图的点中心性<math>C_x</math>的最大差值之和，然后网络中心度是：<ref name="Freeman1979"/>
:<math>C_x=\frac{\sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}{\max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}.</math>
:<math>C_x=\frac{\sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}{\max \sum_{i=1}^{N} C_x(p_*)-C_x(p_i)}.</math>
==基于相异性的中心性度量==
==基于相异性的中心性度量==
在图示的网络中，绿色节点和红色节点最不相似，因为它们之间不共享相邻节点。因此，绿色的节点比灰色的节点对红色节点的中心性的贡献更大，因为红色的节点只能通过绿色访问蓝色的节点，而灰色的节点对于红色的节点是多余的，因为它可以直接访问每个灰色的节点，而不需要任何中介。
在图示的网络中，绿色节点和红色节点最不相似，因为它们之间不共享相邻节点。因此，绿色的节点比灰色的节点对红色节点的中心性的贡献更大，因为红色的节点只能通过绿色访问蓝色的节点，而灰色的节点对于红色的节点是多余的，因为它可以直接访问每个灰色的节点，而不需要任何中介。
为了在给定网络节点的排序中获得更好的结果，<ref>{{Cite journal|title = Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|journal = Scientific Reports|date = 2015-11-25|pmc = 4658528|pmid = 26603652|volume = 5|doi = 10.1038/srep17095|first = A. J.|last = Alvarez-Socorro|first2 = G. C.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz|pages=17095|bibcode = 2015NatSR...517095A}}</ref>在复杂网络中使用了相异性度量（特定于分类和数据挖掘理论）来丰富中心性度量。用特征向量中心性来说明，通过求解特征值问题来计算每个节点的中心性。
:<math>W\mathbf{c}=\lambda \mathbf{c}</math>
:<math>W\mathbf{c}=\lambda \mathbf{c}</math>
这里<math>W_{ij}=A_{ij}D_{ij}</math> (coordinate-to-coordinate product)和 <math>D_{ij}</math>是一个任意的不相似矩阵，通过一个相异性度量来定义，例如，Jaccard相异性由以下给出。
:<math>D_{ij}=1-\dfrac{|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}</math>
:<math>D_{ij}=1-\dfrac{|V^{+}(i)\cap V^{+}(j)|}{|V^{+}(i)\cup V^{+}(j)|}</math>
这种度量允许我们量化每个节点对给定节点中心性的拓扑贡献（这就是为什么我们称之为贡献中心性） ，对那些相异性较大的节点有更多的权重/相关性，因为这些节点允许给定的节点访问那些它们自己不能直接访问的节点。
值得注意的是，<math>W</math> 是非负的，因为 <math>a</math> 和 <math>d</math>都是非负矩阵，所以我们可以使用Perron–Frobenius定理来确保上述问题对于 c 非负的''λ'' = ''λ<sub>max</sub>'' 有唯一的解，这样我们就可以推断出网络中每个节点的中心性。因此，i-th 节点的中心性为
:<math>c_i=\dfrac{1}{n}\sum_{j=1}^{n}W_{ij}c_{j}, \,\,\,\,\,\, j=1,\cdots,n</math>
:<math>c_i=\dfrac{1}{n}\sum_{j=1}^{n}W_{ij}c_{j}, \,\,\,\,\,\, j=1,\cdots,n</math>
其中 <math> n </math> 是网络中的节点数。在所研究的案例中，为了获得改进的结果，测试了一些相异性度量和网络被测试。<ref>{{Cite web|url = http://www.nature.com/article-assets/npg/srep/2015/151125/srep17095/extref/srep17095-s1.pdf|title = Supplementary Information for Eigencentrality based on dissimilarity measures reveals central nodes in complex networks|date = |website = |publisher = Nature Publishing Group|last = Alvarez-Socorro|first = A.J.|last2 = Herrera-Almarza|first3 = L. A.|last3 = González-Díaz}}</ref>
==扩展==
==扩展==
经验和理论研究已经将静态网络中的中心性概念扩展到时间依赖网络和时间网络中的动态中心性。<ref>{{cite journal | last1 = Hill | first1 = S.A. | last2 = Braha | first2 = D. | year = 2010 | title = Dynamic Model of Time-Dependent Complex Networks | url = | journal = Physical Review E | volume = 82 | issue = 4| page = 046105 | doi=10.1103/physreve.82.046105| pmid = 21230343 | arxiv = 0901.4407 | bibcode = 2010PhRvE..82d6105H }}</ref><ref>Gross, T. and Sayama, H. (Eds.). 2009. ''Adaptive Networks: Theory, Models and Applications.'' Springer.</ref><ref>Holme, P. and Saramäki, J. 2013. ''Temporal Networks.'' Springer.</ref>
经验和理论研究已经将静态网络中的中心性概念扩展到时间依赖网络和时间网络中的动态中心性。<ref>{{cite journal | last1 = Hill | first1 = S.A. | last2 = Braha | first2 = D. | year = 2010 | title = Dynamic Model of Time-Dependent Complex Networks | url = | journal = Physical Review E | volume = 82 | issue = 4| page = 046105 | doi=10.1103/physreve.82.046105| pmid = 21230343 | arxiv = 0901.4407 | bibcode = 2010PhRvE..82d6105H }}</ref><ref>Gross, T. and Sayama, H. (Eds.). 2009. ''Adaptive Networks: Theory, Models and Applications.'' Springer.</ref><ref>Holme, P. and Saramäki, J. 2013. ''Temporal Networks.'' Springer.</ref>
对加权网络的推广，见 Opsahl 等人。(2010). <ref>{{cite journal | last1 = Opsahl | first1 = Tore | last2 = Agneessens | first2 = Filip | last3 = Skvoretz | first3 = John | title = Node centrality in weighted networks: Generalizing degree and shortest paths | doi = 10.1016/j.socnet.2010.03.006 | year = 2010 | pages = 245–251 | volume = 32 | journal = Social Networks | url = http://toreopsahl.com/2010/04/21/article-node-centrality-in-weighted-networks-generalizing-degree-and-shortest-paths/ | issue = 3 | access-date = 2010-04-23 | archive-url = https://web.archive.org/web/20180226080331/https://toreopsahl.com/2010/04/21/article-node-centrality-in-weighted-networks-generalizing-degree-and-shortest-paths/ | archive-date = 2018-02-26 | url-status = dead }}</ref>
对加权网络的推广，见 Opsahl 等人。(2010). <ref>{{cite journal | last1 = Opsahl | first1 = Tore | last2 = Agneessens | first2 = Filip | last3 = Skvoretz | first3 = John | title = Node centrality in weighted networks: Generalizing degree and shortest paths | doi = 10.1016/j.socnet.2010.03.006 | year = 2010 | pages = 245–251 | volume = 32 | journal = Social Networks | url = http://toreopsahl.com/2010/04/21/article-node-centrality-in-weighted-networks-generalizing-degree-and-shortest-paths/ | issue = 3 | access-date = 2010-04-23 | archive-url = https://web.archive.org/web/20180226080331/https://toreopsahl.com/2010/04/21/article-node-centrality-in-weighted-networks-generalizing-degree-and-shortest-paths/ | archive-date = 2018-02-26 | url-status = dead }}</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] {{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] {{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>
==See also==
==另见==
*[[阿尔法中心性]]
* [[Alpha centrality]]
*[[核心—外围结构]]
*[[距离（图论）]]
==参考文献==
{{Reflist}}
==Notes and references==
==拓展阅读==
* Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) ''Network Analysis: Methodological Foundations'', pp. 16–61, LNCS 3418, Springer-Verlag.
* Koschützki, D.; Lehmann, K. A.; Peeters, L.; Richter, S.; Tenfelde-Podehl, D. and Zlotowski, O. (2005) Centrality Indices. In Brandes, U. and Erlebach, T. (Eds.) ''Network Analysis: Methodological Foundations'', pp. 16–61, LNCS 3418, Springer-Verlag.
==编者推荐==
===书籍推荐===
[[File:图论导论.jpg|200px|thumb|right|《图论导论》封面]]
[[File:种群结果如何影响自然选择.jpeg|300px|thumb|right|[https://swarma.org/?p=1113 种群结构如何影响自然选择？图论对进化生物学的启发] ]]
[[File:图网络读书会.png|300px|thumb|right|[https://campus.swarma.org/course/1167 图网络读书会]]]
====《图论导论》====
Douglas B．West教授是伊利诺伊大学数学系的资深教授，长期从事图论理论和组合优化方面的研究工作，发表了100多篇论文。本书旨在介绍图论的基本概念、基本定理和算法，帮助读者理解并掌握图的结构和解决图论问题的技巧。另外，本书包含很多图论的新研究结果，并介绍了一些悬而未决的图论问题．证明与应用并举是本书的一个重要特点。
<br/>
[[Category:Algebraic graph theory]]
====[https://vdisk.weibo.com/s/dDPmAoC9qB694 《图论及其应用》]====
该书籍主要介绍了图论的基本知识、相关定理等，并对于不同图，给出实际应用，如与对集有关的人员分派问题、与Hamilton图有关的旅行售货员问题等，通俗易懂。
</br>
===集智文章推荐===
[[Category:Networks]]
*集智俱乐部：[https://swarma.org/?p=1113 种群结构如何影响自然选择？ | 图论对进化生物学的启发] ====
*集智斑图：[https://pattern.swarma.org/paper?id=d25fb568-16f8-11ea-91b3-0242ac1a0005 Graph theory in the information age 信息时代的图论] ====
*集智斑图：[https://pattern.swarma.org/paper?id=24dc7004-2808-11ea-a1e5-0242ac1a0007 Graph Theory and Metro Traffic Modelling 图论与地铁交通模型] ====
</br>
===课程推荐===
图神经网络是深度学习领域的前沿热点议题，尤其是图网络（GraphNetworks）提出以来，深度学习有了实现因果推理的潜力。为了持续追踪相关领域的前沿进展，集智俱乐部联合北师大系统科学学院张江课题组，组织了以图网络为主题的线上读书会，研讨最新论文，孕育研究思路。下面从图网络的不同方面进行了讨论交流。
*[https://campus.swarma.org/course/1169 图网络解决优化问题]'''
*[https://campus.swarma.org/course/1172 图网络中的对抗学习问题]'''
*[https://campus.swarma.org/course/1168 GNN 算法变体]'''
*[https://campus.swarma.org/course/1170 GNN算法应用]'''
*[https://campus.swarma.org/course/1167 图网络算法原理探究]'''
*[https://campus.swarma.org/course/1171 关系推断问题]'''
<br/>
----
本条目由[[用户:水流心不竞|水流心不竞]]翻译，[[用户:Bai|Bai]]审校，[[用户:薄荷|薄荷]]编辑，如有问题，欢迎在讨论页面进行讨论。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
[[Category:待整理页面]]
[[Category:图论]]
[[Category:图形算法]]
[[Category:代数图论]]
[[Category:网络]]
[[Category:网络分析]]
[[Category:网络理论]]