  Estimating influential nodes in large scale networks including but not
limited to social networks, biological networks, communication networks,
emerging smart grids etc. is a topic of fundamental interest. To understand
influences of nodes in a network, a classical metric is centrality within which
there are multiple specific instances including degree centrality, closeness
centrality, betweenness centrality and more. As of today, existing algorithms
to identify nodes with high centrality measures operate upon the entire (or
rather global) network, resulting in high computational complexity. In this
paper, we design efficient algorithms for determining the betweenness
centrality in large scale networks by taking advantage of the modular topology
exhibited by most of these large scale networks. Very briefly, modular
topologies are those wherein the entire network appears partitioned into
distinct modules (or clusters or communities), wherein nodes within the module
(that likely share highly similar profiles) have dense connections between
them, while connections across modules are relatively sparse. Using a novel
adaptation of Dijkstra's shortest path algorithm, and executing it over local
modules and over sparse edges between modules, we design algorithms that can
correctly compute the betweenness centrality much faster than existing
algorithms. To the best of our knowledge, ours is the first work that leverage
modular topologies of large scale networks to address the centrality problem,
though here we mostly limit our discussions to social networks. We also provide
more insights on centrality in general, and also how our algorithms can be used
to determine other centrality measures.
