论文标题
群间传输控制使用图模式屏障
Inter-cluster Transmission Control Using Graph Modal Barriers
论文作者
论文摘要
在本文中，我们考虑了跨图的传输问题，以及如何用有限的资源有效控制/限制它。传播可以代表跨社交网络的信息转移，恶意病毒在计算机网络中传播，或传播传染病在社区中传播。关键的见解是根据图形在降低图中两个或更强烈的连接簇之间的连接方面的作用，将适当的权重分配给图形的瓶颈边缘。有选择地降低临界边缘上的权重（意味着降低的传输速率）有助于限制从一个群集到另一个群集的传输。我们将其称为屏障权重，它们的计算是基于图拉普拉斯图的特征向量。与图形分区和聚类方面的其他工作不同，我们通过将权重分配给边缘而不是执行离散图切割来完全避免关联的计算复杂度。这使我们能够就提出的方法提供强大的理论结果。我们还开发了近似值，可以使用图表上仅使用邻域通信对屏障重量进行低复杂度分布。
In this paper we consider the problem of transmission across a graph and how to effectively control/restrict it with limited resources. Transmission can represent information transfer across a social network, spread of a malicious virus across a computer network, or spread of an infectious disease across communities. The key insight is to assign proper weights to bottleneck edges of the graph based on their role in reducing the connection between two or more strongly-connected clusters within the graph. Selectively reducing the weights (implying reduced transmission rate) on the critical edges helps limit the transmission from one cluster to another. We refer to these as barrier weights and their computation is based on the eigenvectors of the graph Laplacian. Unlike other work on graph partitioning and clustering, we completely circumvent the associated computational complexities by assigning weights to edges instead of performing discrete graph cuts. This allows us to provide strong theoretical results on our proposed methods. We also develop approximations that allow low complexity distributed computation of the barrier weights using only neighborhood communication on the graph.
