Title：On Interdicting Dense Clusters in a Network
标题：关于网络中密集簇的拦截
相关数据
作者简介
About the Author
钟昊男
云南财经大学商学院
Foad Mahdavi Pajouh
史蒂文斯理工学院 副教授
Sergiy Butenko
德克萨斯农工大学
Oleg Prokopyev
苏黎世大学
摘要
Abstract
给定一个顶点加权无向图，其顶点和边具有阻塞成本，我们寻求一个顶点和边的最小阻塞成本子集，使得中断图中任何γ拟团的权重最多为某个预定义的阈值参数。𝛾∈（0,1]的值
指定了网络中感兴趣的内聚顶点群的边密度。所考虑的加权γ-拟团阻断问题可以被视为先前文献中研究的团阻断问题的几个变体的自然推广。从应用程序的角度来看，这种设置的主要动机是破坏对抗性（“黑暗”）网络（例如社交或通信网络）的问题，其中γ-准派系代表了我们想要瓦解的“紧密结合”的对手群体。我们首先解决这个问题的理论计算复杂性。然后，我们利用其可行解的一些基本特征来推导线性整数规划（IP）公式。这种线性IP模型可以使用懒惰的分支和切割方案来求解。我们还提出了一种组合分支定界算法来解决这个问题。使用随机生成和真实网络的试验台研究了所开发的精确解方案的计算性能。最后，还使用一个众所周知的恐怖主义网络例子提供了一些有趣的见解和观察。
顶刊数据展示
高级、永久会员数据展示
