A framework for the evaluation and management of network centrality
Date
2011-10-13
DOI
Authors
Ishakian, Vatche
Erdos, Dora
Terzi, Evimaria
Bestavros, Azer
Version
OA Version
Citation
Ishakian, Vatche; Erdos, Dora; Terzi, Evimaria; Bestavros, Azer. "A Framework for the Evaluation and Management of Network Centrality", Technical Report BUCS-TR-2011-022, Computer Science Department, Boston University, October 13, 2011. [Available from: http://hdl.handle.net/2144/11379]
Abstract
Network-analysis literature is rich in node-centrality measures that quantify the centrality of a node as a function of the (shortest) paths of the network that go through it. Existing work focuses on defining instances of such measures and designing algorithms for the specific combinatorial problems that arise for each instance. In this work, we propose a unifying definition of centrality that subsumes all path-counting based centrality definitions: e.g., stress, betweenness or paths centrality. We also define a generic algorithm for computing this generalized centrality measure for every node and every group of nodes in the network. Next, we define two optimization problems: k-Group Centrality Maximization and k-Edge Centrality Boosting. In the former, the task is to identify the subset of k nodes that have the largest group centrality. In the latter, the goal is to identify up to k edges to add to the network so that the centrality of a node is maximized. We show that both of these problems can be solved efficiently for arbitrary centrality definitions using our general framework. In a thorough experimental evaluation we show the practical utility of our framework and the efficacy of our algorithms.