Closeness Centrality for Networks with Overlapping Community Structure

Authors

  • Mateusz Tarkowski University of Oxford
  • Piotr Szczepański Warsaw University of Technology
  • Talal Rahwan Masdar Institute of Science and Technology
  • Tomasz Michalak University of Oxford and University of Warsaw
  • Michael Wooldridge University of Oxford

DOI:

https://doi.org/10.1609/aaai.v30i1.10034

Keywords:

Network Centrality, Game Theory

Abstract

Certain real-life networks have a community structure in which communities overlap. For example, a typical bus network includes bus stops (nodes), which belong to one or more bus lines (communities) that often overlap. Clearly, it is important to take this information into account when measuring the centrality of a bus stop - how important it is to the functioning of the network. For example, if a certain stop becomes inaccessible, the impact will depend in part on the bus lines that visit it. However, existing centrality measures do not take such information into account. Our aim is to bridge this gap. We begin by developing a new game-theoretic solution concept, which we call the Configuration semivalue, in order to have greater flexibility in modelling the community structure compared to previous solution concepts from cooperative game theory. We then use the new concept as a building block to construct the first extension of Closeness centrality to networks with community structure (overlapping or otherwise). Despite the computational complexity inherited from the Configuration semivalue, we show that the corresponding extension of Closeness centrality can be computed in polynomial time. We empirically evaluate this measure and our algorithm that computes it by analysing the Warsaw public transportation network.

Downloads

Published

2016-02-21

How to Cite

Tarkowski, M., Szczepański, P., Rahwan, T., Michalak, T., & Wooldridge, M. (2016). Closeness Centrality for Networks with Overlapping Community Structure. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10034

Issue

Section

Technical Papers: Game Theory and Economic Paradigms