  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.
