期刊
OPTIMIZATION METHODS & SOFTWARE
卷 32, 期 2, 页码 369-399出版社
TAYLOR & FRANCIS LTD
DOI: 10.1080/10556788.2016.1167892
关键词
betweenness centrality; bounded-distance betweenness centrality; group betweenness centrality; most central groups; mixed integer programming
类别
资金
- U.S. Air Force Research Laboratory (AFRL) Mathematical Modeling and Optimization Institute
- AFRL/RW [FA8651-14-2-0002]
- U.S. Air Force Summer Faculty Fellowship program
- Defense Threat Reduction Agency (DTRA) [HDTRA1-14-1-0065]
In this paper we consider the problem of identifying the most influential (or central)group of nodes (of some predefined size) in a network. Such a group has the largest value of betweenness centrality or one of its variants, for example, the length-scaled or the bounded-distance betweenness centralities. We demonstrate that this problem can be modelled as a mixed integer program (MIP) that can be solved for reasonably sized network instances using off-the-shelf MIP solvers. We also discuss interesting relations between the group betweenness and the bounded-distance betweenness centrality concepts. In particular, we exploit these relations in an algorithmic scheme to identify approximate solutions for the original problem of identifying the most central group of nodes. Furthermore, we generalize our approach for identification of not only the most central groups of nodes, but also central groups of graph elements that consists of either nodes or edges exclusively, or their combination according to some pre-specified criteria. If necessary, additional cohesiveness properties can also be enforced, for example, the targeted group should form a clique or a -club. Finally, we conduct extensive computational experiments with different types of real-life and synthetic network instances to show the effectiveness and flexibility of the proposed framework. Even more importantly, our experiments reveal some interesting insights into the properties of influential groups of graph elements modelled using the maximum betweenness centrality concept or one of its variations.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据