[Dmbu-l] A Framework for the Evaluation and Management of Network Centrality [Thursday 04/05 @ 12:00 pm in MCS 137]

Charalampos Mavroforakis cmav at bu.edu
Mon Apr 2 15:14:21 EDT 2012


Boston University -- Computer Science Department

*Data Mining and Database Group Speaker*

Thursday, April 5, 2012
12:00 - 1:30 PM
MCS 137

*
A Framework for the Evaluation and
Management of Network Centrality
*
*

*
*Dora Erdos*
Boston University



*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.

Joint work with together with Vatche Ishakian, Evimaria Terzi and Azer
Bestavros.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cs-mailman.bu.edu/pipermail/dmbu-l/attachments/20120402/09a72368/attachment.html 


More information about the Dmbu-l mailing list