(untitled) (International Journal of Engineering and Computer Science, 2015)
The need for large-scale graph analysis and finding efficient methods for the same are increasing. MapReduce framework has already been accepted as a standard for large-scale analysis. Finding betweenness centrality is highly significant in finding the importance of a node in a network. In this paper, we propose a map-based method to find betweenness centrality using the multi-source message passing model. The multi-source message passing model has two phases namely the breadth-first traversal phase and the backtracking phase. In the breadth-first traversal phase, we traverse the graph in breadth-first form by sending and receiving messages and in the process find the shortest paths in the graph. In the backtracking phase, we traverse back to the source node. While doing so, we find the dependency of the source node on other vertices by transmitting messages. Both these phases are implemented in the map-based method which consists of an initial MapReduce job followed by a number of iterations of mapper functions until there are no more messages to send. We can then find betweenness centrality by summing the dependencies of all the source nodes on the vertex.