Identifying Important Nodes: Centrality Metrics

Kimmo Soramäki and Samantha Cook

The fields of statistical mechanics and social network analysis have seen significant progress towards understanding the structure and functioning of complex networks. A multitude of centrality measures has been developed, each with an explicit or implicit network process in mind. When deciding which measure is best for the question at hand, it is useful to think about the assumptions of the centrality metrics in terms of processes taking place in the networks. Borgatti (2005) identifies several stylised processes. According to this typology, a process can move through a network via geodesic paths, paths, trails or walks. Processes that travel via geodesic (shortest) paths are, for example, problems of the “travelling salesman” type – ie, they always take the shortest route between two nodes. Processes that travel via paths need not necessarily use the shortest route, but do not visit any node more than once. These can, for example, be viral infections (a person becomes immune once infected, so cannot become infected again) or the routing of Internet traffic.

Processes that travel along trails do not visit any given link more than once. An example of this is the spread of gossip