Show simple item record

dc.contributor.authorSaxena, Akrati
dc.contributor.authorGera, Ralucca
dc.contributor.authorIyengar, S.R.S.
dc.date.accessioned2018-01-16T16:26:15Z
dc.date.available2018-01-16T16:26:15Z
dc.date.issued2017-06-07
dc.identifier.citationA. Saxena, R. Gera, S.R.S. Iyengar, "A faster method to estimate closeness centrality ranking," arXiv:1706.02083v1 [cs.SI] 7 Jun 2017.en_US
dc.identifier.urihttp://hdl.handle.net/10945/56660
dc.description.abstractCloseness 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 O(n · m + n), where n represents total number of nodes, and m 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 O(α · m) time complexity, where α = 3. We also pro- pose an extended improved method using uniform sampling technique. This method better estimates the rank and it has the time complexity O(α · m), where α ≈ 10 − 100. 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.en_US
dc.format.extent25 p.en_US
dc.rightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.en_US
dc.titleA faster method to estimate closeness centrality rankingen_US
dc.typeArticleen_US
dc.contributor.corporateNaval Postgraduate School (U.S.)en_US
dc.contributor.departmentApplied Mathematicsen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record