Show simple item record

dc.contributor.authorKhopkar, Sushant S.
dc.date.accessioned2016-03-29T17:18:48Z
dc.date.available2016-03-29T17:18:48Z
dc.date.issued2010
dc.identifier.isbn9781124244723
dc.identifier.other757921493
dc.identifier.urihttp://hdl.handle.net/10477/45936
dc.description.abstractIn social network analysis, graph-theoretic concepts are used to understand and explain social phenomena. Calculations of centrality metrics such as Degree centrality, Closeness centrality, and Betweenness centrality are essential parts of network analysis. These centrality metrics indicate the prominence of individual nodes within a social network. In case of static graphs, algorithms have been designed and implemented to compute the aforementioned metrics. However if a graph is dynamic, that is if some nodes and edges are added or deleted from a graph at some later stage, then recalculating values of these centrality metrics from scratch is a costly operation in terms of computational efforts and time. This work involves design and implementation of incremental algorithms which will compute values of Degree, Closeness and Betweenness Centralities for dynamically changing social networks. Closeness and Betweenness Centralities are based on the concept of All Pairs Shortest Paths. Hence, the design of incremental algorithms for these Centrality Metrics are built on the foundations of an incremental All Pairs Shortest Path algorithm. Our incremental All Pairs Shortest Path algorithm runs in O ( n 2 ) time, which is an improvement over current fastest implemented algorithm running in O ( n 2 logn ) time. We also show that O ( n 2 ) is a theoretical lower bound for Dynamic All Pairs Shortest Path algorithm. This work also compares repeated use of static algorithms for Centrality Metrics with the newly designed incremental algorithms. Results indicate that the incremental versions are capable of running approximately 655 times faster than their static counterparts for a graph of 1000 nodes.
dc.languageEnglish
dc.sourceDissertations & Theses @ SUNY Buffalo,ProQuest Dissertations & Theses Global
dc.subjectSocial sciences
dc.subjectApplied sciences
dc.subjectAll pairs shortest paths
dc.subjectDynamic graph algorithms
dc.subjectIncremental algorithms
dc.subjectSocial network analysis
dc.titleIncremental algorithms for centrality metric calculations in social network analysis
dc.typeDissertation/Thesis


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record