Title: A Framework for the Evaluation and Management of Network Centrality
Authors: Vatche Ishakian, Dora Erdos, Evimaria Terzi, and Azer Bestavros
Date: October 13, 2011
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.