Back to search

Rochester Institute of Technology

Efficiency and Betweenness Centrality of Graphs and some Applications

Abstract

dc:description.abstract

The distance dG(i,j) between any two vertices $i$ and $j$ in a graph $G$ is the minimum number of edges in a path between $i$ and $j$. If there is no path connecting $i$ and $j$, then dG(i,j)=infty. In 2001, Latora and Marchiori introduced the measure of efficiency between vertices in a graph. The efficiency between two vertices $i$ and $j$ is defined to be ini,j=frac{1}{dG(i,j)} for all $ineq j$. The textit{global efficiency} of a graph is the average efficiency over all $ineq j$. The {it power of a graph} Gm is defined to be V(Gm)=V(G) and E(Gm)={(u,v)|dG(u,v)le m}. In this paper we determine the global efficiency for path power graphs Pnm, cycle power graphs Cnm, complete multipartite graphs Km,n, star and subdivided star graphs, and the Cartesian products Kntimes Pmt, Kntimes Cmt, Kmtimes Kn, and Pmtimes Pn. The concept of global efficiency has been applied to optimization of transportation systems and brain connectivity. We show that star-like networks have a high level of efficiency. We apply these ideas to an analysis of the Metropolitan Atlanta Rapid Transit Authority (MARTA) Subway system, and show this network is 82% as efficient as a network where there is a direct line between every pair of stations. From BOLD fMRI scans we are able to partition the brain with consistency in terms of functionality and physical location. We also find that football players who suffer the largest number of high-energy impacts experience the largest drop in efficiency over a season. Latora and Marchiori also presented two local properties. The textit{local efficiency} Eloc=frac{1}{n}sumlimitsiin V(G)Eglobleft(Giright) is the average of the global efficiencies over the subgraphs Gi, the subgraph induced by the neighbors of $i$. The clustering coefficient of a graph $G$ is defined to be CC(G)=frac{1}{n}sumlimitsiCi where Ci=|E(Gi)|/binom{|V(Gi)|}{2} is a degree of completeness of Gi. In this paper, we compare and contrast the two quantities, local efficiency and clustering coefficient. Betweenness centrality is a measure of the importance of a vertex to the optimal paths in a graph. Betweenness centrality of a vertex is defined as bc(v)=sumx,yfrac{sigmaxy(v)}{sigmaxy} where sigmaxy is the number of unique paths of shortest length between vertices $x$ and $y$. sigmaxy(v) is the number of optimal paths that include the vertex $v$. In this paper, we examined betweenness centrality for vertices in Cnm. We also include results for subdivided star graphs and C3 star graphs. A graph is said to have unique betweenness centrality if bc(vi)=bc(vj) implies $i=j$: the betweenness centrality function is injective over the vertices of $G$. We describe the betweenness centrality for vertices in ladder graphs, P2times Pn. An appended ladder graph Un is P2times Pn with a pendant vertex attached to an tbl endtbr. We conjecture that the infinite family of appended graphs has unique betweenness centrality.

Degree

thesis:*
Name thesis:degree_name
Applied and Computational Mathematics (MS)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
School of Mathematical Sciences (COS)

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ek, Bryan
Contributors dc:contributor
  • Darren Narayan

Subjects

dc:subject × 6

Identifiers

dc:identifier.*
Repository record dc:identifier
https://repository.rit.edu/theses/8585

Chain of custody

source
Harvested from
Rochester Institute of Technology
Base URL
repository.rit.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ek, Bryan. Efficiency and Betweenness Centrality of Graphs and some Applications. Thesis thesis, https://repository.rit.edu/theses/8585