Calculating betweenness centrality PDF

Preview

Summary

Download Calculating betweenness centrality PDF

Description

ECON2080/ECON8180 Economic Analysis of the Digital Economy (ANU) – S1 2019

Betweenness centrality – definition and calculation Betweenness centrality This measure indicates the extent to which an individual node plays a "brokering" or "bridging" role in a network and is calculated for a given node by summing up the proportion of all minimum paths within the network that "pass through" the node. The betweenness centrality of node v is:

C B (v)=

∑

s≠v≠t ∈V (G )

σ st (v ) σ st

where V (G) is the set of nodes in graph G, σ st is the total number of shortest paths between nodes s and t, and σ st (v) is the number of shortest paths between nodes s and t that pass through node v. The following are the steps for calculating betweenness centrality for a particular vertex: 1. Find the minimum path(s) between each pair of vertices (other than the one we are calculating betweenness centrality for). Note: it is possible for there to be more than one minimum path between two vertices. 2. For each pair of vertices, find the proportion of minimum paths that pass through the vertex in question. 3. Calculate the sum of the proportion over all pair of vertices. The following is an undirected star network with 5 nodes.

1

ECON2080/ECON8180 Economic Analysis of the Digital Economy (ANU) – S1 2019 Table 1: Calculating betweenness centrality for node A Pairs of vertices (A is excluded)

Step 1: Number of min. Step 2a: Number of paths between nodes in min. paths passing pair through A

Step 2b: Proportion passing through A

B, C

1

1

1

B, D

1

1

1

B, E

1

1

1

C,D

1

1

1

C, E

1

1

1

D, E

1

1

1 6

Step 3: Betweenness centrality for A

Note 1: To be sure that all pairs of vertices are listed, you can calculate the number of pairs that you need to list by using the formula for maximum possible number of ties in networks. For an undirected network of size N the maximum possible number of ties is N(N-1)/2. For a directed network of size N, the maximum possible number of ties is N(N-1). The network above is undirected and the network size is 5, but the number of pairs of nodes (not including node A) is the same as finding the maximum number of ties in a network of size 4 i.e. 4(4-1)/2 = 6. Note 2: Betweenness centrality is sometimes normalised by dividing it by the maximum possible betweenness for a network of this size (this is difficult to calculate, and we do not do it in this course). Another normalisation is to divide each betweenness centrality by the sum of all betweenness centrality scores. Table 2: Calculating betweenness centrality for node B Pairs of vertices (B is excluded)

Step 1: Number of min. Step 2a: Number of paths between nodes in min. paths passing through B pair

Step 2b: Proportion passing through B

A,C

1

0

0

A,D

1

0

0

A,E

1

0

0

C,D

1

0

0

C,E

1

0

0

D,E

1

0

0

Step 3: Betweenness centrality for B

0

2

ECON2080/ECON8180 Economic Analysis of the Digital Economy (ANU) – S1 2019 As another example, we compute betweenness centrality for node “C” in the following network.

Table 3: Calculating betweenness centrality for node C Pairs of vertices (C is excluded)

Step 1: Number of min. Step 2a: Number of paths between nodes in min. paths passing through C pair

Step 2b: Proportion passing through C

H,I

1

0

0

H,J

1

0

0

H,M

1

1

1

I,H

2

1

0.5

I,J

1

0

0

I,M

1

1

1

J,H

1

0

0

J,I

1

0

0

J,M

1

1

1

M,H

1

0

0

M,I

1

1

1

M,J

2

1

0.5

Step 3: Betweenness centrality for C

5

Note: this is a directed network with 5 nodes; the number of pairs of vertices is therefore equal to (5-1)*(5-2) = 12.

3

ECON2080/ECON8180 Economic Analysis of the Digital Economy (ANU) – S1 2019

Table 4: Calculating betweenness centrality for node J Pairs of vertices (J is excluded)

Step 1: Number of min. Step 2a: Number of paths between nodes in min. paths passing pair through J

Step 2b: Proportion passing through J

C,H

1

0

0

C,I

1

0

0

C,M

1

0

0

H,C

1

1

1

H,I

1

1

1

H,M

1

1

1

I,C

1

0

0

I,H

2

1

0.5

I,M

1

0

0

M,C

1

0

0

M,H

1

0

0

M,I

1

0

0

Step 3: Betweenness centrality for J

3.5

4...