Main Content

本页翻译不是最新的。点击此处可查看最新英文版本。

centrality

衡量节点的重要性

说明

示例

C = centrality(G,type) 为图中的每个节点计算由 type 指定的节点中心性。

示例

C = centrality(___,Name,Value) 使用一个或多个名称-值对组参数指定的其他选项。例如,centrality(G,'closeness','Cost',c) 指定遍历每条边的成本。

示例

全部折叠

创建并绘制一个包含六个虚拟网站的图。

s = [1 1 2 2 3 3 3 4 5];
t = [2 5 3 4 4 5 6 1 1];
names = {'http://www.example.com/alpha', 'http://www.example.com/beta', ...
         'http://www.example.com/gamma', 'http://www.example.com/delta', ...
         'http://www.example.com/epsilon', 'http://www.example.com/zeta'};
G = digraph(s,t,[],names);
plot(G,'NodeLabel',{'alpha','beta','gamma','delta','epsilon','zeta'})

Figure contains an axes object. The axes object contains an object of type graphplot.

使用 centrality 函数计算每个网站的网页排名。将此信息作为图节点的一个属性追加到图的 Nodes 表中。

pg_ranks = centrality(G,'pagerank')
pg_ranks = 6×1

    0.3210
    0.1706
    0.1066
    0.1368
    0.2008
    0.0643

G.Nodes.PageRank = pg_ranks;
G.Nodes
ans=6×2 table
                   Name                   PageRank
    __________________________________    ________

    {'http://www.example.com/alpha'  }    0.32098 
    {'http://www.example.com/beta'   }    0.17057 
    {'http://www.example.com/gamma'  }    0.10657 
    {'http://www.example.com/delta'  }    0.13678 
    {'http://www.example.com/epsilon'}    0.20078 
    {'http://www.example.com/zeta'   }    0.06432 

还可以使用 centrality 确定哪些节点是枢纽节点和权威节点,并将得分追加到 Nodes 表中。

hub_ranks = centrality(G,'hubs');
auth_ranks = centrality(G,'authorities');
G.Nodes.Hubs = hub_ranks;
G.Nodes.Authorities = auth_ranks;
G.Nodes
ans=6×4 table
                   Name                   PageRank       Hubs       Authorities
    __________________________________    ________    __________    ___________

    {'http://www.example.com/alpha'  }    0.32098        0.24995    7.3237e-05 
    {'http://www.example.com/beta'   }    0.17057        0.24995      0.099993 
    {'http://www.example.com/gamma'  }    0.10657        0.49991      0.099993 
    {'http://www.example.com/delta'  }    0.13678     9.1536e-05       0.29998 
    {'http://www.example.com/epsilon'}    0.20078     9.1536e-05       0.29998 
    {'http://www.example.com/zeta'   }    0.06432              0       0.19999 

使用随机稀疏邻接矩阵创建并绘制一个加权图。由于有很多边,请使用非常小的 EdgeAlpha 值使边几乎透明。

A = sprand(1000,1000,0.15);
A = A + A';
G = graph(A,'omitselfloops');
p = plot(G,'Layout','force','EdgeAlpha',0.005,'NodeColor','r');

Figure contains an axes object. The axes object contains an object of type graphplot.

计算每个节点的度中心性。使用边权重指定每条边的重要性。

deg_ranks = centrality(G,'degree','Importance',G.Edges.Weight);

根据节点的中心性得分,使用 discretize 将节点放入 7 个等间距 bin 中。

edges = linspace(min(deg_ranks),max(deg_ranks),7);
bins = discretize(deg_ranks,edges);

使每个节点在绘图中的大小与其中心性得分成正比。每个节点的标记大小等于 bin 编号 (1-7)。

p.MarkerSize = bins;

Figure contains an axes object. The axes object contains an object of type graphplot.

加载 minnesota.mat 中的数据,其中包含代表明尼苏达州道路网络的图对象 G。图节点具有 xy 坐标,这些坐标包含在 G.Nodes 表的 XCoordYCoord 变量中。

load minnesota.mat
xy = [G.Nodes.XCoord G.Nodes.YCoord];

在图中添加与道路长度(使用每条边的端节点的 xy 坐标之间的欧几里德距离计算得出)大致对应的边权重。

[s,t] = findedge(G);
G.Edges.Weight = hypot(xy(s,1)-xy(t,1), xy(s,2)-xy(t,2));

使用节点的 xy 坐标绘图。

p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'MarkerSize',5);
title('Minnesota Road Network')

Figure contains an axes object. The axes object with title Minnesota Road Network contains an object of type graphplot.

计算每个节点的接近中心性。调整节点颜色 NodeCData,使其与中心性得分成正比。

ucc = centrality(G,'closeness');
p.NodeCData = ucc;
colormap jet
colorbar
title('Closeness Centrality Scores - Unweighted')

Figure contains an axes object. The axes object with title Closeness Centrality Scores - Unweighted contains an object of type graphplot.

还要计算加权的接近中心性得分(使用边权重作为遍历每条边的成本)。使用道路长度作为边权重可以提高得分质量,因为距离现在等于遍历的所有边的长度总和,而不是遍历的边数。

wcc = centrality(G,'closeness','Cost',G.Edges.Weight);
p.NodeCData = wcc;
title('Closeness Centrality Scores - Weighted')

Figure contains an axes object. The axes object with title Closeness Centrality Scores - Weighted contains an object of type graphplot.

计算图的加权中间中心性得分,以确定在两个节点之间的最短路径上出现频率最高的道路。使用因子 (n-2)(n-1)2 对中心性得分进行归一化,以使得分表示旅行者沿两个随机节点之间的最短路径经过给定节点的概率。该绘图表明进出这座城市有几条非常重要的道路。

wbc = centrality(G,'betweenness','Cost',G.Edges.Weight);
n = numnodes(G);
p.NodeCData = 2*wbc./((n-2)*(n-1));
colormap(flip(autumn,1));
title('Betweenness Centrality Scores - Weighted')

Figure contains an axes object. The axes object with title Betweenness Centrality Scores - Weighted contains an object of type graphplot.

输入参数

全部折叠

输入图,指定为 graphdigraph 对象。可使用 graph 创建一个无向图,或使用 digraph 创建一个有向图。

示例: G = graph(1,2)

示例: G = digraph([1 2],[2 3])

节点中心性的类型,指定为下表中的选项之一。表中还列出了适用于每个类型的兼容的名称-值参数。每个节点中心性变体为衡量节点在图中的重要性提供了一种不同的方法。

选项

图类型

描述

名称-值参数

'degree'

无向

'degree''outdegree''indegree' 中心性类型基于每个节点连接的边数:

  • 'degree' - 每个节点连接的边数。一个自环记为与节点连接的两条边。

  • 'indegree' - 每个节点的入向边数。一个自环记为一条入向边。

  • 'outdegree' - 每个节点的出向边数。一个自环记为一条出向边。

如果指定 'Importance' 边权重,则算法使用边权重之和,而不是连接边的条数。

'Importance'

'indegree'

'outdegree'

有向

'closeness'

无向

'closeness''incloseness''outcloseness' 中心性类型使用图中从一个节点到其他所有节点的距离的总和的倒数。如果并非所有节点都可达,则节点 i 的中心性为:

c(i)=(AiN1)21Ci.

Ai 是可从节点 i 到达的节点数(不计 i),N 是 G 中的节点数,Ci 是从节点 i 到所有可到达节点之间的距离之和。

  • 如果从节点 i 不能到达任何节点,则 c(i) 为零。

  • 对于 'incloseness',距离测量值是从所有节点到节点 i

  • 'Cost' 边权重指定边的长度。

'Cost'

'incloseness'

'outcloseness'

有向

'betweenness'

无向或有向

'betweenness' 中心性类型衡量每个图节点出现在图中两个节点之间的最短路径上的频率。由于两个图节点 st 之间可能存在多个最短路径,因此节点 u 的中心性为:

c(u)=s,tunst(u)Nst.

nst(u) 是从 st 且穿过节点 u 的最短路径数,Nst 是从 st 的最短路径总数。

  • 如果是无向图,则从 st 与从 ts 的路径只记为一条路径(将公式除以 2)。

  • 'Cost' 边权重指定边的长度,帮助确定节点 st 之间的最短路径。

'Cost'

'pagerank'

无向或有向

'pagerank' 中心性类型来自网络的随机游走。在图中的每个节点处,按照概率 'FollowProbability' 从当前节点的后继节点集(无向图中的相邻节点)中选择下一个节点。否则,当一个节点没有后继节点时,将从所有节点中选择下一个节点。中心性得分是指随机游走期间在每个节点上花费的平均时间。

  • 如果某个节点存在自环,则算法可能会遍历该循环。因此,自环会增加所连接节点的 PageRank 中心性得分。

  • 在相同的两个节点之间具有多条边的多重图中,具有多条边的节点被选择的可能性更大。

  • 'Importance' 边权重影响算法选择后继节点的方式。重要性越高的节点,被选择的可能性越大。

'Importance'

'FollowProbability'

'Tolerance'

'MaxIterations'

'eigenvector'

无向

'eigenvector' 中心性类型使用与图邻接矩阵的最大特征值对应的特征向量。得分经过归一化,因此所有中心性得分的总和等于 1。

  • 如果有多个未连通分量,算法将分别计算每个分量的特征向量中心性,然后根据图节点在该分量中的百分比来折算分数。

  • 未连接节点的中心性得分为 1/numnodes(G)

  • 指定 'Importance' 边权重以在计算时使用加权的邻接矩阵。

'Importance'

'Tolerance'

'MaxIterations'

'hubs'

'authorities'

有向

'hubs''authorities' 中心性得分是两个链接的递归中心性测量值。一个节点的枢纽得分是其所有后继节点的权威得分之和。同样,权威得分是其所有前趋节点的枢纽得分之和。所有枢纽得分之和等于 1,所有权威得分之和也等于 1。

  • 这些得分可理解为与邻接矩阵的最大奇异值对应的左侧(枢纽)和右侧(权威)奇异向量。

  • 未连接节点的中心性得分为 1/numnodes(G)

  • 指定 'Importance' 边权重以使用加权和,而不是将所有后继/前趋节点的得分简单相加。这相当于使用加权的邻接矩阵的奇异向量。

  • 如果有多个未连通分量(在弱连通意义上),该算法将分别计算每个分量的枢纽得分和权威得分。然后根据图节点在该分量中的百分比来折算分数,从而使总和依然为 1。

'Importance'

'Tolerance'

'MaxIterations'

注意

centrality 函数假定所有边权重都等于 1。要更改此设置,请指定边权重与 'Cost''Importance' 名称-值对组一起使用。

示例: centrality(G,'degree')

示例: centrality(G,'hubs','Tolerance',tol)

名称-值参数

将可选的参数对组指定为 Name1=Value1,...,NameN=ValueN,其中 Name 是参数名称,Value 是对应的值。名称-值参数必须出现在其他参数之后,但参数对组的顺序无关紧要。

在 R2021a 之前,使用逗号分隔每个名称和值,并用引号将 Name 引起来。

示例: C = centrality(G,'closeness','Cost',edgeCosts) 使用 edgeCosts 作为遍历图中每条边的成本(权重)来计算接近中心性。

遍历边的成本,以逗号分隔的对组形式指定,包含 'Cost' 和一个边权重向量。第 i 个边权重指定与遍历边 findedge(G,i) 相关的成本。

  • 对于 'closeness''outcloseness''incloseness' 中心性类型,边成本必须为非负值。

  • 对于 'betweenness' 中心性类型,边成本必须为正值。

连接越短、越快或者成本越低,'Cost' 边权重就越小。'Cost' 边权重的一些示例包括:

  • 旅程长度

  • 差旅时间

  • 机票成本

注意

'Cost' 仅适用于 'closeness''outcloseness''incloseness''betweenness' 中心性类型。

示例: centrality(G,'closeness','Cost',c)

选择后继节点的概率,以逗号分隔的对组形式指定,包含 'FollowProbability' 和一个介于 0 和 1 之间的标量。下面的概率是 PageRank 算法在遍历过程中从当前节点的后继节点中选择下一个节点的概率,而不是从所有节点中随机选择下一个节点的概率。对于网站,此概率指点击当前网页上的某个链接而不是浏览到另一个随机网页的概率。

注意

'FollowProbability' 仅适用于 'pagerank' 中心性类型。

示例: centrality(G,'pagerank','FollowProbability',0.5)

边的重要性,以逗号分隔的对组形式指定,包含 'Importance' 和一个非负的边权重向量。第 i 个边权重指定边 findedge(G,i) 的重要性。边权重为零相当于从图中删除这条边。

对于两个节点之间具有多条边的多重图,centrality 会将多条边相加,将它们视为具有合并权重的单条边。

连接越强,'Importance' 边权重越大。'Importance' 边权重的一些示例包括:

  • 每天的旅行人数

  • 链接的点击次数

  • 发表的论文总数

注意

'Importance' 仅适用于 'degree''outdegree''indegree''pagerank''eigenvector''hubs''authorities' 中心性类型。

示例: centrality(G,'degree','Importance',x)

最大迭代数,指定为以逗号分隔的对组,包含 'MaxIterations' 和一个标量。centrality 算法一直运行到满足容差或达到最大迭代次数为止,以先出现者为准。

注意

'MaxIterations' 仅适用于 'pagerank''eigenvector''hubs''authorities' 中心性类型。

示例: centrality(G,'pagerank','MaxIterations',250)

迭代求解器的停止条件,指定为以逗号分隔的对组,包含 'Tolerance' 和一个标量。centrality 算法一直运行到满足容差或达到最大迭代次数为止,以先出现者为准。

注意

'Tolerance' 仅适用于 'pagerank''eigenvector''hubs''authorities' 中心性类型。

示例: centrality(G,'pagerank','Tolerance',1e-5)

输出参数

全部折叠

节点中心性得分,以列向量形式返回。C(i) 是节点 i 的中心性得分。对节点中心性得分的解释取决于所选的中心性计算类型。节点距离中心越近,其中心性得分越高。

扩展功能

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2016a 中推出

另请参阅

|