Title: Efficient Closeness Centrality Computation for Dynamic Graphs
Authors: Zhenzhen Shao, Na Guo, Yu Gu, Zhigang Wang, Fangfang Li and Ge Yu
Abstract: As a classic metric, closeness centrality can measure the importance of a node in a graph by its proximity to the other nodes. However, exactly calculating closeness centrality of all nodes is significantly time-consuming. Besides, graphs usually evolve with inserted and/or deleted edges, which exacerbates the performance issue if we recompute results from scratch. The paper proposes a preliminary algorithm for calculating exact closeness centrality by using biconnected components and articulation points. Firstly, a large graph is divided into a series of biconnected components which are connected by articulation points. Then distance between arbitrary nodes on the whole graph can be converted into multiple distances between different biconnected components. We further propose an incremental update technique to dynamically maintain the computation results when graphs are changing, like inserting and/or deleting edges, by efficiently detecting all the affected shortest paths to update the closeness centrality based on articulation points. We finally conduct extensive experiments over real graphs to validate the efficiency and effectiveness of our techniques.
