A penalty box approach for approximation betweenness and closeness centrality algorithms

Sushant S. Khopkar, Rakesh Nagi, Gregory Tauer

Research output: Contribution to journalArticlepeer-review


Centrality metrics are used to find important nodes in social networks. In the days of ever-increasing social network sizes, it becomes more and more difficult to compute centrality scores of all nodes quickly. One of the ways to tackle this problem is to use approximation centrality algorithms using sampling techniques. Also, in situations where finding only high value individuals/important nodes is the primary objective, accuracy of rank ordering of nodes is especially important. We propose a new sampling method similar to Tabu search, called “penalty box approach,” which can be used for approximation closeness and betweenness algorithms. On a variety of graphs we experimentally demonstrate that this new method when combined with previously known methods, such as random sampling and linear scaling, produces better results. The evaluation is done based on two measures that assess quality of rank ordered lists of nodes when compared against the true lists based on their closeness and betweenness scores. Effects of graph characteristics on the parameters of the proposed method are also analyzed.

Original languageEnglish (US)
Article number4
Pages (from-to)1-13
Number of pages13
JournalSocial Network Analysis and Mining
Issue number1
StatePublished - Dec 1 2016

ASJC Scopus subject areas

  • Information Systems
  • Communication
  • Media Technology
  • Human-Computer Interaction
  • Computer Science Applications


Dive into the research topics of 'A penalty box approach for approximation betweenness and closeness centrality algorithms'. Together they form a unique fingerprint.

Cite this