Finding groups with maximum betweenness centrality via integer programming with random path sampling
Finding groups with maximum betweenness centrality via integer programming with random path sampling
复制标题
DOI：
10.1007/s10898-022-01269-2
复制
发表时间：
2023-02
影响因子：
1.8
通讯作者：
Tomas Lagos;O. Prokopyev;Alexander Veremyev
中科院分区：
文献类型：
--
作者：
Tomas Lagos;O. Prokopyev;Alexander Veremyev
一种访问网络中一组节点的重要性/影响力的流行方法是基于中心性的概念。对于给定的组，其组介数中心性首先通过评估被所考虑的组中的至少一个节点“覆盖”的网络中的每个节点对之间的最短路径的比率来计算，然后对所有节点对的所有这些比率求和。在本文中，我们研究的问题，找到最有影响力的（或中心）组的节点（一些预定义的大小）在网络中的介数中心的概念的基础上。解决该问题的一种已知方法完全依赖于使用线性混合整数规划（线性MIP）模型。然而，该MIP模型的大小（相对于变量和约束的数量）在最坏情况下是指数的，因为它需要计算网络中的所有（或几乎所有）最短路径。我们通过考虑随机化方法来解决这个限制，该方法通过对足够大数量的最短路径进行采样来解决尺寸小得多的单个线性MIP（或一系列线性MIP）。我们的方法提供的解决方案的质量的一些概率估计进行了讨论。最后，我们说明了我们的方法在计算研究中的性能。
One popular approach to access the importance/influence of a group of nodes in a network is based on the notion of centrality. For a given group, its group betweenness centrality is computed, first, by evaluating a ratio of shortest paths between each node pair in a network that are “covered” by at least one node in the considered group, and then summing all these ratios for all node pairs. In this paper we study the problem of finding the most influential (or central) group of nodes (of some predefined size) in a network based on the concept of betweenness centrality. One known approach to solve this problem exactly relies on using a linear mixed-integer programming (linear MIP) model. However, the size of this MIP model (with respect to the number of variables and constraints) is exponential in the worst case as it requires computing all (or almost all) shortest paths in the network. We address this limitation by considering randomized approaches that solve a single linear MIP (or a series of linear MIPs) of a much smaller size(s) by sampling a sufficiently large number of shortest paths. Some probabilistic estimates of the solution quality provided by our approaches are also discussed. Finally, we illustrate the performance of our methods in a computational study.