It's Not Whom You Know, It's What You (or Your Friends) Can Do: Succint Coalitional Frameworks for Network Centralities

It's Not Whom You Know, It's What You (or Your Friends) Can Do: Succint Coalitional Frameworks for Network Centralities. September 25, 2019 Abstract We investigate the representation of game-theoretic measures of network centrality using a framework that blends a social network representation with the succint formalism of cooperative skill games. We discuss the expressiveness of the new framework and highlight some of its advantages, including a fixed-parameter tractability result for computing centrality measures under such representations. As an application we introduce new network centrality measures that capture the extent to which neighbors of a certain node can help it complete relevant tasks. 1 Introduction Measures of network centrality have a long and rich history in the social sciences [1] and Artificial Intelligence. Such measures have proved useful for a variety of tasks, such as identifying spreading nodes [2] and gatekeepers for information dissemination [3], advertising ...