{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-2557"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-2557","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Path Centrality: A New Centrality Measure in Networks","abstract":"In network analysis, it is useful to identify important vertices in a network. Based on the varying notions of importance of vertices, a number of centrality measures are defined and studied in the literature. Some popular centrality measures, such as betweenness centrality, are computationally prohibitive for large-scale networks. In this thesis, we propose a new centrality measure called k-path centrality and experimentally compare this measure with betweenness centrality. We present a polynomial-time randomized algorithm for distinguishing high k-path centrality vertices from low k-path centrality vertices in any given (unweighted or weighted) graph. Specifically, for any graph G = (V, E) with n vertices and for every choice of parameters α ∈ (0, 1), ε ∈ (0, 1/2), and integer k ∈ [1, n], with probability at least 1 − 1/n2 our randomized algorithm distinguishes all vertices v ∈ V that have k-path centrality Ck(v) more than nα(1 + 2ε) from all vertices v ∈ V that have k-path centrality Ck(v) less than nα(1 − 2ε). The running time of the algorithm is O(k2ε −2n1−α ln n). Theoretically and experimentally, our algorithms are (for suitable choices of parameters) significantly faster than the best known deterministic algorithm for computing exact betweenness centrality values (Brandes’ algorithm). Through experimentations on both real and randomly generated networks, we demonstrate that vertices that have high betweenness centrality values also have high k-path centrality values.","abstract_html":"In network analysis, it is useful to identify important vertices in a network. Based on the varying notions of importance of vertices, a number of centrality measures are defined and studied in the literature. Some popular centrality measures, such as betweenness centrality, are computationally prohibitive for large-scale networks. In this thesis, we propose a new centrality measure called k-path centrality and experimentally compare this measure with betweenness centrality. We present a polynomial-time randomized algorithm for distinguishing high k-path centrality vertices from low k-path centrality vertices in any given (unweighted or weighted) graph. Specifically, for any graph G = (V, E) with n vertices and for every choice of parameters α ∈ (0, 1), ε ∈ (0, 1/2), and integer k ∈ [1, n], with probability at least 1 − 1/n2 our randomized algorithm distinguishes all vertices v ∈ V that have k-path centrality Ck(v) more than nα(1 + 2ε) from all vertices v ∈ V that have k-path centrality Ck(v) less than nα(1 − 2ε). The running time of the algorithm is O(k2ε −2n1−α ln n). Theoretically and experimentally, our algorithms are (for suitable choices of parameters) significantly faster than the best known deterministic algorithm for computing exact betweenness centrality values (Brandes’ algorithm). Through experimentations on both real and randomly generated networks, we demonstrate that vertices that have high betweenness centrality values also have high k-path centrality values.","abstract_has_math":false,"creators":["Alahakoon, Tharaka"],"institution":"University of South Florida","degree_name":null,"degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Rahul Tripathi, Ph.D.","Adriana Iamnitchi, Ph.D.","Miguel Labrador, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-05-28T07:00:00Z","date_published":"2010-05-28T07:00:00Z","updated_at":"2026-11-19T08:36:18Z","subjects":["betweenness centrality","social networks","randomized algorithms","experimental algorithmics","graphs","American Studies","Arts and Humanities"],"languages":["EN-US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/1558","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/1558","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-2557","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Rahul Tripathi, Ph.D.","Adriana Iamnitchi, Ph.D.","Miguel Labrador, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Alahakoon, Tharaka"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-05-28T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.S.C.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["betweenness centrality","social networks","randomized algorithms","experimental algorithmics","graphs","American Studies","Arts and Humanities"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["EN-US"]},{"key":"dc:rights.license","label":"Dc Rights License","values":["default"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/1558"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In network analysis, it is useful to identify important vertices in a network. Based on the varying notions of importance of vertices, a number of centrality measures are defined and studied in the literature. Some popular centrality measures, such as betweenness centrality, are computationally prohibitive for large-scale networks. In this thesis, we propose a new centrality measure called k-path centrality and experimentally compare this measure with betweenness centrality. We present a polynomial-time randomized algorithm for distinguishing high k-path centrality vertices from low k-path centrality vertices in any given (unweighted or weighted) graph. Specifically, for any graph G = (V, E) with n vertices and for every choice of parameters α ∈ (0, 1), ε ∈ (0, 1/2), and integer k ∈ [1, n], with probability at least 1 − 1/n2 our randomized algorithm distinguishes all vertices v ∈ V that have k-path centrality Ck(v) more than nα(1 + 2ε) from all vertices v ∈ V that have k-path centrality Ck(v) less than nα(1 − 2ε). The running time of the algorithm is O(k2ε −2n1−α ln n). Theoretically and experimentally, our algorithms are (for suitable choices of parameters) significantly faster than the best known deterministic algorithm for computing exact betweenness centrality values (Brandes’ algorithm). Through experimentations on both real and randomly generated networks, we demonstrate that vertices that have high betweenness centrality values also have high k-path centrality values."]},{"key":"dc:title","label":"Title","values":["Path Centrality: A New Centrality Measure in Networks"]}]}],"canonical_facts":{"dc:contributor":["Rahul Tripathi, Ph.D.","Adriana Iamnitchi, Ph.D.","Miguel Labrador, Ph.D."],"dc:creator":["Alahakoon, Tharaka"],"dc:date":["2010-05-28T07:00:00Z"],"dc:description":["In network analysis, it is useful to identify important vertices in a network. Based on the varying notions of importance of vertices, a number of centrality measures are defined and studied in the literature. Some popular centrality measures, such as betweenness centrality, are computationally prohibitive for large-scale networks. In this thesis, we propose a new centrality measure called k-path centrality and experimentally compare this measure with betweenness centrality. We present a polynomial-time randomized algorithm for distinguishing high k-path centrality vertices from low k-path centrality vertices in any given (unweighted or weighted) graph. Specifically, for any graph G = (V, E) with n vertices and for every choice of parameters α ∈ (0, 1), ε ∈ (0, 1/2), and integer k ∈ [1, n], with probability at least 1 − 1/n2 our randomized algorithm distinguishes all vertices v ∈ V that have k-path centrality Ck(v) more than nα(1 + 2ε) from all vertices v ∈ V that have k-path centrality Ck(v) less than nα(1 − 2ε). The running time of the algorithm is O(k2ε −2n1−α ln n). Theoretically and experimentally, our algorithms are (for suitable choices of parameters) significantly faster than the best known deterministic algorithm for computing exact betweenness centrality values (Brandes’ algorithm). Through experimentations on both real and randomly generated networks, we demonstrate that vertices that have high betweenness centrality values also have high k-path centrality values."],"dc:identifier":["https://digitalcommons.usf.edu/etd/1558"],"dc:language":["EN-US"],"dc:rights.license":["default"],"dc:subject":["betweenness centrality","social networks","randomized algorithms","experimental algorithmics","graphs","American Studies","Arts and Humanities"],"dc:title":["Path Centrality: A New Centrality Measure in Networks"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis","M.S.C.S."],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:36:18Z"}