Network Centrality Measures And Their Applications

Abstract

Study of complex networks by researchers from many disciplines has provided penetrating insights on various complex systems. A study of the world wide web from a network theoretic perspective has led to the design of new search engines [65]. The spread of diseases is now better understood by analyzing the underlying social network [26]. The study of metabolic networks, protein-protein interaction networks and the transcriptional regulatory networks with graph theoretic rigor, has led to the growing importance of an interdisciplinary approach [71]. Network centrality measures, which has been of interest to the social scientists, from as long as 1950 [13], is today studied extensively in the framework of complex networks. The thesis is an investigation on understanding human navigation with a network analytic approach using the well established and widely used centrality measures. Experiments were conducted on human participants to observe how people navigate in a complex environment. We made human participants way-find a destination from a source on a complex network and analyzed the paths that were taken. Our analysis established a fact that the learning process involved in navigating better in an unknown network boils down to learning certain strategic locations on the network. The vertices in the paths taken by the participants, when analyzed using the available centrality measures, enabled us to conclude experimentally that humans are naturally inclined to learn superior ranked vertices to navigate better and reach their intended destination. Our experiments were based on a word game called the word-morph. A generalized version of the experiment was conducted on a 6x6 photo collage with an underlying network hidden from the participant. A detailed analysis of the above experiment established a fact that, when humans are asked to take a goal-directed path, they were prone to take a path that passed through landmark nodes in the network. We call such paths center-strategic. We then present an algorithm that simulates the navigational strategy adopted by humans. We show empirically that the algorithm performs better than naive random walk based navigational techniques. We observe that the algorithm produces rich center-strategic paths on scale-free networks. We note that the effectiveness of the algorithm is highly dependent on the topology of the network by comparing its functionality on Erdos-Renyi networks and Barabasi-Albert networks. Then we discuss a lookahead algorithm to compute betweenness centrality in networks under vertex deletion operations. We show that the widely used Brandes algorithm can be modified to a lookahead version. We show that our proposed algorithm performs better than recomputing the betweenness centrality values in the vertex deleted graph. We show that our method works 20% faster than the Brandes algorithm.