Measuring Topological Properties of Networks - Centralities

University:
Boston University
Course:
CAS CS 501 | Computer Science Practicum
Academic year:

2020
Views:

336

Pages:

8
Author:

hanzestisswj

Measuring Topological Properties of Networks (2): Centralities Centrality measures (“B,C,D,E”) • Degree centrality – How many connections the node has • Betweenness centrality – How many shortest paths go through the node • Closeness centrality – How close the node is to other nodes • Eigenvector centrality Degree centrality • Simply, # of links attached to a node CD(v) = deg(v) or sometimes defined as CD(v) = deg(v) / (N-1) Betweenness centrality • Prob. for a node to be on shortest paths between two other nodes CB(v) = Σs≠v,t≠v #sp(s,e,v) #sp(s,e) • s: start node, e: end node • #sp(s,e,v): # of shortest paths from s to e that go though node v • #sp(s,e): total # of shortest paths from s to e • Easily generalizable to “group betweenness” Closeness centrality • Inverse of an average distance from a node to all the other nodes n-1 CC(v) = Σw≠v d(v,w) • d(v,w): length of the shortest path from v to w • Its inverse is called “farness” • Sometimes “Σ” is moved out of the fraction (it works for networks that are not strongly connected) • NetworkX calculates closeness within each connected component Eigenvector centrality • Eigenvector of the largest eigenvalue of the adjacency matrix of a network CE(v) = (v-th element of x) Ax = lx • l: dominant eigenvalue • x is often normalized (|x| = 1) Exercise • Who is most central by degree, betweenness, closeness, eigenvector? Which centrality to use? • To find the most popular person • To find the most efficient person to collect information from the entire organization • To find the most powerful person to control information flow within an organization • To find the most important person (?)