An Extension of the Owen-Value Interaction Index and Its Application to Inter-Links Prediction

Piotr Lech Szczepański , Tomasz P. Michalak , Talal Rahwan , Michael Wooldridge

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.
Author Piotr Lech Szczepański II
Piotr Lech Szczepański,,
- The Institute of Computer Science
, Tomasz P. Michalak - Uniwersytet Warszawski (UW), University of Oxford (UO)
Tomasz P. Michalak,,
-
, Talal Rahwan - Masdar Institute of Science and Technology (MIST)
Talal Rahwan,,
-
, Michael Wooldridge - University of Oxford (UO)
Michael Wooldridge,,
-
Pages90-98
Publication size in sheets0.5
Book Kaminka Gal A., Fox Maria, Bouquet Paolo, Dignum Virginia, Dignum Frank, van Harmelen Frank (eds.): The proceedings of the Twenty-second European Conference on Artificial Intelligence (ECAI 2016), Frontiers in Artificial Intelligence and Applications, vol. 285, 2016, IOS Press, ISBN 978-1-61499-671-2, [978-1-61499-672-9], 1834 p., DOI:10.3233/978-1-61499-672-9-90
Keywords in EnglishInter-Links Prediction
DOIDOI:10.3233/978-1-61499-672-9-90
URL http://ebooks.iospress.nl/volumearticle/44746
projectGame theoretical approach to determining a crucial nodes in the networks. Project leader: Szczepański Piotr Lech, , Phone: +48 22 234-7148, application date 13-06-2013, start date 21-03-2014, end date 20-03-2017, II/2014/PRELUDIUM/1, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
Languageen angielski
File
ecai2016a.pdf / 317.49 KB / ecai2016a.pdf 317.49 KB
Score (nominal)15
ScoreMinisterial score = 15.0, 27-03-2017, BookChapterSeriesAndMatConf
Ministerial score (2013-2016) = 15.0, 27-03-2017, BookChapterSeriesAndMatConf
Citation count*0
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back