Centrality with Diversity

Journal Article

Graph centrality measures use the structure of a network to quantify central or "important"nodes, with applications in web search, social media analysis, and graphical data mining generally. Traditional centrality measures such as the well known PageRank interpret a directed edge as a vote in favor of the importance of the linked node. We study the case where nodes may belong to diverse communities or interests and investigate centrality measures that can identify nodes that are simultaneously important to many such diverse communities. We propose a family of diverse centrality measures formed as fixed point solutions to a generalized nonlinear eigenvalue problem. Our measure can be efficiently computed on large graphs by iterated best response and we study its normative properties on both random graph models and real-world data. We find that we are consistently and efficiently able to identify the most important diverse nodes of a graph, that is, those that are simultaneously central to multiple communities.

Full Text

Duke Authors

Cited Authors

  • Lyu, L; Fain, B; Munagala, K; Wang, K

Published Date

  • August 3, 2021

Published In

  • Wsdm 2021 Proceedings of the 14th Acm International Conference on Web Search and Data Mining

Start / End Page

  • 644 - 652

Digital Object Identifier (DOI)

  • 10.1145/3437963.3441789

Citation Source

  • Scopus