Forest Distance Closeness Centrality in Disconnected Graphs Ranking the relative importance of nodes is a fundamental issue in network science, especially in the analysis of social and information networks. A variety of importance metrics and related algorithms have been proposed. However, these previous measures either do not apply to disconnected networks or have some weakness when applied to disconnected networks. In this paper, we use forest distance to assess the importance of nodes in a graph, whether connected or disconnected. For a node in a graph, its forest distance is defined as the sum of forest distances from the node to all other nodes in the graph. To illustrate the discriminating power of forest distance, we first compute the exact forest distances for all nodes in the path graph, and show that the order of node importance given by forest distances is in complete agreement with our intuition. We then show that forest distance centrality has a better discriminating power than alternate metrics such as betweenness, harmonic centrality, eigenvector centrality, and PageRank. Also, we present a theoretically guaranteed estimation algorithm, which approximates the forest distances for all nodes in a graph in nearly linear time with respect to the number of edges. Finally, we perform extensive experiments on realworld networks, which show that our approximation algorithm is both efficient and accurate for large networks.

Critical Nodes Identification in Complex Networks Critical nodes identification in complex networks is significance for studying the survivability and robustness of networks. The previous studies on structural hole theory uncovered that structural holes are gaps between a group of indirectly connected nodes and intermediaries that fill the holes and serve as brokers for information exchange. In this paper, we leverage the property of structural hole to design a heuristic algorithm based on local information of the network topology to identify node importance in undirected and unweighted network, whose adjacency matrix is symmetric. In the algorithm, a node with a larger degree and greater number of structural holes associated with it, achieves a higher importance ranking. Six real networks are used as test data. The experimental results show that the proposed method not only has low computational complexity, but also outperforms degree centrality, kshell method, mapping entropy centrality, the collective influence algorithm, DDN algorithm that based on node degree and their neighbors, and random ranking method in identifying node importance for network connectivity in complex networks.