Centrality Measures

Rishi Ranjan Singh

Department of Electrical Engineering & Computer Science
Indian Institute of Technology, Bhilai
[email protected]

February 4, 2020

Rishi Ranjan Singh Centrality Measures

Degree Centrality

Rishi Ranjan Singh Centrality Measures

Degree Centrality: Example

Rishi Ranjan Singh Centrality Measures

Degree Centrality: Example

Rishi Ranjan Singh Centrality Measures

Degree Centrality: Example

Rishi Ranjan Singh Centrality Measures

Degree Centrality: Example

Rishi Ranjan Singh Centrality Measures

Degree Centrality: Example

Rishi Ranjan Singh Centrality Measures

Degree Centrality: Example

Rishi Ranjan Singh Centrality Measures

Degree Centrality in Social Networks

Degree centrality �→ popularity

Higher degree node has many followers/friends �→ Higher

strength.

Lowest degree nodes are nearly isolated from the population

and are least popular

Shortcoming: Local measure

Rishi Ranjan Singh Centrality Measures

Degree Centrality in Social Networks

Degree centrality �→ popularity

Higher degree node has many followers/friends �→ Higher

strength.

Lowest degree nodes are nearly isolated from the population

and are least popular

Shortcoming: Local measure

Rishi Ranjan Singh Centrality Measures

Degree Centrality in Social Networks

Degree centrality �→ popularity

Higher degree node has many followers/friends �→ Higher

strength.

Lowest degree nodes are nearly isolated from the population

and are least popular

Shortcoming: Local measure

Rishi Ranjan Singh Centrality Measures

Degree Centrality in Social Networks

Degree centrality �→ popularity

Higher degree node has many followers/friends �→ Higher

strength.

Lowest degree nodes are nearly isolated from the population

and are least popular

Shortcoming: Local measure

Rishi Ranjan Singh Centrality Measures

Application: Degree Centrality

To hypothesize the amount of emotional support available to

a person.

To find influential people

Highly visible actors

Highly exposed nodes to a flowing infection/information

Rishi Ranjan Singh Centrality Measures

Closeness Centrality

Rishi Ranjan Singh Centrality Measures

Closeness Centrality

Introduced by Freeman in 197912 .

Called “Status” earlier by Harary in 195913 .
Node’s importance is inversely proportional to the sum of its
distance to other nodes.
Mathematically:
1
CC (u) = �
v ∈V \{u} duv

Normalized by multiplying with n − 1 i.e

n−1
CC (u) = � .
v ∈V \{u} duv

12
Centrality in social networks conceptual clarification. Social Networks, 1979
13
Status and contrastatus. Sociometry, 1959
Rishi Ranjan Singh Centrality Measures
Closeness Centrality

Introduced by Freeman in 197912 .

Called “Status” earlier by Harary in 195913 .
Node’s importance is inversely proportional to the sum of its
distance to other nodes.
Mathematically:
1
CC (u) = �
v ∈V \{u} duv

Normalized by multiplying with n − 1 i.e

n−1
CC (u) = � .
v ∈V \{u} duv

12
Centrality in social networks conceptual clarification. Social Networks, 1979
13
Status and contrastatus. Sociometry, 1959
Rishi Ranjan Singh Centrality Measures
Closeness Centrality

Introduced by Freeman in 197912 .

Called “Status” earlier by Harary in 195913 .
Node’s importance is inversely proportional to the sum of its
distance to other nodes.
Mathematically:
1
CC (u) = �
v ∈V \{u} duv

Normalized by multiplying with n − 1 i.e

n−1
CC (u) = � .
v ∈V \{u} duv

12
Centrality in social networks conceptual clarification. Social Networks, 1979
13
Status and contrastatus. Sociometry, 1959
Rishi Ranjan Singh Centrality Measures
Closeness Centrality

Introduced by Freeman in 197912 .

Called “Status” earlier by Harary in 195913 .
Node’s importance is inversely proportional to the sum of its
distance to other nodes.
Mathematically:
1
CC (u) = �
v ∈V \{u} duv

Normalized by multiplying with n − 1 i.e

n−1
CC (u) = � .
v ∈V \{u} duv

12
Centrality in social networks conceptual clarification. Social Networks, 1979
13
Status and contrastatus. Sociometry, 1959
Rishi Ranjan Singh Centrality Measures
Closeness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Closeness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Closeness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Closeness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Closeness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Closeness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Closeness Centrality : Some Key Points

Closeness centrality of u �→ the expected time for an

information originated at a random node to reach u or
vice-versa.

Higher closeness �→ Node gets updated earlier with an

information flowing in the network and vice-versa.

Does not work in disconnected networks.

Rishi Ranjan Singh Centrality Measures

Closeness Centrality : Some Key Points

Closeness centrality of u �→ the expected time for an

information originated at a random node to reach u or
vice-versa.

Higher closeness �→ Node gets updated earlier with an

information flowing in the network and vice-versa.

Does not work in disconnected networks.

Rishi Ranjan Singh Centrality Measures

Closeness Centrality : Some Key Points

Closeness centrality of u �→ the expected time for an

information originated at a random node to reach u or
vice-versa.

Higher closeness �→ Node gets updated earlier with an

information flowing in the network and vice-versa.

Does not work in disconnected networks.

Rishi Ranjan Singh Centrality Measures

Another measure like Closeness Centrality: Harmonic

Introduced by Opsahl et al. in 201014 and reused by Boldi et

al. in 201415 .
Node’s importance is proportional to the sum of inverse of its
distance to other nodes.
Mathematically:
1�
HC (u) =
d
v ∈V \{u} uv

Normalized by dividing with n − 1 i.e

1 �˙ 1
HC (u) =
n − 1 v ∈V \{u} duv

14
Node centrality in weighted networks: Generalizing degree and shortest paths, Social Networks, 2010.
15
Axioms for centrality, Internet Mathematics, 2014
Rishi Ranjan Singh Centrality Measures
Another measure like Closeness Centrality: Harmonic

Introduced by Opsahl et al. in 201014 and reused by Boldi et

al. in 201415 .
Node’s importance is proportional to the sum of inverse of its
distance to other nodes.
Mathematically:
1�
HC (u) =
d
v ∈V \{u} uv

Normalized by dividing with n − 1 i.e

1 �˙ 1
HC (u) =
n − 1 v ∈V \{u} duv

14
Node centrality in weighted networks: Generalizing degree and shortest paths, Social Networks, 2010.
15
Axioms for centrality, Internet Mathematics, 2014
Rishi Ranjan Singh Centrality Measures
Another measure like Closeness Centrality: Harmonic

Introduced by Opsahl et al. in 201014 and reused by Boldi et

al. in 201415 .
Node’s importance is proportional to the sum of inverse of its
distance to other nodes.
Mathematically:
1�
HC (u) =
d
v ∈V \{u} uv

Normalized by dividing with n − 1 i.e

1 �˙ 1
HC (u) =
n − 1 v ∈V \{u} duv

14
Node centrality in weighted networks: Generalizing degree and shortest paths, Social Networks, 2010.
15
Axioms for centrality, Internet Mathematics, 2014
Rishi Ranjan Singh Centrality Measures
Harmonic Centrality: Example

Rishi Ranjan Singh Centrality Measures

Harmonic Centrality: Example

Rishi Ranjan Singh Centrality Measures

Harmonic Centrality: Example

Rishi Ranjan Singh Centrality Measures

Harmonic Centrality: Example

Rishi Ranjan Singh Centrality Measures

Harmonic Centrality: Example

Rishi Ranjan Singh Centrality Measures

Harmonic Centrality: Example

Rishi Ranjan Singh Centrality Measures

Application: Closeness/Harmonic centrality

Nodes receiving information of higher fidelity on an average.

Nodes for installing facilities that needs to be used regularly

by the whole network.

Nodes prone to get exposed to infection/information quickly.

Rishi Ranjan Singh Centrality Measures

Eccentricity

Rishi Ranjan Singh Centrality Measures

Another measure based on geodesic: Eccentricity

Node’s importance is inversely proportional to the max of its

distance to other nodes.
Mathematically:
1
E (u) =
maxv ∈V \{u} duv

Already normalized.

Rishi Ranjan Singh Centrality Measures

Another measure based on geodesic: Eccentricity

Node’s importance is inversely proportional to the max of its

distance to other nodes.
Mathematically:
1
E (u) =
maxv ∈V \{u} duv

Already normalized.

Rishi Ranjan Singh Centrality Measures

Another measure based on geodesic: Eccentricity

Node’s importance is inversely proportional to the max of its

distance to other nodes.
Mathematically:
1
E (u) =
maxv ∈V \{u} duv

Already normalized.

Rishi Ranjan Singh Centrality Measures

Eccentricity: Example

Rishi Ranjan Singh Centrality Measures

Eccentricity: Example

Rishi Ranjan Singh Centrality Measures

Eccentricity: Example

Rishi Ranjan Singh Centrality Measures

Eccentricity: Example

Rishi Ranjan Singh Centrality Measures

Eccentricity: Example

Rishi Ranjan Singh Centrality Measures

Eccentricity: Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality

Rishi Ranjan Singh Centrality Measures

Betweenness concept in LAKSHYA Movie

Figure 11: (Source :- Lakhsya Movie)

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality

The idea of betweenness centrality was proposed by

Freeman16 .
Mathematical notation for betweenness centrality:
� σst (v )
BC (v ) =
s�=t�=v � V
σst

where σst is the number of shortest paths from vertex s to

vertex t and σst (v ) is the number of shortest paths between s
and t that pass through vertex v.
Normalized by dividing with (n − 1)(n − 2)/2 i.e

2 � σst (v )
BC (v ) =
(n − 1)(n − 2) s�=t�=v � V σst

16
Freeman, Linton, A set of measures of centrality based on betweenness, Sociometry, 1977.
Rishi Ranjan Singh Centrality Measures
Betweenness Centrality

The idea of betweenness centrality was proposed by

Freeman16 .
Mathematical notation for betweenness centrality:
� σst (v )
BC (v ) =
s�=t�=v � V
σst

where σst is the number of shortest paths from vertex s to

vertex t and σst (v ) is the number of shortest paths between s
and t that pass through vertex v.
Normalized by dividing with (n − 1)(n − 2)/2 i.e

2 � σst (v )
BC (v ) =
(n − 1)(n − 2) s�=t�=v � V σst

16
Freeman, Linton, A set of measures of centrality based on betweenness, Sociometry, 1977.
Rishi Ranjan Singh Centrality Measures
Betweenness Centrality

The idea of betweenness centrality was proposed by

Freeman16 .
Mathematical notation for betweenness centrality:
� σst (v )
BC (v ) =
s�=t�=v � V
σst

where σst is the number of shortest paths from vertex s to

vertex t and σst (v ) is the number of shortest paths between s
and t that pass through vertex v.
Normalized by dividing with (n − 1)(n − 2)/2 i.e

2 � σst (v )
BC (v ) =
(n − 1)(n − 2) s�=t�=v � V σst

16
Freeman, Linton, A set of measures of centrality based on betweenness, Sociometry, 1977.
Rishi Ranjan Singh Centrality Measures
Betweenness Centrality : Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality : Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality: Example

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality : Some Key Points

Betweenness centrality �→ Brokerage power, i.e. control over

the flow

Assumption: information is flowing through shortest paths

Higher betweenness �→ Control over major fraction of the flow

Higher betweenness �→ Higher load

Higher betweenness �→ Higher risk for an attack or failure

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality : Some Key Points

Betweenness centrality �→ Brokerage power, i.e. control over

the flow

Assumption: information is flowing through shortest paths

Higher betweenness �→ Control over major fraction of the flow

Higher betweenness �→ Higher load

Higher betweenness �→ Higher risk for an attack or failure

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality : Some Key Points

Betweenness centrality �→ Brokerage power, i.e. control over

the flow

Assumption: information is flowing through shortest paths

Higher betweenness �→ Control over major fraction of the flow

Higher betweenness �→ Higher load

Higher betweenness �→ Higher risk for an attack or failure

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality : Some Key Points

Betweenness centrality �→ Brokerage power, i.e. control over

the flow

Assumption: information is flowing through shortest paths

Higher betweenness �→ Control over major fraction of the flow

Higher betweenness �→ Higher load

Higher betweenness �→ Higher risk for an attack or failure

Rishi Ranjan Singh Centrality Measures

Betweenness Centrality : Some Key Points

Betweenness centrality �→ Brokerage power, i.e. control over

the flow

Assumption: information is flowing through shortest paths

Higher betweenness �→ Control over major fraction of the flow

Higher betweenness �→ Higher load

Higher betweenness �→ Higher risk for an attack or failure

Rishi Ranjan Singh Centrality Measures

Application: Betweenness centrality

Detecting communities
Identifying sensitive nodes in
Electronic communication system network
Public transit system network
Gas pipeline network
Waste-water disposal system network etc.
Used to identify crucial nodes for information flow in a brain
network

Rishi Ranjan Singh Centrality Measures

Centralization

Rishi Ranjan Singh Centrality Measures

Centralization

Star network is an idle example of fully centralized network.

Freeman defined centralization of any network G in case of a
centrality measure M as:
� � �
G
Mmax − M(v )
G v ∈V
CM = �
v ∈V (Mmax
S − M(v ))

where
G : Highest M-centrality value in G
Mmax
S : M-centrality value of the center in a star network with
Mmax
the same number of nodes.

Rishi Ranjan Singh Centrality Measures

Centralization

Star network is an idle example of fully centralized network.

Freeman defined centralization of any network G in case of a
centrality measure M as:
� � �
G
Mmax − M(v )
G v ∈V
CM = �
v ∈V (Mmax
S − M(v ))

where
G : Highest M-centrality value in G
Mmax
S : M-centrality value of the center in a star network with
Mmax
the same number of nodes.

Rishi Ranjan Singh Centrality Measures

Centralization: Example

(a) Centralization=0 (b) Centralization=1 (c) Centralization=0

Rishi Ranjan Singh Centrality Measures

Largest Centrality Values

Highest Centralization
Higest value
value

Degree n−1

1
Closeness n−1

Betweenness n2 −3n+2
2

Rishi Ranjan Singh Centrality Measures

Quiz

Questions adapted from a slide by James

Moody

Rishi Ranjan Singh Centrality Measures

Low Degree and High Closeness

Rishi Ranjan Singh Centrality Measures

Low Degree and High Closeness

Key player tied to important/active players

Rishi Ranjan Singh Centrality Measures

Low Degree and High Betweenness

Rishi Ranjan Singh Centrality Measures

Low Degree and High Betweenness

Node’s few ties are crucial for network flow

Rishi Ranjan Singh Centrality Measures

Low Closeness and High Degree

Rishi Ranjan Singh Centrality Measures

Low Closeness and High Degree

Embedded in cluster that is far from the rest

of the network

Rishi Ranjan Singh Centrality Measures

Low Closeness and High Betweenness

Rishi Ranjan Singh Centrality Measures

Low Closeness and High Betweenness

Very rare cell. Would mean that the node

monopolizes the ties from a small number of
people to many others.

Rishi Ranjan Singh Centrality Measures

Low Betweenness and High Degree

Rishi Ranjan Singh Centrality Measures

Low Betweenness and High Degree

Node’s connections are redundant -

communication bypasses him/her

Rishi Ranjan Singh Centrality Measures

Low Betweenness and High Closeness

Rishi Ranjan Singh Centrality Measures

Low Betweenness and High Closeness

Probably multiple paths in the network, Node

is near many people, but so are many others

Rishi Ranjan Singh Centrality Measures

Eigenvector Centrality

Introduces by Bonacich in 197217 .

Node’s importance is proportional to the sum of the
importance of neighboring nodes.
Mathematically:
1 �
EC (u) = (auv · EC (v ))
λ v ∈V \{u}

where λ is a constant.
Popular as Page-rank measure

17
Factoring and weighting approaches to status scores and clique identification, Journal of Mathematical
Sociology, 1972.
Rishi Ranjan Singh Centrality Measures
Eigenvector Centrality

Introduces by Bonacich in 197217 .

Node’s importance is proportional to the sum of the
importance of neighboring nodes.
Mathematically:
1 �
EC (u) = (auv · EC (v ))
λ v ∈V \{u}

where λ is a constant.
Popular as Page-rank measure

17
Factoring and weighting approaches to status scores and clique identification, Journal of Mathematical
Sociology, 1972.
Rishi Ranjan Singh Centrality Measures
Eigenvector Centrality

Introduces by Bonacich in 197217 .

Node’s importance is proportional to the sum of the
importance of neighboring nodes.
Mathematically:
1 �
EC (u) = (auv · EC (v ))
λ v ∈V \{u}

where λ is a constant.
Popular as Page-rank measure

17
Factoring and weighting approaches to status scores and clique identification, Journal of Mathematical
Sociology, 1972.
Rishi Ranjan Singh Centrality Measures
Application:Eigenvector Centrality

Google uses to compute the Page-rank of documents while

searching
Twitter uses to recommend users, who to follow
More sophisticated measure (than degree) to find highly
exposed nodes

Rishi Ranjan Singh Centrality Measures