centrality
Measure node importance
Description
uses additional options specified by one or more NameValue pair arguments. For
example, C
= centrality(___,Name,Value
)centrality(G,'closeness','Cost',c)
specifies the cost of
traversing each edge.
Examples
Page Rank of 6 Websites
Create and plot a graph containing six fictitious websites.
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'})
Calculate the page rank of each website using the centrality
function. Append this information to the Nodes
table of the graph as an attribute of the graph 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
Also determine which nodes are hubs and authorities using centrality
and append the scores to the Nodes
table.
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.3237e05
{'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.1536e05 0.29998
{'http://www.example.com/epsilon'} 0.20078 9.1536e05 0.29998
{'http://www.example.com/zeta' } 0.06432 0 0.19999
Degree Centrality of Random Graph
Create and plot a weighted graph using a random sparse adjacency matrix. Since there are a lot of edges, use a very small value for EdgeAlpha
to make the edges mostly transparent.
A = sprand(1000,1000,0.15); A = A + A'; G = graph(A,'omitselfloops'); p = plot(G,'Layout','force','EdgeAlpha',0.005,'NodeColor','r');
Calculate the degree centrality of each node. Specify the importance of each edge using the edge weights.
deg_ranks = centrality(G,'degree','Importance',G.Edges.Weight);
Use discretize
to place the nodes into 7 equallyspaced bins based on their centrality scores.
edges = linspace(min(deg_ranks),max(deg_ranks),7); bins = discretize(deg_ranks,edges);
Make the size of each node in the plot proportional to its centrality score. The marker size of each node is equal to the bin number (17).
p.MarkerSize = bins;
Closeness and Betweenness of Minnesota Roads
Load the data in minnesota.mat
, which contains a graph object G
representing the network of roads in Minnesota. The graph nodes have xy coordinates contained in the XCoord
and YCoord
variables of the G.Nodes
table.
load minnesota.mat
xy = [G.Nodes.XCoord G.Nodes.YCoord];
Add edge weights to the graph that roughly correspond to the length of the roads, calculated using the Euclidean distance between the xy coordinates of the end nodes of each edge.
[s,t] = findedge(G); G.Edges.Weight = hypot(xy(s,1)xy(t,1), xy(s,2)xy(t,2));
Plot the graph using the xy coordinates for the nodes.
p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'MarkerSize',5); title('Minnesota Road Network')
Compute the closeness centrality of each node. Scale the node color NodeCData
to be proportional to the centrality score.
ucc = centrality(G,'closeness'); p.NodeCData = ucc; colormap jet colorbar title('Closeness Centrality Scores  Unweighted')
Also compute the weighted closeness centrality score, using the edge weights as the cost of traversing each edge. Using the road lengths as edge weights improves the score quality, since distances are now measured as the sum of the lengths of all traveled edges, rather than the number of edges traveled.
wcc = centrality(G,'closeness','Cost',G.Edges.Weight); p.NodeCData = wcc; title('Closeness Centrality Scores  Weighted')
Compute the weighted betweenness centrality scores for the graph to determine the roads most often found on the shortest path between two nodes. Normalize the centrality scores with the factor $$\frac{(n2)(n1)}{2}$$ so that the score represents the probability that a traveler along a shortest path between two random nodes will travel through a given node. The plot indicates that there are a few very important roads leading into and out of the city.
wbc = centrality(G,'betweenness','Cost',G.Edges.Weight); n = numnodes(G); p.NodeCData = 2*wbc./((n2)*(n1)); colormap(flip(autumn,1)); title('Betweenness Centrality Scores  Weighted')
Input Arguments
type
— Type of node centrality
'degree'
 'outdegree'
 'indegree'
 'closeness'
 'incloseness'
 'outcloseness'
 'betweenness'
 'pagerank'
 'eigenvector'
 'hubs'
 'authorities'
Type of node centrality, specified as one of the options in the table. The table also lists the compatible namevalue arguments that work with each type. Each variety of node centrality offers a different measure of node importance in a graph.
Option 
Graph type 
Description  NameValue Arguments 


Undirected  The
If you specify  

Directed  

Undirected 
The $$c\left(i\right)={\left(\frac{{A}_{\text{\hspace{0.17em}}i}}{N1}\right)}^{2}\frac{1}{{C}_{i}}\text{\hspace{0.17em}}.$$ A_{i} is the
number of reachable nodes from node
 

Directed  

Undirected or Directed 
The $$c\left(u\right)={\displaystyle \sum _{s,t\ne u}\frac{{n}_{st}\left(u\right)}{{N}_{st}}}\text{\hspace{0.17em}}.$$ $${n}_{st}\left(u\right)$$ is the number of shortest paths from
 

Undirected or Directed  The
 

Undirected 
The
 

Directed 
The

Note
The centrality
function assumes all edge weights
are equal to 1. To change this, specify edge weights for use with the
'Cost'
or 'Importance'
namevalue pairs.
Example: centrality(G,'degree')
Example: centrality(G,'hubs','Tolerance',tol)
NameValue Arguments
Specify optional
commaseparated pairs of Name,Value
arguments. Name
is
the argument name and Value
is the corresponding value.
Name
must appear inside quotes. You can specify several name and value
pair arguments in any order as
Name1,Value1,...,NameN,ValueN
.
C = centrality(G,'closeness','Cost',edgeCosts)
computes
the closeness centrality using edgeCosts
as the cost (weight) of
traversing each edge in the graph.Cost
— Cost of edge traversal
vector
Cost of edge traversal, specified as the commaseparated pair
consisting of 'Cost'
and a vector of edge weights.
The ith edge weight specifies the cost associated with traversing the
edge findedge(G,i)
.
For the
'closeness'
,'outcloseness'
, and'incloseness'
centrality types, edge costs must be nonnegative.For the
'betweenness'
centrality type, edge costs must be positive.
'Cost'
edge weights are smaller when the connection
is shorter, or faster, or cheaper. Some examples of
'Cost'
edge weights are:
Length of a path
Travel time
Cost of a ticket
Note
'Cost'
only applies to the
'closeness'
,
'outcloseness'
,
'incloseness'
, and
'betweenness'
centrality types.
Example: centrality(G,'closeness','Cost',c)
FollowProbability
— Probability of selecting a successor node
0.85
(default)  scalar between 0 and 1
Probability of selecting a successor node, specified as the
commaseparated pair consisting of
'FollowProbability'
and a scalar between 0 and 1.
The follow probability is the probability that the next node selected in
the traversal by the pagerank algorithm is chosen among the successors
of the current node, and not at random from all nodes. For websites,
this probability corresponds to clicking a link on the current web page
instead of surfing to another random web page.
Note
'FollowProbability'
only applies to the
'pagerank'
centrality type.
Example: centrality(G,'pagerank','FollowProbability',0.5)
Importance
— Edge importance
vector
Edge importance, specified as the commaseparated pair consisting of
'Importance'
and a vector of nonnegative edge
weights. The ith edge weight specifies the importance of the edge
findedge(G,i)
. An edge weight of zero is
equivalent to removing that edge from the graph.
For multigraphs with multiple edges between two nodes,
centrality
adds the multiple edges together and
treats them as a single edge with the combined weight.
'Importance'
edge weights are larger when the
connection is stronger. Some examples of 'Importance'
edge weights are:
Number of travellers per day
Number of clicks on a link
Number of papers published together
Note
'Importance'
only applies to the
'degree'
, 'outdegree'
,
'indegree'
, 'pagerank'
,
'eigenvector'
, 'hubs'
, and
'authorities'
centrality types.
Example: centrality(G,'degree','Importance',x)
MaxIterations
— Maximum number of iterations
100
(default)  scalar
Maximum number of iterations, specified as the commaseparated pair
consisting of 'MaxIterations'
and a scalar. The
centrality
algorithm runs until the tolerance
is met or the maximum number of iterations is reached, whichever comes
first.
Note
'MaxIterations'
only applies to the
'pagerank'
, 'eigenvector'
,
'hubs'
, and 'authorities'
centrality types.
Example: centrality(G,'pagerank','MaxIterations',250)
Tolerance
— Stopping criterion for iterative solvers
1e4
(default)  scalar
Stopping criterion for iterative solvers, specified as the
commaseparated pair consisting of 'Tolerance'
and a
scalar. The centrality
algorithm runs until the
tolerance is met or the maximum number of iterations is reached,
whichever comes first.
Note
'Tolerance'
only applies to the
'pagerank'
, 'eigenvector'
,
'hubs'
, and 'authorities'
centrality types.
Example: centrality(G,'pagerank','Tolerance',1e5)
Output Arguments
C
— Node centrality scores
column vector
Node centrality scores, returned as a column vector.
C(i)
is the centrality score of node
i
. The interpretation of the node centrality score
depends on the type of centrality computation selected. The more central a
node is, the larger its centrality score.
Open Example
You have a modified version of this example. Do you want to open this example with your edits?
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
 América Latina (Español)
 Canada (English)
 United States (English)
Europe
 Belgium (English)
 Denmark (English)
 Deutschland (Deutsch)
 España (Español)
 Finland (English)
 France (Français)
 Ireland (English)
 Italia (Italiano)
 Luxembourg (English)
 Netherlands (English)
 Norway (English)
 Österreich (Deutsch)
 Portugal (English)
 Sweden (English)
 Switzerland
 United Kingdom (English)