Group centrality maximization via network design

Sourav Medya, Arlei Silva, Ambuj Singh, Prithwish Basu, Ananthram Swami

Research output: Contribution to conferencePaperpeer-review

26 Scopus citations


Network centrality plays an important role in many ap-plications. Central nodes in social networks can be in-uential, driving opinions and spreading news or ru-mors. In hyperlinked environments, such as the Web, where users navigate via clicks, central content receives high traffic, becoming target for advertising campaigns. While there is an extensive amount of work on central-ity measures and their efficient computation, control-ling nodes' centrality via network updates is a more re-cent and challenging task. Performing minimal modifications to a network to achieve a desired property falls under the umbrella of network design problems. This paper is focused on improving group (coverage and be-tweenness) centrality, which is a function of the shortest paths passing through a set of nodes, by adding edges to the network. Several variations of the problem, which are NP-hard as well as APX-hard, are introduced. We present a greedy algorithm, and even faster sampling algorithms, for group centrality maximization with the-oretical quality guarantees under realistic constraints. The experimental results show that our sampling algo-rithms outperform the best baseline solution in terms of centrality by up to 5 times while being 2-3 orders of magnitude faster than our greedy approach.

Original languageEnglish (US)
Number of pages9
StatePublished - 2018
Externally publishedYes
Event2018 SIAM International Conference on Data Mining, SDM 2018 - San Diego, United States
Duration: May 3 2018May 5 2018


Conference2018 SIAM International Conference on Data Mining, SDM 2018
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Computer Science Applications
  • Software


Dive into the research topics of 'Group centrality maximization via network design'. Together they form a unique fingerprint.

Cite this