A Framework for the Evaluation and Management of Network Centrality

12th SIAM International Conference on Data Mining

数学;计算机科学

Vatche Ishakian ; Dóra Erdös ; Evimaria Terzi ; Azer Bestavros

Others  :  http://siam.omnibooksonline.com/2012datamining/data/papers/223.pdf
PID  :  32482

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

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 dening instances of such measures and designing algorithms for the specific combinatorial problems that arise for each instance. In this work, we propose a unifying denition of centrality that subsumes all path-counting based centrality denitions: e.g., stress, betweenness or paths centrality. We also dene a generic algorithm for computing this generalized centrality measure for every node and every group of nodes in the network. Next, we dene two optimization problems: k-Group Central- ity 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 denitions using our general framework. In a thorough experimental evaluation we show the practical utility of our framework and the ecacy of our algorithms.