key: cord-0480573-ahdrez5w
authors: Zhang, Leiming; Sadler, Brian M.; Blum, Rick S.; Bhattacharya, Subhrajit
title: Inter-cluster Transmission Control Using Graph Modal Barriers
date: 2020-10-09
journal: nan
DOI: nan
sha: 447e819692d400d3dbad8168ca9d2dd5f08a99a0
doc_id: 480573
cord_uid: ahdrez5w

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.

W E consider transmission or flow control across a graph with the aim of lowering the rate of transmission from one cluster (a strongly-connected subgraph) to another. This is an important problem in many different contexts. In computer networks, for example, this may represent the transmission of a virus between computers, and hence the problem is to limit its spread from one sub-network to another. In the context of an epidemic or pandemic this represents the problem of controlling/slowing the transmission of a commutable disease from one community to another. The premise of this work is based on identifying the relatively weak inter-cluster edges, and restricting flow/transmission across those edges.

We use eigenvectors of a graph Laplacian for identifying edges that form weak connections between well-connected clusters within the graph. Instead of determining the cuts in the graph explicitly, we compute values, called resistance, that indicate the potential of an edge of being an inter-cluster edge (as opposed to an intra-cluster edge). This gives us a means of adjusting flow/transmission rates across edges that prevent or slow down transmission from one cluster to another. We provide strong theoretical results to that end, and describe a decentralized algorithm that can be used to compute the edge resistances in a distributed manner through neighborhood communication only.

Graph clustering and partitioning are well-researched topics in graph and network theory. In [2] the authors use the Cheeger constant as a measure of a graph bottleneck and solve the clustering problem by formulating it as a linear program. This method also allows reducing the bottleneck by adding additional relay nodes and links, but the overall time complexity is relatively high. In [6] , eigenvectors of the graph Laplacian are used for partitioning of circuit netlists. This is a similar approach to our work. However, the authors didn't go beyond the second smallest eigenvalue and corresponding eigenvector. A method is proposed in [9] that approximately obtains Fast Fourier Transforms on graphs using the graph Laplacian matrix and eigenvector matrix. In the context of image segmentation, [14] developed a graph partitioning and segmentation method using more than one eigenvector of of the graph Laplacian, and the idea was further developed for multi-layer graphs [4] . However, when using multiple eigenvectors, this approach requires a separate clustering methods, such as k-means. Furthermore, the cluster assignment (i.e., determination of the cuts) is a binary/discrete process. We, on the other hand, assign numerical values to those edges representing weak connections between strongly-connected clusters, which is more suitable for applications such as inter-cluster transmission control. Online multi-agent optimization methods can be used to form local consensus within larger graphs [8] , and these methods have some similarity to the approach presented in this paper. An ordered transmission approach is proposed in [1] to test the covariance matrix of Gaussian graph model where the global transmissions can be reduced without compromising performance, which is particularly effective for graphs that have sparsely connected clusters. Graph clustering can also be related to discrete and continuous time dynamic processes on graphs such as diffusion and epidemics using a Z-Laplacian framework [15] . Identifying critical edges may also be a precursor to placement of protection nodes whose purpose is to stop cascading network failures [17] .

While the Fiedler vector (the eigenvector corresponding to the first non-zero eigenvalue of the graph Laplacian) has been used to partition a graph into two parts [3] , [6] , we make use of the entire spectrum of the Laplacian to control flow between multiple clusters in a graph. Even in prior work where multiple eigenvectors have been used for graph partitioning/clustering ( [14] , [4] use the top K eigenvectors in the context of image segmentation), very little theoretical guarantees have been provided for multi-way graph partitioning using the eigenvectors. This is partly because the set of all possible partitions or cuts arXiv:2010.04790v1 [cs.SI] 9 Oct 2020 of a graph is extremely large and designing algorithms that find the best partitioning have high computational complexity. We circumvent this issue by not seeking to construct explicit partitions using the eigenvectors of the graph Laplacian. Instead, we assign values (called resistance) to each edge that indicates the potential of an edge for being a cut in the optimal partitioning. These resistances can thus be considered a continuous, real-valued proxy for the discrete cuts, and are then sufficient for establishing cost/weight barriers that can be used to restrict flow/transmission across the graph, and in particular, restrict the transmission from one cluster to another. We also develop a decentralized method for computation of the resistance values through distributed, neighborhood connection only. Our numerical evaluation demonstrates how our approach can slow inter-cluster transmission more effectively compared to baseline methods.

While a dual problem of strengthening the bottleneck edges (inter-cluster edges) may also be considered (e.g., by adding more edges or increasing the weights on the bottleneck edges), in this paper we only consider the problem of restricting intercluster flow by means of weakening those edges. However, the methods we propose can be adopted for regulating or increasing flow, as well. Furthermore, the problem we consider seeks to restrict connectivity, which is in sharp contrast to that required for consensus on a graph [11] , [7] . Our objective is to restrict transmission on a graph instead of allowing information flow to happen, which is essential for consensus attainment.

The paper is organized as follows: In Section II we provide background on the graph Laplacian, including some known properties of its spectrum. In Section III-A we first provide a general intuitive description of how the first q eigenvalues and eigenvectors of the graph Laplacian can be used for identifying clusters in a graph. Following that, in Sections III-B we provide mathematical underpinning for the said intuition, formally defining what is meant by strongly-connected clusters, how to quantify the weakness of inter-cluster connections, and why the first q eigenvectors of the Laplacian provides a description of such clusters. In Section IV we describe how the eigenvectors can be used to compute the resistance values on the edges, and in Section IV-B we describe two approximations that allow distributed computation of the resistance. Finally in Section V we describe models of transmission over a network and how the resistances can be used for slowing the intercluster transmission rate. Numerical results are presented in Section VI. Conclusions are presented in Section VII. Fig. 3 : Illustration of how a transition from a graph with two connected components (a) to a connected graph with a weak connection between two strongly connected components (b-d) changes the eigenvalues. Eigenvalues of the respective graph Laplacians are shown directly below the graphs. (a) has 2 separated components without any connection in between (equivalently, zero weight on the inter-component edge). All other weights on the edges are set to 1. In graphs (b), (c) and (d), we add an inter-cluster edge with increasing weights of 0.01, 0.1 and 1 respectively. As a result the second smallest eigenvalue increases gradually but stays relative small.

For a given undirected graph, G, with vertex set V(G) = {v 1 , v 2 , · · · , v n } and weighted edges, a weighted adjacency matrix, A, is defined such that the (i, j)-th element of the matrix is the weight of the edge (v i , v j ) if the edge exists, or 0 otherwise. The weighted degree matrix, D, of the undirected graph is a diagonal matrix with k-th diagonal element being the summation of row k (or column k) of the adjacency matrix A. Finally, the Laplacian of the undirected graph is defined as

The spectrum of the Laplacian matrix has been a topic of intense study in network theory. The eigenvalues of the Laplacian are non-negative and the number of connected components of a graph is equal to the dimension of the null space (the multiplicity of the zero eigenvalue) of the Laplacian matrix. For a single connected graph, the second smallest eigenvalue (often referred to as the Fiedler value [5] ) indicates how connected the graph is. Throughout the paper, we denote 0 = λ 0 ≤ λ 1 ≤ λ 2 ≤ · · · ≤ λ n−1 as the eigenvalues of L and u 0 , u 1 , · · · , u n−1 as corresponding orthogonal unit eigenvectors (in case of eigenvalues of multiplicities greater than 1, we select an arbitrary orthogonal basis in the corresponding eigenspace as the eigenvectors).

An eigenvector of a graph Laplacian, L, can be interpreted as a real-valued distribution over the vertex set (u ∈ R n ). So, the i-th element of an eigenvector u corresponds to the value on vertex v i . We refer to these distributions (corresponding to the different eigenvectors of the Laplacian) as modes of the graph. Figures 1 and 2 show examples of such modes and corresponding eigenvalues.

Building on the previous discussion, one can expect that in a single connected graph with weakly connected components, the eigenvectors corresponding to the smallest eigenvalues would correspond to relatively uniform distributions over each strongly connected component (or cluster) in the graph. This is illustrated in Figure 3 . Starting from 2 isolated clusters (in which case the zero eigenvalue has multiplicity of two), and then adding a weak edge between the two clusters and gradually increasing the weight of the edge, one of the two zero eigenvalues gradually increases to attain low positive values.

We consider the eigenvectors corresponding to the smallest eigenvalues to qualify the structure of the graph and identifying strongly-connected components. In particular, we identify jumps or gaps in the ordered set of eigenvalues to determine which eigenvalues are to be considered as small.

In the example of Figure 1 , there are 2 big clusters (upper left and lower right in the figure). As a result, a linear combination of the first two modes, u 0 and u 1 , will give a distribution that is almost-uniform over the clusters. There are also 5 smaller sub-clusters in the same example which can likewise be readily identified from linear combinations of u 0 to u 4 . In Figure 1 (g), the gap between λ 4 and λ 5 is relatively large indicating there are 5 well-defined clusters within the 2 primary clusters in the graph. Note that a small cluster circled in Figure 1 (f) is also captured and its eigenvalue λ 5 is relatively larger compared to the first 5 eigenvalues due to its smaller scale. However, since this is the last well identified cluster, there is an even larger gap between λ 5 and λ 6 .

In the example of Figure 2 (b), there are 2 large clusters. This is once again manifested in the fact that there is a relatively large jump/gap ("gap 1") in the value of eigenvalues after the first two eigenvalues (i.e., a gap between λ 1 and λ 2 ). A second gap ("gap 2" between λ 2 and λ 3 ) corresponds to a smaller scale cluster circled in Figure 2 (c). An absence of any relatively large gap following the third eigenvalue indicates the absence of any other significant cluster or sub-cluster in the graph.

The qualitative introduction and general observations about the first q eigenvectors representing the clusters in a graph are formalized by the following development leading to Proposition 1.

1) Mode-based Representation of Clusters: We first formalize the notion of eigenvectors representing clusters in Definition 1, followed by a formal description of stronglyconnected clusters with weak inter-cluster connections. The relationship between these two definitions is then established in Proposition 1. We start by describing some notation.

Suppose a graph G is cut into q disjoint sub-graphs, G 0 , G 1 , · · · , G q−1 , to construct the q-partitioned sub-graph,

, or more compactly, G = ∪ q−1 j=0 G j , so that G has at least q connected components (each of G j , j = 0, 1, · · · , q−1). We denote the set of the sub-graphs themselves that constitute the partition by G = {G 0 , G 1 , · · · , G q−1 }.

Let N = {u 0 , u 1 , · · · , u q−1 } be the set of normalized (unit) vectors such that u j ∈ R n (for 0 ≤ j ≤ q − 1) corresponds to a uniform positive distribution on the vertices of the sub-graph G j and zero on all other vertices. The vectors in N thus form an orthogonal set in the null-space of the Laplacian, L, of G. Let the set of all other orthogonal unit eigenvectors of L be N ⊥ = {u q , u q+1 , · · · , u n−1 }, so that span(N ) and span(N ⊥ )

are orthogonal subspaces, and N ∪ N ⊥ spans the entire R n .

Let the set of orthogonal unit eigenvectors corresponding to the lowest q eigenvalues of the Laplacian, L, of G be N = {u 0 , u 1 , · · · , u q−1 } (the first q modes). Let the set of all other orthogonal unit eigenvectors of L be N ⊥ = {u q , u q+1 , · · · , u n−1 }.

[q-modal Distance from a q-partitioned Graph] The q-modal distance of G from the partitioned graph G (i.e., the distance of the first q modes of G from the uniform distributions over the sub-graphs in G = {G 0 , G 1 , · · · , G q−1 }) is then defined as 1

1 The second equality in (1) holds because of the following: For orthonormal basis {u 0 , u 1 , · · · , u n−1 } and {u 0 , u 1 , · · · , u n−1 }, either of which span R n , we have

Key Property of q-modal distance: It is easy to observe that the q-modal distance is zero if and only if span(N ) = span(N ) -that is, the first q eigenvectors, u 0 , u 1 , · · · , u q−1 , of L, are linear combinations of u 0 , u 1 , · · · , u q−1 , thus corresponding to distributions that are uniform over the vertices of each of the sub-graphs G 0 , G 1 , · · · , G q−1 . More generally, modaldist G ( G) measures how far the first q modes of G are from the distributions which are uniform over the vertices of G 0 , G 1 , · · · , G q−1 .

Suppose the weights on the outgoing 2 edges from the subgraph H of G are w 1 , w 2 , · · · , w m H (i.e., these are the weights on the edges connecting a vertex in H to a vertex not in H). We define the relative outgoing weight of H in G as

where |V(H)| is the number of vertices in H and A is the adjacency matrix of G. Thus relout G (H) is smaller for subgraphs that are large and are weakly-connected to the rest of the graph.

[Average Relative Outgoing Weight of a q-partitioned Graph] Given a q-partition of G, G = {G 0 , G 1 , · · · , G q−1 }, its average relative outgoing weight is defined as the root mean square of the relative outgoing weights of the sub-graphs:

where λ q is the (q + 1)-th eigenvalue (in order of magnitude) of the Laplacian, L, of G.

Remarks on Proposition 1: i. As a consequence of the above proposition, out of all possible q-partitions, G = {G 0 , G 1 , · · · , G q−1 }, of G, the one that gives the tightest upper bound on modaldist G ( G) is the one in which the average relative outgoing weight is the lowest. In particular,

where min G implies minimization over all possible qpartitions of G.

ii. Considering the sub-graphs, {G j } j=0,··· ,q−1 , as the clusters, this also implies that if there exists a q-partitioning of the graph such that the relative outgoing weights of each sub-graph (cluster) are small (i.e., the intercluster connections relative to the size of the clusters are weak), then the q-modal distance of the graph from that partition will be small, i.e., the first q modes of the graph, G, will be close to distributions that are uniform over each of the sub-graphs G j , j = 0, 1, · · · , q − 1.

2) On the Existence of the "gap":

A q-partition that satisfies the above condition is called an α-realizable q-partition.

A graph that admits a well-defined q-partition (i.e., a qpartition with weak inter-cluster connections, and hence low avgrelout G ( G)) will thus have an α-realizable q-partition for a small value of α. In particular, we say a graph is qpartitionable only if it admits an α-realizable q-partition for α ∈ [0, 1). Also, note that if G is an α-realizable q-partition, then it implies that it is also an α -realizable q-partition for any α ≥ α. The lowest value of α for which G is

λq argmin G (avgrelout G ( G))) thus gives a topological characterization of the graph. A low value implies that the graph is well-clustered and allows a good q-way partitioning.

Suppose we consider the eigenvectors corresponding to the first q eigenvalues of the Laplacian, L, of the graph G. Assuming that in a q-partition the q strongly-connected clusters in the graph are connected to each other by weak inter-cluster connections, then based on the development in Section III-A it is expected that λ 0 , λ 1 , · · · , λ q−1 are small (see Figure 1 (g)). This observation is formalized by the following proposition.

Assuming G admits an α-realizable q-partition for a small value of α(< 1), the key insight from the above proposition is that λ q−1 will be small compared to λ q , giving the formal underpinning for the eigenvalue gaps as discussed in Section III-A and illustrated in Figure 1(g) .

3) Sensitivity of Modal Shapes to Edge Weights: As a result of the above, if avgrelout G ( G) and hence α are small (close to zero), the vector space spanned by u 0 , u 1 , · · · , u q−1 is very close to being a degenerate eigenspace (nullspace) of L with eigenvalues bounded above by αλ q 1 − α 2 . Furthermore, Proposition 1 indicates that a small avgrelout G ( G) results in a small modaldist G ( G), which implies that u 0 , u 1 , · · · , u q−1 are distributions that are close to linear combinations of the distributions that are uniform over each G j (the distributions corresponding to u 0 , u 1 , · · · , u q−1 ). However, the proposition does not give any indication of the exact nature of the linear combination of u 0 , u 1 , · · · , u q−1 that is closest to u 0 , u 1 , · · · , u q−1 which generally depends on the specific value of the weights on the inter-and intra-cluster edges.

As described in the previous section, the modes corresponding to the smallest q eigenvalues prior to a relatively large jump or gap in the ordered set of eigenvalues form the basis for identifying clusters in a graph. While it may be challenging to determine the value of q just from the ordered set of eigenvalues (in fact in graphs without well-defined clusters there may not even exist a well-defined gap in the ordered set of eigenvalues), for the purpose of discussion in this section we will assume that the value of q and the first q eigenvectors of L are given.

As a consequence of Proposition 1, each of the first q eigenvectors correspond to modes with relatively uniform distributions over each strongly connected cluster of the graph with a well-defined q-partition (small average relative outgoing weight). Given that we have q linearly independent modes, each with almost-uniform values over the clusters, the uniform value on each cluster differs from the uniform values on its neighboring clusters in at least one of the modes. Consequently, the difference of values across edges that connect clusters will be non-zero in those modes (we call these the inter-cluster barrier edges), while inside each cluster differences across edges will be very close to zero because of the intra-cluster uniformity. 1) Gradient of u: We denote the edge set of the graph as E(G) = {e 1 , e 2 , · · · , e m } and give every edge an arbitrary direction. For a given distribution u ∈ R n on the vertices, the difference of values on two vertices across an edge e k connecting vertices v i , v j ∈ V(G) is interpreted as the "gradient" of the distribution on the graph. The gradient yields a realvalued distribution over the edge set and can thus be written as a vector d ∈ R m in which the k-th element corresponds to the value on edge

and can be expressed as d k = u j − u i . More concisely, the gradient can be written as

where u ∈ R n is a column vector, and B ∈ R n×m is the incidence matrix in which the (i, k)-th element is defined as

This is illustrated in the example of Figure 4 which shows a modal distribution and the gradient values labeled on each edge. The inter-cluster edge has relatively large gradient value (0.659) while the gradients over the intra-cluster edges are much smaller (order of 10 −3 ).

Because of the arbitrary direction assigned to edges, a gradient can be positive or negative. Thus, to identify the edges that separate the clusters, we square the individual elements of the gradient vector to obtain vector r = [d 2 1 , d 2 2 , · · · , d 2 m ] T , which is a positive-valued distribution over the edges. We call this the resistance vector or the resistance distribution over the edges, and it is easy to observe that it can be compactly written as Figure 5 shows an example of the resistance vector for u 1 .

The value of the inter-cluster edge is significantly higher and readily identified.

2) Aggregated Resistance from Gradient of First q Modes: Define the resistance vector corresponding to the l-th mode, u l , as In order to determine all the barrier edges from the first q modes we aggregate the resistances from the vectors r l , l = 0, 2, · · · , q − 1 to define the q-aggregated resistance as

is the n × q matrix with the columns corresponding to the first q eigenvectors of L. Figure 6 shows an example ofȓ. The inter-cluster edges have noticeably higher values than intra-cluster edges. Once these values are computed, we can apply a threshold to values of the vectorȓ to identify the inter-cluster/bottleneck edges.

Due to Definition 1 and Proposition 1, if a graph admits a q-partition with low avgrelout, the columns ofȖ are close to a linear combination of the columns ofȖ = [u 0 u 1 · · · u q−1 ]. Since the columns are all orthonormal, this impliesȖ Ȗ R for some q × q orthogonal matrix R. Thus we observe that UȖ T Ȗ RR TȖ T =ȖȖ T is independent of the exact nature of the linear combination. This shows that the resistance vector,ȓ, is independent of the exact nature of the linear combination of the distributions that are uniform over the subgraphs {G j } j=0,1,··· ,q−1 that constitute the low-eigenvalue modes (see Section III-B3). This general observation is formalized in the following proposition.

Consider graphs G and G with the same topology (i.e., same vertex and edge sets, but possibly different edge weights) such that both permit the same q-partition, G, that is α-realizable in both the graphs for some α ∈ [0, 1). Let the resistance vectors for the two graphs beȓ andȓ respectively. Then

where d max is the maximum degree over the vertices of either of the graphs.

Proof. See Appendix C.

The computation ofȓ in Equation (9) requires the computation of eigenvectors and eigenvalues, and determining how many eigenvectors (q) to be used in computingȖ . In this section we propose an approximation that does not require explicit eigendecomposition of L and is amenable to distributed computation. Furthermore, the choice of q is replaced by the choice of a parameter, , that is directly related to the desired value of avgrelout G ( G).

1) Approximation for Mode-independent Computation: The following proposition establishes that for a low value of q (compared to n) and an appropriately chosen value of , if there exists a well-defined q-partition of the graph, thenȖȖ T can be reasonably approximated by ( I + L) −1 . We call this the approximation for mode-independent computation. Proposition 4. Given a desired value for an average relative outgoing weight, a, suppose there exists a q-partition, G, such that i. G is α-realizable with some α ∈ [0, α], and, ii. avgrelout G ( G) ∈ [β a, a/β] for some β ≤ 1 (i.e., the actual average relative outgoing weight of the partition is within a β proportion of the desired value of a in either direction).

where · 2 is the matrix operator 2-norm.

Proof. See Appendix D.

As a consequence, if the graph admits a good q-partition for a desired value of avgrelout, and if the value of is chosen appropriately, the q-aggregated resistance vector in (9) can be approximated as

This approximation automatically factors out the influence from eigenvectors corresponding to larger eigenvalues and only relies on the contribution for the first q eigenvectors. Figure 12 (b) illustrates an example in computation of the resistance vector using this approximation.

2) Approximation for Distributed Computation: The computation of the inverse of the matrix ( I + L), and hence the approximated resistance vector,ȓ, as described above is not immediately distributable. For distributed computation, we note that I + L = ( I + D) − A, where I + D is a diagonal matrix and A is the weighted adjacency matrix. We define the left-normalized adjacency matrix as A = ( I + D) −1 A. ( I + L) −1 can then be further approximated as

The convergence of the infinite sum in the Neumann series above, and hence the approximation using the partial sum in the last step, is formalized in the following proposition:

where d max is the maximum degree over the vertices of the graph.

Proof. Part 1: Since the elements of A are all positive,

Part 2:

Thus, lim N →∞ S N ∞ ≤ 1 1−ρ . Furthermore,

Thus the partial sums, S N , get closer to S ∞ exponentially fast as the value of N increases.

The consequence of the above proposition is that the qaggregated resistance vector can be further approximated as

where A = ( I + D) −1 A. We next discuss how the computation ofȓ aprox-II can be distributed over the graph.

Since ( I + D) is a diagonal matrix and A is the adjacency matrix, the computation of the t-th power of A = ( I + D) −1 A is amenable to distributed computation. In order to describe the distributed computation algorithm we observe that the (i, j)-th element of A t+1 can be written as

where

indicates the set of vertices that are neighbors of the i-th vertex. The second equality in (16) 

In a distributed computation, the vertex i will store only the elements of the i-th row of A t and the computation of the ith row of the partial sum matrix, Sp := p t=0 A t . In practice each vertex can maintain associative arrays for the rows, which are populated as new non-zero entries are computed. This is illustrated in Algorithm 1.

Suppose the k-th edge connects the i-th to the l-th vertex (i.e., v l ∈ N G (v i ) and e k = (v i , v l ) ∈ E(G)). Using the iand l-th rows of the partial sum matrix, Sp, stored on vertices i and l respectively, and using their respective degrees, the resistance on the edge (the k-th component of the resistance vector) can be computed in a distributed manner as follows: for {l | v l ∈ N G (v i )} do // communicate w/neighbors 9: while t l < t i do wait // wait for latest data 10: for (j : s j ) ∈ APow l do 11:

done i ← t i + 1 13: for {l | v l ∈ N G (v i )} do // wait for neighbors 14: while done l < t i + 1 do wait APow i ← APowTmp i

t i ← t i + 1 16: for (j : s j ) ∈ APow i do // update partial sum 17: if Sp i [j] does not exist then while t l < p do wait

where the first approximation follows from Equation (9), Proposition 4 and Equation (12) , and the simplification of the summation domain from every pair of vertex indices to {i, l} is due to the fact that B ck is zero for any c / ∈ {i, l}. The important thing to note here is that this approximate computation of the resistance on the k-th edge requires only values stored on its bounding vertices, thus making this computation distributable as well. The complete algorithm for the distributed computation of the resistances is described in Figure 12 (c) illustrates a result in computation of the resistance vector using this distributed implementation.

For a given graph and weighted Laplacian matrix, L = D − A (where A is the weighted adjacency matrix, and D the corresponding diagonal degree matrix), consider the following dynamics on the grapḣ

where x ∈ R n corresponds to a distribution over the vertices of the graph. A first-order discrete time form of equation (18) can be written as

where τ ∈ R is the continuous time, while t ∈ Z is the (rescaled) discrete time. κ 2 λn is a small number chosen to ensure that (I − κL) has the same eigenspace as L, but its highest eigenvalue is 1 corresponding to the eigenvector u 0 , while all other eigenvalues are in (−1, 1) .

As t → +∞, x (+∞) thus converges to the first eigenvector, u 0 , of L, which corresponds to a uniform distribution over the vertices. The effect of the dynamics is diffusion -starting with any non-zero distribution x (0) , the dynamics of (18) or (19) ends up re-distributing the values on the vertices to their neighbors until an equilibrium (uniform distribution) is attained. In fact the dynamics in (18) can be written aṡ

In this form it's easy to see that the diffusion rate from v j to v i (i.e., across the edge (v i , v j )) is determined by the weight on the edge, A ij (the (i, j)-th element of the weighted adjacency matrix). The lower the rate, the slower the diffusion across the edge. Furthermore, it is clear that the dynamics required only neighborhood communication/transmission, since updating x i requires the values of x j for only the neighbor indices in

We thus use this as a model for network transmission (such as information in a communication network context, or infection in context of disease spread) in the network. The entity being transmitted is represented by the values of the elements of x, with X k denoting the value on vertex v k .

In particular we consider the situation where the entity being transmitted originates from one particular start vertex, v start (i.e., the k-th element of

. We are interested in studying (and reducing) the time taken by the dynamics to make the value on a target vertex, v target (belonging to a different cluster than v start ), go above a threshold value of γ, And we refer to the value of the target vertex v target as x target . Figure 7 shows an example of start and target vertices for transmission on a simple graph.

For the edge weights modeling the dynamics (elements of the weighted adjacency matrix that govern the dynamics (20)) we consider three different cases:

i. Unrestricted Transmission: In this case we set a uniform unit weight for every edge in the graph. The corresponding adjacency matrix, degree matrix and the Laplacian matrix are denoted by A U , D U and L U . The (continuous-time) dynamics of unrestricted transmission is thusẋ = −L U x. ii. Inter-cluster Barriered Transmission: In order to reduce transmission across the network we propose to decrease weights on selected edges (reducing the rate of transmission across those edges). For this approach, we use the resistance vector computed using the Laplacian for unrestricted transmission, L U , to compute new weights.

In particular, ifȓ k is the resistance computed for the k-th edge, we define the new barrier weights as

where 0 < B 1 is a small positive constant. These barrier weights thus take values in (0, 1] and edges with computed resistance close to 0 (such as the intra-cluster edges) have barrier weights close to 1, while the barrier weights are lower for edges on which the computed resistance is high (for example the inter-cluster edges) 3 . The corresponding adjacency matrix, degree matrix and Laplacian are thus

The (continuous-time) dynamics of transmission with inter-cluster barrier is then defined asẋ = −L B x. iii. Shuffled Weight Transmission: In order to be able to compare/benchmark the performance of the barriered transmission described above, we randomly shuffle the barrier weights as computed in (21) across the different edges of the graph. We define shuffled weight on the k-th edge as w S k = w B σ(k) , for some permutation, σ, of (1, 2, · · · , m). The corresponding adjacency matrix, degree matrix and Laplacian matrix are denoted by A S , D S and L S , and the (continuous-time) dynamics of transmission with shuffled weights is defined asẋ = −L S x. If we regard decreasing the weight on an edge below 1 as consuming a certain amount of available resource, the simple shuffling of the weights ensure that the same amount of resource is being used in lowering the weights (i.e., the same number of edges with the same weights as in the barrierred transmission case), but the edges are chosen randomly without using our method for modebased barrier construction. This gives a baseline method to compare against.

We compare the performance of our method in detecting inter-cluster edges with a recent algorithm [2] based on multiway Cheeger partitioning that uses an integer linear programming formulation to find partitions. For this algorithm, the number of clusters is required as input and, for a total of q clusters and n vertices, the first q − 1 clusters are required to contain less than an average of n/q vertices. This requirement affects the accuracy of the bottleneck detection as shown in the example of Figure 8 . In this case, some vertices are forced to be separated from their well-aggregated cluster due to the vertex count limit per cluster, resulting in suboptimal inter-cluster edge detection. Furthermore, because of the integer linear programming implementation, the multiway Cheeger partition algorithm took 54, 304.6 seconds to compute the partitions in this particular example on an intel cpu. In comparison, our method took less than one second to compute the resistance,ȓ, on the edges using (9) , and the result is shown in Figure 6 . [2] . The method is less accurate in clustering and significantly more computationally complex than our proposed resistance computation, illustrated in Figure 6 (see text Section VI-A). 

A comparison of transmission rates using the different weight assignment methods described in Section V-B is shown in Figure 9 . As can be seen from the plot, the value of x target grows significantly slower when using the Barriered transmission weights than using the Unrestricted transmission weights or the Shuffled weights. While eventually any nonzero weights will result in convergence to a uniform distribution (corresponding to the null-space vector of either of L U , L B or L S ), the objective of slowing the rate of transmission using the barriered weights is clearly achieved.

For a large scale network graph example, we use an open network dataset called ego-Facebook from the Stanford Large Network Dataset Collection [10] . This anonymized social network has 4039 nodes and 88234 edges in total. As shown is Figure 10 , there is a big gap between λ 6 and λ 7 for this network. We choose q = 7 in Equation (10) to construct our barrier weighted graph Laplacian. We also choose node #1 as the start vertex and node #4038 as the target vertex for information transmission across the network. The simulation result in Figure 11 shows a similar trend as the result of the small scale simulation (Figure 9 ). The barrier edge weights are able to slow the information transmission effectively.

We use 3 different methods for computingȖȖ T for computing the resistance vector,ȓ, in equation (9) . The first is the direct eigen-decomposition of the graph Laplacian for computingȖ . The second is the approximate method for mode-independent computation as was described under Section IV-B1. And finally we use the approximation method for distributed computation as was described in Section IV-B2. Figure 12 shows the results obtained on a simple graph using these three methods. As can be seen from the value of ȓ aprox-I −ȓ , the result using the approximation methods for mode-independent computation is very close to the direct computation. The advantage of the approximation is that it can be computed in a decentralized manner, which is especially useful when dealing with a large scale graph whose nodes have limited computational resources and communicate only with edge-connected neighbors.

As of writing this paper, our world is undergoing the COVID-19 pandemic. Social restriction has been shown to be a proven way of slowing the spread of the virus and providing time for treatment and eradication measures [12] . From our previous simulations, we can already see how effective the graph modal barriers are for slowing transmission across a network. We thus apply the method developed in this paper to a pandemic model that can lower the probability of virus transmission along inter-cluster connections. In this context a cluster can be a representation of a closely-knit community of individuals (e.g, with a vertex representing a household and the flow representing interaction/travel of individuals). Thus, given limited resources for imposing restrictions on travel or social interactions, identifying the most critical edges that predominate in transmitting the virus from one community to another (as is done by the proposed modal barrier method) is essential.

For the simulation, the daily contagious probability of the k-th edge, e k = (v i , v j ) (i.e., the probability that v j will get infected if v i is infected), is assumed to be

where P a is a constant which is set to be 0.03. The lower the weight on the k-th edge, the lower is the probability of transmission.

Initially we start with only one infected vertex ("patient zero"). Once infected, a vertex will turn contagious in a range of 3 to 5 days, and will stay infected for a range of 15 to 70 days. We compare the results with uniform unrestricted weights, w U k (= 1 ∀k), barriered weights, w B k , and shuffled weights, w S k . Results for the ego-Facebook network are shown in Figure  13 . Figure 14 shows some snapshots on the spread of the infection across the example graph shown in Figure 6 .

In this paper we used the eigenvectors of the graph Laplacian to construct modal barrier weights on the edges of a graph to lower the transmission rate on those critical edges. Our method relies on using the eigenvectors to identify clusters in the graph and hence the edges that form weak intercluster connections form the basis of preventing inter-cluster transmission. We provided theoretical foundations for the proposed method and developed an approximation that enabled low complexity distributed computation of the barrier weights. We demonstrated that the proposed method is more effective in slowing transmission across a network compared to a method that uses the same amount of resources in lowering the edge weights but does so in a randomized manner. We discussed the applicability of the proposed method in deciding how to impose social distancing and travel restrictions in preventing transmission of infection across communities.

We use the same notations as in Definition 1, Definition 2 and Proposition 1.

Proof. Suppose D k and D k are the degrees of the vertex v k ∈ V(G j ) in the graphs G and G respectively. Then D k and D k are equal iff all the neighbors of v k are in G j . Otherwise

Suppose A and A are the adjacency matrices of G and G. An edge (v k , v l ) exists (and have the same weight, i.e., A kl = A kl ) in both G and G iff v k and v l belong to the same sub-graph. Otherwise A kl = 0 (the edge is non-existent in G). Thus,

(25) Next we consider the vector u j (for j = 0, 1, · · · , q − 1), which by definition is non-zero and uniform only on vertices in the sub-graph G j . Let u lj be the l-th element of the unit vector u j . Thus,

Thus the k-th element of the vector (L − L)u j ,

(since D and D are diagonal marices)

(using the definition of u lj ) 

Thus,

=2 (reloutG(Gj)) 2 (28)

Proof. For any j ∈ {0, 1, · · · , q − 1}, forms an orthogonal basis.)

From the above,

Thus, using the above and Lemma 1,

Since the above is true for any j ∈ {0, 1, · · · , q − 1},

B. Proof of Proposition 2 Proposition 2

Proof. Since (29) is true for any j ∈ {0, 1, · · · , q − 1},

Using Lemma 1, 

n−1 l,l =q (u T j u l )(u T l u l )(u T l u j ) tr(u j u T j )

− (u T j u l )(u T l u j )(u T j u l ) tr(u j u T l ) − (u T l u j )(u T j u l )(u T l u j ) tr(u l u T j ) + (u T l u j )(u T j u j )(u T j u l ) tr(u l u T l ) 

Using a similar analysis we get

Using triangle inequality of Frobenius norm, (36) and (37))

For notational simplicity, define ∆ =ȖȖ T −Ȗ Ȗ T . Suppose the k-th edge connects the a-th and b-th vertices (i.e. e k = (v a , v b ) ∈ E(G)). Then from (9) (39) Thus, 1 4 |ȓ k −ȓ k | 2 ≤ |∆ aa | 2 + |∆ ab | 2 + |∆ ba | 2 + |∆ bb | 2 (since (a + b + c + d) 2 ≤ 2((a + b) 2 + (c + d) 2 ) ≤ 4(a 2 + b 2 + c 2 + d 2 ) for any a, b, c, d ∈ R) (40) We next proceed to sum both sides of the above equation over all edges in G.

In the above equation we observe that, in the sum on the right hand side, terms of the form |∆ ii | 2 appears as many times as there are edges connected to the i-th vertex (i.e., the degree of the vertex). However, terms of the form |∆ ij | 2 (for i = j) appear twice for every edge (v i , v j ) that exists. Thus we have Proof. From the definition ofȖ , since it constitutes of the first q columns of U , we haveȖȖ T = U diag([1 q , 0 n−q ])U T .

Furthermore, ( I + L) −1 = U diag n−1 i=0 ( +λi )U T (since U is the orthogonal matrix that diagonalizes L). Thus, UȖ T − ( I + L) −1 = U diag 1− +λ0 , 1− +λ1 , · · · , 1− +λq−1 , − +λq , − +λq+1 , · · · , − +λn−1 U T (41) Furthermore, since the matrices are symmetric their operator 2-norms are the maximum of the absolute values of their eigenvalues. Thus,

Testing the structure of a Gaussian graphical model with reduced transmissions in a distributed setting

Network connectivity assessment and improvement through relay node deployment

Spectral Graph Theory

Clustering with multi-layer graphs: A spectral perspective

Algebraic connectivity of graphs

New spectral methods for ratio cut partitioning and clustering

Consensus and Synchronization in Complex Networks

Proximity without consensus in online multiagent optimization

Approximate fast graph fourier transforms via multilayer sparse approximations

SNAP Datasets: Stanford large network dataset collection

Distributed Algorithms

Evaluating the effectiveness of social distancing interventions to delay or flatten the epidemic curve of coronavirus disease

Normalized cuts and image segmentation

Graph filters and the Z-Laplacian

Functional Analysis

Averting cascading failures in networked infrastructures: Poset-constrained graph algorithms