Closeness centrality is one way of measuring how central a node is in the given network. The closeness centrality measure assigns a centrality value to each node based on its accessibility to the whole network. In real life applications, we are mainly interested in ranking nodes based on their centrality values. The classical method to compute the rank of a node first computes the closeness centrality of all nodes and then compares them to get its rank. Its time complexity is @math , where @math represents total number of nodes, and @math represents total number of edges in the network. In the present work, we propose a heuristic method to fast estimate the closeness rank of a node in @math time complexity, where @math . We also propose an extended improved method using uniform sampling technique. This method better estimates the rank and it has the time complexity @math , where @math . This is an excellent improvement over the classical centrality ranking method. The efficiency of the proposed methods is verified on real world scale-free social networks using absolute and weighted error functions.
Most of the real life applications focus on identifying few top nodes having the highest closeness centrality. proposed a method to rank @math highest closeness centrality nodes using a hybrid of approximate and exact algorithms @cite_39 . Ufimtsev proposed an algorithm to identify high closeness centrality nodes using group testing @cite_0 . presented an efficient technique to find @math most central nodes based on closeness centrality @cite_14 . They used intermediate results of centrality computation to minimize the computation time. proposed a faster method to identify top- @math nodes in undirected networks by approximating the upper bound on closeness centrality using BFT @cite_5 .
@cite_0 @cite_5 @cite_14 @cite_39
1973450591 2295695614 1536060130
The significance of an entity in a network is generally given by the centrality value of its vertex. For most analysis purposes, only the high ranked vertices are required. However, most algorithms calculate the centrality values of all the vertices. We present an extremely fast and scalable algorithm for identifying the high closeness centrality vertices, using group testing. We show that our approach is significantly faster (best-case over 50 times, worst-case over 7 times) than the currently used methods. We can also use group testing to identify networks that are sensitive to edge perturbation. Given a connected graph G = (V,E), the closeness centrality of a vertex v is defined as (n-1 w V d(v,w). This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the k most central vertices has been deeply analysed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the paper, we prove that it is not solvable in time O(|E|^ 2-epsilon) on directed graphs, for any constant epsilon > 0, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the k most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top k nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the 10 most central actors in the IMDB collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page p to a page q if p contains a link to q. Closeness centrality is an important concept in social network analysis. In a graph representing a social network, closeness centrality measures how close a vertex is to all other vertices in the graph. In this paper, we combine existing methods on calculating exact values and approximate values of closeness centrality and present new algorithms to rank the top-kvertices with the highest closeness centrality. We show that under certain conditions, our algorithm is more efficient than the algorithm that calculates the closeness-centralities of all vertices.