第126行: |
第126行: |
| | | |
| | | |
− | 历史上第一个概念上简单的中心性定义是点度中心性,定义为与节点直接相连的连边(例如,一个节点有的边的数目)。度可以理解为节点接触到在任何在网络中传播的事物(比如病毒或者信息)的可能性。在有向图中(连边具有方向性),我们经常定义两种不同的度中心测量:指向和指出。相应的,指向的定义为方向指向节点的连边数,指出的定义为节点指出方向的连边数。
| + | 历史上第一个概念上简单的中心性定义是点度中心性,定义为与节点直接相连的连边(例如,一个节点有的边的数目)。度可以理解为节点接触到在任何在网络中传播的事物(比如病毒或者信息)的 |
| + | [[File:six pictures.jpg|right|thumb 同2图的A)中间性中心,B)紧密性中心,C)特征向量中心,D)度中心,E)谐波中心和F)Katz中心的示例。 |
| + | |图2]] |
| + | 可能性。在有向图中(连边具有方向性),我们经常定义两种不同的度中心测量:指向和指出。相应的,指向的定义为方向指向节点的连边数,指出的定义为节点指出方向的连边数。 |
| 当连边与友谊或者合作相关时,指向的度中心常被解释为赶潮流,指出被解释为交际。对于有<math>|V|</math>个节点<math>|E|</math>条边的图<math>G:=(V,E)</math>,节点<math>v</math>的度中心定义为, | | 当连边与友谊或者合作相关时,指向的度中心常被解释为赶潮流,指出被解释为交际。对于有<math>|V|</math>个节点<math>|E|</math>条边的图<math>G:=(V,E)</math>,节点<math>v</math>的度中心定义为, |
| + | |
| | | |
| :<math>{\displaystyle C_{D(v)}= \deg(v)}</math> | | :<math>{\displaystyle C_{D(v)}= \deg(v)}</math> |
− |
| |
− |
| |
| 计算图中所有节点的度中心,在密邻接矩阵表象中需要 big theta|:<math>\Theta(V^2)</math>, 在稀疏矩阵表象中,连边需要<math>\Theta(E)</math> 。 | | 计算图中所有节点的度中心,在密邻接矩阵表象中需要 big theta|:<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>中心度最大的点): | | <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>G</math>的度中心如下: |
| | | |
| | | |
| :<math>{\displaystyle C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v{^*})-C_D(v_i)]}{H}}</math> | | :<math>{\displaystyle C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v{^*})-C_D(v_i)]}{H}}</math> |
| + | 当图 |
| | | |
| + | :<math>X</math>包含一个与其他节点都相连的中心点 (星图)时 <math>H</math>的值最大, 此时 |
| | | |
− | 当图:<math>X</math>包含一个与其他节点都相连的中心点 (星图)时 <math>H</math>的值最大, 此时
| |
| | | |
| :<math>H=(n-1)\cdot((n-1)-1)=n^2-3n+2.</math> | | :<math>H=(n-1)\cdot((n-1)-1)=n^2-3n+2.</math> |
| + | 所以对于任意图 :<math>{\displaystyle G:=(V,E)}</math>, |
| | | |
− |
| |
− | 所以对于任意图 :<math>{\displaystyle G:=(V,E)}</math>,
| |
| | | |
| :<math>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2}</math> | | :<math>C_D(G)= \frac{\sum^{|V|}_{i=1} [C_D(v*)-C_D(v_i)] }{|V|^2-3|V|+2}</math> |