Optimizing the Coherence of Composite Networks
Erika Mackin Stacy Patterson




The 2.4 μm Galaxy Luminosity Function as Measured Using . II. Sample Selection
    S. E. Lake1, E. L. Wright1, R. J. Assef2, T. H. Jarrett3, S. Petty4, S. A. Stanford5,6, D. Stern7,  C.-W. Tsai1,7
    December 30, 2023
=====================================================================================================================

empty
empty




We consider how to connect a set of disjoint networks to optimize the performance of the resulting composite network.
We quantify this performance by the coherence of the composite network, which is defined by an H_2 norm of the system.
Two dynamics are considered: noisy consensus dynamics with and without stubborn agents. 
For noisy consensus dynamics without stubborn agents, we derive analytical expressions for the coherence of composite networks in terms of the coherence of the individual networks and the structure of their interconnections.  We also identify  optimal interconnection topologies and give bounds on coherence for general composite graphs. 
 For noisy consensus dynamics with stubborn agents, we  develop  a non-combinatorial algorithm that identifies
connecting edges such that the composite network coherence closely approximates the performance of the optimal composite graph.







§ INTRODUCTION

Networked systems are becoming ever more important in today's highly connected world. We find such systems in power grids, vehicle networks, sensor networks, and so on.  A problem of particular interest is how to coordinate or synchronize these networks, and in addition, how robust this coordination 
or synchronization is to external disturbances.  With an understanding of the relationship between the network topology and this robustness, it becomes possible to modify a network's topology to optimize performance.

In this paper, we study topology design in networks that take the form of  composite graphs. A composite graph is one  that is formed from a set of disjoint subgraphs and a designed set of edges between them. We analyze these networks under two dynamics: noisy consensus dynamics and noisy consensus dynamics with stubborn agents. In both cases, we investigate how to choose edges to connect subgraphs to optimize the network coherence—a performance measure defined by the H_2 norm of the system.
For networks with noisy consensus dynamics and no stubborn agents,  we derive analytical expressions for the coherence of composite networks in terms of the coherence of the individual sub-networks and the structure of their interconnections. We then derive upper and lower bounds for the coherence of general composite graphs. For systems with noisy consensus dynamics with stubborn agents, we prove that coherence is a  submodular function of the edges added to a set of initially disjoint networks, and we use this result to create a greedy algorithm for choosing the connecting edge set for the network. This greedy algorithm yields an edge set that is within a provable bound of the performance of the optimal edge set.



Coherence has been used as a measure of network performance in several previous works, for example, <cit.>. <cit.>, <cit.>,
and <cit.> describe algorithms and analysis for adding edges to an arbitrary graph to improve its coherence.
Modifying the edge weights within a graph is another approach for optimizing network coherence, which is used in <cit.>. In all of these works, however, the authors consider only edge additions or modifications to a single graph.
Our focus, in contrast, is on how best to connect a set of disjoint subgraphs.
A system of interacting networks is considered in the works <cit.>, where the performance is based on robustness to cascading and random failures.
In <cit.>, the authors study the performance of a composite network in terms of the H_2 norm of the system, but they consider different dynamics than those presented in this paper. 






The remainder of this paper is structured as follows. Section <ref> describes our system model. Section III  gives analysis and formulas regarding the coherence of composite networks with noisy consensus dynamics. In Section IV, we consider noisy consensus dynamics with stubborn agents and present our greedy algorithm for connecting edge selection. Section V demonstrates the performance of our algorithm through a pair of numerical examples, followed by our conclusion in Section <ref>.

































§ SYSTEM MODEL
 
We consider a graph consisting of a set of n disjoint subgraphs {G_1, …, G_n}. Each subgraph G_i = (V_i, E_i) is connected and undirected, with n_i nodes.
The objective is to connect these n subgraphs to form a connected composite graph G=(V,E), |V|=N, where:

    V=   V_1∪…∪ V_n 
    
    E =    E_1 ∪…∪ E_n ∪,

where  is a set of undirected edges connecting the subgraphs, i.e.,
 ⊆{(u,v) |  u∈ V_i, v ∈ V_j,  j ≠ i }.
The edge set  is to be selected so as to optimize a desired performance objective. 


The dynamics of each node j ∈ V is given by

    ẋ_j = u_j + ν_j,

where u_j is the control input and ν_j is a zero-mean, unit variance, white stochastic disturbance.
We consider two types of dynamics, described below.  



 §.§ Noisy Consensus Dynamics

We first consider noisy consensus dynamics, where each node updates its state based on the relative states of its neighbors.
The control input is given by:

    u_j = - ∑_k ∈j(x_j - x_k).

The dynamics of the the network G can be written as

    ẋ   = - L  x + ν,

where L is the Laplacian matrix of the composite graph G, i.e.,

    L = [ [ L_1       0;   ⋮   ⋱   ⋮;   0     L_n ]] + L_E_con,

where L_i is the Laplacian  matrix of  G_i, i=1 … n, and L_E_con is the Laplacian matrix of the graph consisting of all nodes in V and only those edges in E_con.


We quantify the performance of the network by the network coherence, which is defined as follows:

    H_C(G):=  lim_t →∞∑_j=1^Nvar(x_j - 1/N∑_k=1^N x_k ).

The network coherence is the total steady-state variance of the deviations from the average of the current node states.
It has been shown that <cit.>:

    H_C(G) = 1/2L^†,

where  L^† is the pseudo-inverse of L.










 §.§ Stubborn Agent Dynamics

We also consider noisy consensus dynamics with stubborn agents.
The nodes execute a consensus law, each with some degree of stubbornness, as defined by the scalar  d_j ≥ 0.
We assume that, in each subgraph, at least one d_j is strictly greater than 0.  
The control input is given by:

    u_j = - ∑_k ∈j (x_j - x_k) - d_j x_j.



The dynamics of the composite network can be written as:

    ẋ   = - Q + ν,

where

    Q = [ [ Q_1       0;   ⋮   ⋱   ⋮;   0     Q_n ]]+L_E_con,

Here, Q_i = L_i + D_i, where D_i is the diagonal matrix of degrees of stubborness for graph G_i, and L_E_con is as defined for the noisy consensus dynamics. 





We again quantify the performance of a graph G by an H_2 norm,  

    H_S(G) = ∫_0^∞ e^-2Qtdt = 1/2 Q^-1.

Note that  if G is connected and at least one d_j > 0, then Q is positive definite <cit.>.

The dynamics in (<ref>) are a variation of the dynamics for noise-corrupted leaders presented in <cit.>, where each node j with d_j>0 plays the role of a leader.  In our system, we allow that any number of agents may be leaders, including every node in the network.
These dynamics can also be given a different interpretation as leader-follower consensus dynamics with noise-free leaders, similar to those presented in <cit.>.  
Let G' be the graph formed from G by adding a single node s  and creating an edge from
 each node j in V to s with edge weight d_j. All other edge weights are equal to 1.
Let node s be the single leader node, with noise-free dynamics, i.e. ẋ_s = 0,
and let all other nodes be follower nodes, governed by the dynamics in (<ref>) with the control input in (<ref>).
Let L' be the weighted Laplacian matrix of G', and let L'_f be the sub-matrix of L' with the row and column corresponding to node s removed.  It has been shown that the total steady-state variance of the deviation from the leader's state is given by <cit.>:

    H_f(G) = 1/2L'_f^-1.

Observing that L' = Q, it holds that H_S(G) = H_f(G).




§ COMPOSITE GRAPHS WITH NOISY CONSENSUS DYNAMICS

We first consider systems with noisy consensus dynamics and no stubborn agents.  For such networks, we refine the definition
of a composite network in the following way. 
For each of the n disjoint subgraphs G_i,
a single node l_i ∈ V_i is used to connect G_i to the other subgraphs.  
We call these nodes bridge nodes. An example of a bridge node connecting two subgraphs is shown in in Figure <ref>. Each composite network G of n subgraphs will accordingly have n bridge nodes, where each l_i is connected to at least one other bridge node l_j.




The backbone graph is the graph defined by the bridge nodes and the edges between them, B=(V_B, E_B), V_B={l_1, …, l_n}, E_B={(l_i, l_j)  | l_i, l_j, ∈ V_B}.  
The edge set E_B corresponds to  in the composite graph.









 Our goal is to analyze the coherence of the composite graph in terms of its subgraphs, bridge nodes, and backbone graph topology. To do this, we exploit the connection between coherence and effective resistance in electrical networks.



 §.§ Resistance in Electrical Networks


Consider a connected graph G=(V,E) with N nodes that represents an electrical network, where each edge is a unit resistor. The resistance distance r(u,v)
between nodes u and v is the potential distance between u and v when a 1-A current source runs between them <cit.>. 
The effective resistance of G is the sum of the resistance distances between each pair of nodes <cit.>:

    Ω_G  = 1/2∑_u,v∈ V_Gr(u,v) = ∑_u<v∈ V_Gr(u,v).






Coherence is related to effective resistance as follows <cit.>:

    H_C(G)=Ω_G/2N.











We use the following lemmas in our analysis.


For any graph G=(V,E), let A=(V_A, E_A) and B=(V_B,E_B) be two subgraphs such that V_A ∪ V_B = V, V_A ∩ V_B = {x}, E_A ∪ E_B = E, and E_A ∩ E_B = ∅. In other words G, is partitioned into two components A and B that share only a single vertex {x}.
The resistance distance between any two vertices u, v with u ∈ V_A and v ∈ V_B is: 

    r(u,v) = r(u,x) + r(x,v).





For all vertex pairs u,v ∈ G, the graph distance d(u,v) is such that d(u,v) ≥ r(u,v), with equality if and only if there is exactly one path between u and v.


In the case of tree graphs, we note that d(u,v)=r(u,v).





 §.§ Coherence in General Composite Graphs

We now analyze coherence for a general composite graph with an arbitrary backbone graph topology. To do so, we make use of the following definition.

Consider graph G = (V, E). The resistance centrality of a node v ∈ V is

    C(v)=∑_u ∈ V  u ≠ vr(u,v).


We observe that resistance centrality is inversely proportional to the information centrality measure defined in <cit.>.
We use  C_i(v_i) to denote the resistance centrality of a node v_i in subgraph G_i, computed only over the subgraph G_i.







 



























Using this definition, we derive a formula for H_C(G)  in terms of the the coherence of the subgraphs, the choice of bridge nodes, and the topology of B.
 
 
Consider a composite graph G with backbone graph B (|V_B|=n):


  * The coherence of G is:

    H_C(G)= 1/2N(∑_i=1^n 2 n_i H_C(G_i) 
       + ∑_i=1^n∑_j=i+1^n|V_i||V_j|r(l_i,l_j) + ∑_i=1^n |V - V_i| C_i(l_i) ).


  * To minimize the coherence of G, B should be defined such that l_i = min_v ∈ V_i C_i(v).



To prove this theorem, we  use the following proposition, which immediately follows from Lemma <ref>.

 The resistance distance between two nodes u_i, v_j ∈ V where u_i ∈ V_i, v_j ∈ V_j, i ≠ j is r(u_i,v_j) = r(u_i,l_i) + r(l_i,l_j)+r(l_j,v_j). 


We now prove the theorem.


We find the effective resistance of G and then use this to find H_C(G).

Let G = (V,E)  be a composite graph, i.e., V = V_1 ∪…∪ V_n and E = E_1 ∪…∪ E_n ∪ E_B.
G is constructed such that every pair of subgraphs G_i, G_j, i ≠ j is connected only through their respective bridge nodes l_i and l_j. 
By applying Lemma <ref>, we can define Ω_G in terms of  Ω_i, the effective resistance of G_i, for i = 1 … n,
and the resistance distances of  each edge e ∈ E_B: 
 
    Ω_G    =  1/2∑_i=1^n ∑_j=1^n (∑_u ∈ V_i∑_v ∈ V_j r(u,v) )  
       =∑_i=1^nΩ_i + ∑_i=1^n ∑_j>i^n (∑_u ∈ V_i∑_v ∈ V_j r(u,v) ).

To obtain (<ref>) from (<ref>), note that when i=j, ∑_u ∈ V_i∑_v ∈ V_j r(u,v) = Ω_i.

For i ≠ j, each term ∑_u∈ V_i∑_v∈ V_jr(u,v) in (<ref>) can be rewritten as 

    ∑_u∈ V_i∑_v∈ V_jr(u,l_i)+r(l_i,l_j)+r(l_j,v),

 as noted in Proposition <ref>.
In turn, the double sum  in (<ref>) can be simplified to |V_j|C_i(l_i) + |V_i||V_j|r(l_i,l_j) + |V_i|C_j(l_j).
The formula for Ω_G now becomes:


    Ω_G =   ∑_i=1^nΩ_i 
    
    +    ∑_i=1^n∑_j=i+1^n( |V_j|C_i(l_i) + |V_i||V_j|r(l_i,l_j) + |V_i|C_j(l_j) ) 
    
    =   ∑_i=1^nΩ_i + ∑_i=1^n∑_j=i+1^n( |V_j|C_i(l_i) + |V_i|C_j(l_j) )  
       + ∑_i=1^n∑_j=i+1^n|V_i||V_j|r(l_i,l_j).

We can see that ∑_i=1^n∑_j=i+1^n( |V_j|C_i(l_i) + |V_i|C_j(l_j) )
is C_i(l_i) multiplied by the total number of vertices in G-G_i, therefore Ω_G is:

    Ω_G =  ∑_i=1^nΩ_i +  ∑_i=1^n∑_j=i+1^n|V_i||V_j|r(l_i,l_j) + ∑_i=1^n |V - V_i| C_i(l_i).

Then, we divide use (<ref>) to replace Ω_i with 2n_iH_C(G_i) and divide (<ref>) by 2N to finally obtain (<ref>). 

All terms in H_C(G) are constant for any fixed set of graphs G_i and backbone graph B, except for C_i(l_i). Thus, we minimize H_C(G) by selecting each bridge node l_i to be the vertex with the minimum resistance centrality in G_i.



 §.§ Analysis of Coherence in  Backbone Graph Structures


We now explore specific backbone graph topologies. In addition to deriving formulae for  coherence, we are interested in identifying backbone graphs that
minimize the coherence of the composite graph.

First, consider a composite graph with a tree backbone graph with |V_B|=n. The coherence of such a composite graph can be derived from Theorem <ref> by using Lemma <ref> to replace r(l_i,l_j) with the graph distance d(l_i,l_j) between bridge nodes to obtain:

    H_C(G) =   1/2N( ∑_i=1^n 2n_i H_C(G_i) + ∑_i=1^n∑_j=i+1^n d(l_i,l_j) |V_i||V_j| 
       + ∑_i=1^n |V - V_i| C_i(l_i) ).



With this expression we can show that the star backbone graph is the optimal tree backbone graph topology.


The optimal composite graph with a tree backbone graph, B=(V_B,E_B), |V_B|=n, has a star graph for B,
and the bridge node l_c in the center of the star is such that l_c ∈ V_c, where V_c ∈_i |V_i|. 

In a star graph, the resistance distance between the bridge node of the central graph G_c and all other subgraphs G_i, c ≠ i, is 1, and the resistance distance between the bridge nodes of all other subgraphs G_i and G_j, i,j ≠ c, is 2. 

When calculating H_C(G), d(l_i,l_j) |V_i||V_j| is computed for all combinations of i and j ≤ n. Therefore, to minimize ∑_i=1^n∑_j=i+1^n d(l_i,l_j) |V_i||V_j|, and thus also minimize (<ref>), we choose a subgraph V_c ∈_i |V_i| to be the center of the star graph.
Then,  ∑_i=1^n∑_j=i+1^n d(l_i,l_j) |V_i||V_j| becomes  ∑_i ≠ c |V_c| |V_i| + ∑_i ≠ c∑_j=i+1, j ≠ c 2· |V_i||V_j|.
No other arrangement of subgraphs in a tree can reduce H_C(G) more.



Now consider a composite graph with a line backbone graph of size n. The coherence of such a composite graph is again derived from (<ref>) and (<ref>), but here d(l_i,l_j)=j-i for all i>j. Therefore:

    H_C(G) =  1/2N( ∑_i=1^n  2n_i H_C(G_i) 
       + ∑_i=1^n∑_j=i+1^n (j-i)|V_i||V_j| ∑_i=1^n |V - V_i|C_i(l_i) ).





The optimal composite graph G with a line backbone graph B=(V_B, E_B)  where the nodes of B, V_B={l_s_1, l_s_2, …,l_s_n}, are ordered from left to right in the path graph and the subgraphs G_1,G_2, …, G_n are ordered by decreasing vertex set size. Then if c=⌊n/2⌋, we can assign the vertices of V_B as follows: l_s_c=l_1,   l_s_c+1=l_2,   l_s_c-1=l_3, l_s_c+1=l_4,   l_s_c-2=l_5,  etc., where l_i is the bridge node of G_i. 



As in Corollary <ref>, to optimize (<ref>) we need only to optimize ∑_i=1^n∑_j=i+1^n (j-i)|V_i||V_j|. Therefore we need to find the optimal arrangement of subgraphs in order to minimize this sum, which can be done by finding the ordering such that as |V_i||V_j| increases, j-i decreases. Clearly, this is done by placing the subgraphs along the line backbone in a way that minimizes the distance of the largest subgraphs to all other subgraphs and maximizes the distance of the smallest subgraphs to all other subgraphs. This requirement is fulfilled by placing the largest subgraph at the center of the line, placing the smallest subgraphs on the endpoints of B, and arranging the subgraphs in between closer to the center or to the ends according to their size.



The coherence of a composite graph with a ring backbone graph |V_B|=n is derived from (<ref>) by noting that in a ring graph with n nodes, r(l_i,l_j) = (j-i)(n-(j-i))/n. We then get the following formula:

    H_C(G)    = 1/2N( ∑_i=1^n 2 n_i H_C(G_i)  + ∑_i=1^n |V - V_i| C_i(l_i)
       +   ∑_i=1^n∑_j=i+1^n (j-i)(n-(j-i))/n |V_i||V_j| ).







Finally we consider the upper and lower bounds for H_C(G) over all subgraph topologies and all backbone graph topologies.
The proof of these results is given in the appendix.






 
The lower bound for the coherence of any composite graph with |V_B|=n and |V_i| = |V_j|=m for all i,j ≤ n is: 

    H_C(G) ≥1/2N( n(m-1) + 2m^2(n-1) + 2n(n-1)(m-1)).




Now, we consider the upper bound of H_C(G) for a graph G. We first note that with all else held equal, the backbone graph which maximizes H_C(G) is the line graph, since by Lemma <ref> only tree backbones have d(l_i,l_j) ≥ r(l_i,l_j), and the line graph has the largest diameter of all tree graphs. Since all |V_i|=m, the ordering of the subgraphs along the line has no effect on the coherence. We previously derived the formula for the coherence of a line composite graph (<ref>).
 
The upper bound for the coherence of any composite graph with |V_B|=n and |V_i| = |V_j|=m for all i,j ≤ n is: 

    H_C(G) ≤   1/12N(nm(m^2-1)) + 1/12N(nm^2(n^2-1)) 
           + 1/4N( nm^2 (m-1)(n-1)).







































§ COMPOSITE GRAPHS WITH STUBBORN AGENT DYNAMICS





We consider the problem of how to select  so as to minimize the coherence H_S(G).
In particular, we assume that only a fixed number of edges k
can be chosen.  The optimal edge set can be found by an exhaustive search over all subsets of k edges, however, this approach is computationally intractable for large subgraphs and values of k.

Instead, we define a greedy polynomial-time algorithm for selecting the edge set  E_con.
The pseudocode is given in Algorithm <ref>.
In each iteration, an edge e is chosen whose addition to  minimizes the coherence of G.  This is repeated until || has reached the desired size k. The input to Algorithm <ref>, is the graph G=(V,E), where V=V_1 ∪…∪ V_n and E=E_1 ∪…∪ E_n, the matrix Q, and  the desired size of , k.  












§ NUMERICAL EXAMPLES

We illustrate the performance of our greedy algorithm for adding edges to initially disjoint networks. In all examples, we consider stubborn agent dynamics.
The following two numerical examples were produced in Matlab. Both examples were run with two different types of D matrices: D_I=I  and D_R, where D_R is diagonalized from d=[d_1, …, d_n]^ where for each i, with probability 0.2, we set d_i = 0, and with probability 0.8, we set d_i to a value chosen uniformly at random from (0,1].



 §.§ Adding Edges Between Versus Within Subgraphs





We first demonstrate through numerical examples that the coherence of a network with stubborn agent dynamics will always see more improvement by adding a new edge between the subgraphs rather than within a given subgraph.
 The networks are generated as follows: two disjoint Erdős-Rényi graphs G_1 and G_2 with sizes between 8 and 15 are randomly generated to form a network G=(V_1 ∪ V_2, E_1 ∪ E_2)=(V,E). In Figure <ref> we use D_I and in Figure <ref>, we use D_R for our calculations. For each numerical example, we begin with two candidate edge sets:  the set of edges between the two subgraphs and the set of edges within the two subgraphs. 

We run Algorithm <ref> to choose the set of edges between the graphs, and then we repeat the algorithm to choose the set of edges within the subgraphs.  We run a series of 20 trials; 
we calculate the resulting coherence of each edge added in every trial and take the average results across all runs.
These average coherence values from adding edges between the subgraphs and within the subgraphs are plotted in the accompanying figures. As we can see in Figure <ref> and Figure <ref>, the coherence of the network with edges added between the subgraphs is always better than the coherence of the network with edges added only within G_1 or G_2. Note also that initial improvement from adding a single edge is always greater when adding an edge between the subgraphs, rather than adding an edge within the subgraph. 

We have also observed that when Algorithm <ref> is performed on sets of n>2 graphs, so long as more than n-1 edges are added, the improvement in coherence from adding a k^th edge  up to the n-1^th will always be greater when adding an edge between subgraphs than within subgraphs. That is, the best choice will always be to connect another pair of subgraphs, rather than add an edge within an already connected subgraph of G.



 §.§ Greedy Versus Optimal E_con




We now demonstrate that the coherence of G composed of two subgraphs with E_con of size k chosen by Algorithm <ref> is very close to the coherence of G with an optimal edge set E^* selected. 
We run simulations with two randomly generated Erdős-Rényi graphs with size between 4 and 8 (the small graph sizes are due to the combinatorial nature of optimal set selection). As in the previous numerical example, in Figure <ref> we use D_I and in Figure <ref>, we use D_R.
For this example, we make no distinction between edges within or between the original subgraphs.

We first use Algorithm <ref> to choose an edge set of size k to add to the network. Then the optimal set is selected by forming all possible edge sets of size k and calculating the decrease in coherence of adding each of them in turn. The edge set with the greatest decrease is then chosen. The results of both methods are then summed and averaged over a series of 15 trials.

We can see that the performance of the edge sets chosen by Algorithm <ref>  are quite close to the performance of the optimal sets, justifying the use of the greedy algorithm.





§ EXAMPLE
 


















Consider the graphs G_1 and G_2 shown in Figure <ref>. Let their respective bridge nodes be l_1=2 and l_2=4 and let the edge set of the backbone graph B be E_B={ (2,4)}.
We then form the graph G={{E_1 ∪ E_2}, {V_1 ∪ V_2 ∪ (2,4)}}.



For the given graphs, R_1 = 4, R_2 = 6 1/3, C_1(l_1) = 2, C_2(l_2) = 7/3. 
We then use (<ref>) to calculate the coherence of G to be:  H_C(G)=8/3.








We also use the above pair of graphs to illustrate the results of Algorithm <ref>. In Table <ref>, we list the edge sets E_con of size k=1, …, 3 generated by the algorithm and their corresponding values H_S(E_con) and compare to the optimal edge set E^⋆ and H_S^⋆.
table for H_S(E_con)

 
 

§ CONCLUSION
 
We have considered the problem of  how to best connect disjoint subgraphs to optimize the coherence of the composite graph. For systems with noisy consensus dynamics, we have derived several expressions and bounds for the coherence of composite graphs. For systems with stubborn agent dynamics we presented a non-combinatorial algorithm for choosing edges which, when added to the network, closely approximate the performance of the optimal edge set of the same size. Finally, we have demonstrated the performance of this algorithm in numerical examples.

In future work, we plan to investigate analytical expressions for the coherence of composite networks with stubborn agent dynamics, similar to those we derived for composite networks with noisy consensus dynamics.  We also plan to explore the design of composite graphs under additional dynamics and performance measures.



§ APPENDIX


The lower bound for the coherence of any composite graph with |V_B|=n and |V_i| = |V_j|=m for all i,j ≤ n is: 

    H_C(G) ≥1/2N( n(m-1) + 2m^2(n-1) + 2n(n-1)(m-1)).



To find the lower bound of H_C(G), we need to find the backbone graph structure that minimizes the coherence of G.

The coherence of a composite graph with a complete graph backbone B, |V_B|=n, is derived from (<ref>), using the fact that in a complete graph, r(l_i,l_j) is the same for all 1 ≤ i,j ≤ n, and r(l_i,l_j) = 2n/n^2. The coherence of a complete graph is then:

    H_C(G)    =  1/2N( ∑_i=1^n 2n_iH_C(G_i) +   2n/n^2∑_i=1^n∑_j=i+1^n|V_i||V_j| 
       + ∑_i=1^n |V - V_i| C_i(l_i) ).


Clearly the best way to minimize the resistance distance across all edges of the backbone graph is to connect every vertex to every other vertex, resulting in the lowest resistance distance for each edge in the backbone graph. Therefore the composite graph with |V_B|=n and |V_i|=m for all subgraphs G_i will have the highest connectivity when B is a complete graph of size n and each G_i is a complete subgraph of size m.

To calculate the effective resistance of this graph G, beginning from (<ref>), we substitute m-1 for 2n_iH_C(G_i), m for |V_i|, |V-V_i|=m(n-1), and (m-1)2m/m^2 for C_i(l_i) to get: 

    H_C(G)  =  1/2N( ∑_i=1^n m-1 +  2n/n^2∑_i=1^n∑_j=i+1^n m^2 
       + ∑_i=1^n m(n-1) (m-1)2m/m^2) 
       = 1/2N( n(m-1) + 2n/n^2m^2 n(n-1)/2
       + nm(n-1)(m-1)2m/m^2)
       = 1/2N( n(m-1) + 2m^2(n-1) + 2n(n-1)(m-1)).

Any other composite graph G' with |V_i| = m and |V_B|=n will therefore have 

    H_C(G') ≥1/2N( n(m-1) + 2m^2(n-1) + 2n(n-1)(m-1)).




The upper bound for the coherence of any composite graph with |V_B|=n and |V_i| = |V_j|=m for all i,j ≤ n is: 

    H_C(G) ≤   nm(m^2-1) /12N + nm^2(n^2-1)/12N
       + nm^2 (m-1)(n-1)/4N.



Since the line composite graph has the highest coherence for any graph G, in order to maximize H_C(G) we set each G_i to be a line graph of size m and each l_i ∈ V_i to be an endpoint of the backbone graph B. We use the structural properties of a line graph to find that C_i(l_i)= ∑_i=1^m-1i=m(m-1)/2 and H_C(G_i)= 1/2n_i∑_i=1^m ∑_j=i+1^m (j-i) = 1/12n_im(m^2-1). 
We now substitute H_C(G_i)=1/12 n_im(m^2-1), |V-V_i|=m(n-1), |V_i|=m, and C_i(l_i)=m(m-1)/2 into (<ref>) to get:

    H_C(G)    = 
    
    =   1/2N( ∑_i=1^n 2n_i1/12n_im(m^2-1) + ∑_i=1^n ∑_j=i+1^n (j-i) m^2 
       + ∑_i=1^n m(n-1)·m(m-1)/2).

Simplifying further, we obtain:

    H_C(G) =1/2N( 1/6m(m^2-1)n + 1/6n(n^2-1)m^2 
    
    +    nm(n-1)m(m-1)/2). 
    
    =   nm(m^2-1) /12N + nm^2(n^2-1)/12N + nm^2 (m-1)(n-1)/4N.

Any other composite graph G' with |V_i| = m and |V_B|=n which does not have both a line backbone graph and line subgraphs G_i will therefore have 

    H_C(G') ≤   nm(m^2-1) /12N + nm^2(n^2-1)/12N
       + nm^2 (m-1)(n-1)/4N.




























IEEEtran





