Protein-interaction network (PIN) analysis provides
valuable insight into an organism’s functional organization
and evolutionary behavior. In this paper, we study a PIN
formed by high-confidence human protein interactions obtained
from various public interaction databases. This is
the largest human PIN studied to date, comprising nearly
18,000 proteins and 44,000 interactions. A novel contribution
of this paper is the computation of betweenness centrality,
a graph-theoretic metric that is found to be positively
correlated with the essentiality and evolutionary age
of a protein. We observe that proteins with high betweenness
centrality, but low connectivity are abundant in the human
PIN. We have designed an efficient and portable parallel
implementation for the calculation of this compute-intensive
centrality metric. On the Sun Fire T2000 server
with the UltraSparc T1 (Niagara) processor, we achieve a
relative speedup of about 16 using 32 threads for a typical
instance of betweenness centrality, reducing the running
time from several minutes to 13 seconds.
