A penalty box approach for approximation betweenness and closeness centrality algorithms

Sushant S. Khopkar, Rakesh Nagi, Gregory Tauer

Research output: Contribution to journalArticle

Abstract

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
Volume6
Issue number1
DOIs
StatePublished - Dec 1 2016

Fingerprint

penalty
Sampling
social network
Tabu search
Approximation algorithms
tabu
scaling
evaluation

ASJC Scopus subject areas

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

Cite this

A penalty box approach for approximation betweenness and closeness centrality algorithms. / Khopkar, Sushant S.; Nagi, Rakesh; Tauer, Gregory.

In: Social Network Analysis and Mining, Vol. 6, No. 1, 4, 01.12.2016, p. 1-13.

Research output: Contribution to journalArticle

@article{867f95ab93ea4b88bd3ba4d57a754aa3,
title = "A penalty box approach for approximation betweenness and closeness centrality algorithms",
abstract = "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.",
author = "Khopkar, {Sushant S.} and Rakesh Nagi and Gregory Tauer",
year = "2016",
month = "12",
day = "1",
doi = "10.1007/s13278-015-0308-7",
language = "English (US)",
volume = "6",
pages = "1--13",
journal = "Social Network Analysis and Mining",
issn = "1869-5450",
publisher = "Springer Wien",
number = "1",

}

TY - JOUR

T1 - A penalty box approach for approximation betweenness and closeness centrality algorithms

AU - Khopkar, Sushant S.

AU - Nagi, Rakesh

AU - Tauer, Gregory

PY - 2016/12/1

Y1 - 2016/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84954328868&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84954328868&partnerID=8YFLogxK

U2 - 10.1007/s13278-015-0308-7

DO - 10.1007/s13278-015-0308-7

M3 - Article

AN - SCOPUS:84954328868

VL - 6

SP - 1

EP - 13

JO - Social Network Analysis and Mining

JF - Social Network Analysis and Mining

SN - 1869-5450

IS - 1

M1 - 4

ER -