  Who is more important in a network? Who controls the flow between the nodes
or whose contribution is significant for connections? Centrality metrics play
an important role while answering these questions. The betweenness metric is
useful for network analysis and implemented in various tools. Since it is one
of the most computationally expensive kernels in graph mining, several
techniques have been proposed for fast computation of betweenness centrality.
In this work, we propose and investigate techniques which compress a network
and shatter it into pieces so that the rest of the computation can be handled
independently for each piece. Although we designed and tuned the shattering
process for betweenness, it can be adapted for other centrality metrics in a
straightforward manner. Experimental results show that the proposed techniques
can be a great arsenal to reduce the centrality computation time for various
types of networks.
