Network Analysis and Centrality Measures (Part-I)

Firstly a network is a cluster of closely related components. May it be people, cities, or any other related stuff. Their relationship with each other is represented diagrammatically in the form of graphs which are called NETWORKS.
Few terminologies used in this domain:Node: Every individual component is represented using a dot in the network diagram which is referred as a node. There will be connections between the nodes (vertices for convinience) and they form the edges.Degree of a node: The number of other nodes that are connected to a node constitutes the degree of the node. There are again two types of degrees, namely:Indegree : In a directed graph, the number of edges from other nodes that are directed towards a node forms the indegree of the node.Outdegree : In a directed graph, the number of edges from a node towards other nodes constitute the outdegree of the node.Centrality: Centrality is the measure of importance of a node in a network.Centrality Measures:Degree Centrality.Closeness Centrality.Betweeness Centrality.EigenVector Centrality.Degree Centrality: By this method of measuring the importance of the node in a given network we define that the node with the highest degree is more important and hence it is having greater impact over rest of the other nodes.Closeness Centrality: By this method of measuring the importance of node in a given network, we take the average distance of a node from all the other nodes. Whichever node has a lesser average value is the node which is nearer to every node and thus it is the node with the higher centrality.Betweeness Centrality: In this, all the shortest paths between the nodes are taken and observed which node is visited most of the times while traversing the shortest paths and such a most visited node is the one with highest centrality or that is the node with greater importance.EigenVector Centrality: This method assigns a relative value to a node with respect to the nodes it is connected with. So the one which is connected to a node with better importance will always get a better centrality value. For example: If 100 nodes are connected to node A and node A is connected to node B along with 50 other nodes and node C is connected with 60 nodes and not with A, then the node B will get better than node B because node A to which node B is connected is having a higher centrality or degree or importance. This is used in Google Page Ranking algorithm using walking bots method.In the next article, I will get back to you all with the mathematical approach of the above centralities and also a short note on ranking these nodes based on their centrality values.With regards,Samarth Deyagond.(Research Fellow @ IIT, Ropar)

News Reporter

Leave a Reply

Your email address will not be published. Required fields are marked *