Show simple item record

dc.contributor.advisorVeni Madhavan, C E
dc.contributor.authorSudarshan, S R
dc.date.accessioned2014-03-03T07:28:32Z
dc.date.accessioned2018-07-31T04:38:26Z
dc.date.available2014-03-03T07:28:32Z
dc.date.available2018-07-31T04:38:26Z
dc.date.issued2014-03-03
dc.date.submitted2011
dc.identifier.urihttps://etd.iisc.ac.in/handle/2005/2283
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/2938/G25234-Abs.pdfen_US
dc.description.abstractStudy 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.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG25234en_US
dc.subjectNetwork Centrality Measuresen_US
dc.subjectCentrality Measuresen_US
dc.subjectNavigationen_US
dc.subjectPath Findingen_US
dc.subjectHuman Navigation - Network Analysisen_US
dc.subjectHuman Navigationen_US
dc.subjectHuman-wayfinding Problemen_US
dc.subjectNetwork Analysisen_US
dc.subject.classificationComputer Scienceen_US
dc.titleNetwork Centrality Measures And Their Applicationsen_US
dc.typeThesisen_US
dc.degree.namePhDen_US
dc.degree.levelDoctoralen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record