Scribd
Upload
20 views

3 Lecture 10

This document discusses different ways to measure node importance in networks, including degree centrality and closeness centrality. Degree centrality measures a node's importance based on the number of connections it has, while closeness centrality measures how closely connected a node is to other nodes based on the shortest path distances.

Uploaded by

Aryan Chaudhary
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views

3 Lecture 10

This document discusses different ways to measure node importance in networks, including degree centrality and closeness centrality. Degree centrality measures a node's importance based on the number of connections it has, while closeness centrality measures how closely connected a node is to other nodes based on the shortest path distances.

Uploaded by

Aryan Chaudhary
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 18

Degree and closeness

Centrality
Node Importance
• There are multiple ways of thinking node importance .i.e.
• Number of connection one node has.
Another way
• Another way to think of node importance is Average proximity.
• Means nodes who are important are the nodes that are close to other
nodes or Nodes have high proximity to other nodes

• So Instead of 33 we will have node 9 and instead of 2 we will have 32.


Other stays same.
Another way
• We can say that the node who tend to connect other nodes are
important.
• It means that the nodes that lies in shortest paths or fractions of
shortest path that pass through a node is important node.

• So Instead of having node 9, we have node 33 in top 5 Nodes.


• We have seen some informal ways of measuring node importance.
• Next we will try to formalize this concept
• This topic in general called as network centrality.
• Centrality allows us to find most important nodes in networks.
• We study node importance to know that if any how that node got
removed then it cause whole network rupture or breakup in different
components.
Cases:
• These are the measures that we may discover.
• We will discuss degree and closeness centrality in this lecture.

• In directed graphs, we can use in-degree, out-degree or combination


of both.
• If you are connected to all nodes then It is 1 if connected to no one then it is 0.
Degree centrality- Directed Network
• So centrality divided into indegree centrality and out degree
centrality.
Out Degree:
• Very same way we can defined the out degree centrality .
2-Closeness centrality:
• It says that the nodes that are important are going to be short distance away from all other nodes in
network.
• Recall the distance between two nodes is length of shortest path between them.

• So closeness centrality pf some node v is number of nodes-1 divided by sum of distances(Shortest paths) of v
to all other nodes
NetworkX for closeness centrality:

• Using it’s definition Lets see how this 0.541 comes.


Assumption and special cases:
• It is assumption that all nodes can not reach other but this is not the
case always.
• In directed graph it sis general problem and in undirected graph it can
happen when we have disconnected components.
• So how to measure closeness centrality of a node when it can not
reach all other nodes? Such that

• Here Node L can reach only M.


Solutions:
• We have couple of options:

• It is number of nodes that L can reach divided by sum of distances


from L to all other nodes that L can reach.
- R(L) = M, |R(L)|=1
- Denominator = L M = 1 distance
- But it is highest possible
centrality.

So problem is centrality is too high for a node that can reach only one node
Option2:
• Previous one is unintuitive so option2 comes..

• It fraction of nodes that L can reach which make more sense


• We have not changed the definition of Closeness centrality.
In Disconnected graphs:
• How we can ask networkX to compute closeness centrality when
nodes are disconnected in case when we normalize data and when
not normalize it.

You might also like