1

Scale-free Loopy Structure is Resistant to Noise in
Consensus Dynamics in Complex Networks

arXiv:1801.00535v1 [cs.SY] 2 Jan 2018

Yuhao Yi, Zhongzhi Zhang, and Stacy Patterson, Member, IEEE

Abstract—The vast majority of real-world networks are scalefree, loopy, and sparse, with a power-law degree distribution
and a constant average degree. In this paper, we study first-order
consensus dynamics in binary scale-free networks, where vertices
are subject to white noise. We focus on the coherence of networks
characterized in terms of the H2 -norm, which quantifies how
closely agents track the consensus value. We first provide a
lower bound of coherence of a network in terms of its average
degree, which is independent of the network order. We then study
the coherence of some sparse, scale-free real-world networks,
which approaches a constant. We also study numerically the
coherence of Barabási-Albert networks and high-dimensional
random Apollonian networks, which also converges to a constant
when the networks grow. Finally, based on the connection of
coherence and the Kirchhoff index, we study analytically the
coherence of two deterministically-growing sparse networks and
obtain the exact expressions, which tend to small constants. Our
results indicate that the effect of noise on the consensus dynamics
in power-law networks is negligible. We argue that scale-free
topology, together with loopy structure, is responsible for the
strong robustness with respect to noisy consensus dynamics in
power-law networks.
Index Terms—Distributed average consensus, network coherence, scale-free network, small-world network, resistance distance, Gaussian white noise

I. I NTRODUCTION
HE CONSENSUS problem, as a fundamental problem in
distributed computing [1], decision [2] and control [3],
has been intensely studied in the context of networks of agents.
It describes the process by which a group of agents reach an
agreement on certain quantities, for example, time, positions
and attitudes of satellites, estimation of environmental quantities in a sensor network, and so on. Variations of the consensus
problem can be observed in many science and engineering
scenarios, including problems in clock synchronization [4],
load balancing [5–8], vehicle formation [9], flocking [10], rendezvous [11], human group dynamics [12], distributed sensor
networks [13–15], as well as distributed learning [16, 17] and
collaborative inference [18] with streaming data. In view of the
wide range of applications, consensus problems have attracted
a great deal of recent interest [3, 19, 20].
In real-world applications, agents are often subject to environmental disturbances. For example, the motion of a group of

T

Yuhao Yi and Zhongzhi Zhang were supported by the National Natural
Science Foundation of China under Grant No. 11275049. Stacy Patterson
was supported by NSF grants CNS-1527287 and CNS-1553340.
Yuhao Yi and Zhongzhi Zhang (corresponding author) are with the
Shanghai Key Laboratory of Intelligent Information Processing, School
of Computer Science, Fudan University, Shanghai, 200433, China.
yhyi15@fudan.edu.cn, zhangzz@fudan.edu.cn
Stacy Patterson is with the Department of Computer Science, Rensselaer
Polytechnic Institute, Troy, New York, 12180. sep@cs.rpi.edu

vehicles is affected by many environmental factors, frictions,
wind, slopes, to name a few, and these quantities can fluctuate
within some range. In consensus problems with disturbances,
agents never reach perfect equilibrium but fluctuate around
the average of their current values. It is then ideal that the
deviation for each agent from the average value is small,
which is referred to as network coherence [21–24]. Due to
its practical significance, consensus problems under environmental disturbances have attracted considerable attention [25–
32]. In this paper, we focus on a consensus protocol with
Gaussian white noises added on the first-order derivatives of
the vertex states, which is the most often discussed model in
related literature.
By convention, we use the mean steady state variance of
the system to capture the average deviation of every vertex.
This quantity is also called the first-order network coherence,
or coherence for short in this paper. By defining the output
as the residual between the current states of vertices and their
average, the coherence can be expressed by the H2 norm of the
system divided by the number of nodes. The H2 norm of the
considered system is given by the trace of the pseudoinverse
of the graph Laplacian matrix, which contains some critical
information about the global topology of the network [22–24].
Note that the convergence rate in consensus problems without
noise is determined by the algebraic connectivity, which is the
smallest none-zero eigenvalue of the graph Laplacian, while
the coherence is related to the whole spectrum.
Previous works have studied the network coherence in some
particular network structures [21–27, 30]. Young et al. [27]
gave closed-form solutions for the H2 norm in paths, star
graphs, directed and undirected cycles. Bamieh et al. [22, 24]
studied the network coherence in some fractal trees and found
a connection between spectral dimensions and the first-order
network coherence. They also give asymptotical results for
coherence in tori and lattices [23]. To exploit the impact of
small-world and scale-free topology on the network coherence,
we analytically determined the coherence in the small-world
Farey network [30, 33] and the scale-free Koch network [32],
with the latter consisting of short cycles of only triangles.
However, the above-mentioned models cannot well mimic
many real-world networks, which are sparse and simultaneously display some remarkable properties [34]. For example, various real-world networks exhibit the scale-free behavior [35] and small-world effect [36]. Scale-free behavior [35]
means that the degree distribution P (d) of many real-world
networks has a power-law form as P (d) ∼ d−γ ; while smallworld effect [36] implies that the average path length grows
logarithmically with the number of vertices, or more slowly,

2

and the average clustering coefficient tends to a constant
larger than zero. In addition, many real-world networks display a nontrivial pattern with many cycles/loops at different
scales [37, 38], where a cycle/loop is a sequence of different
nodes (except the starting node and ending node that are the
same), with each pair of consecutive nodes in the sequence
being adjacent to each other. These striking structural patterns
have great impact on other structural and dynamical properties
of networks. For example, scale-free topology strongly affects
structural characteristics (e.g., perfect matchings [39] and
minimum dominating sets [40]) and dynamical processes (e.g.,
epidemic spreading [41], game [42], controllability [43]) on
scale-free networks.
As mentioned above, for first-order noisy consensus, it is
desirable that the network coherence is as small as possible.
Since many real networks are sparse, natural questions arise:
what is the behavior of coherence for these networks? What is
the smallest possible coherence for sparse networks with given
average degree? In addition, realistic networks are often scalefree and small-world with cycles at different scales. We then
propose another interesting question: is there a lower bound for
coherence or its dominant scaling that can be obtained in both
real networks and popular models describing real networks
with these prominent structural properties?
In this paper, we study the first-order coherence of noisy
consensus on sparse networks with an average degree ρ,
especially scale-free networks with cycles at distinct scales.
First, we provide a lower bound and an upper bound for
coherence of an arbitrary network, with the lower bound being
a constant 1/(2ρ), independent of the network order. Then, we
consider the coherence of sparse real networks, which is also a
constant but a little larger than 1/(2ρ). In addition, we address
the coherence of random, sparse scale-free network models,
including the Barabási-Albert (BA) network [35] and high
dimensional random Apollonian networks (HDRAN) [44, 45],
which is also constant. Finally, by making use of the connection between the Kirchhoff index and the first-order network
coherence, we study coherence on two exactly solvable, deterministic scale-free networks: one is the pseudofractal scalefree web [46]; the other is a new network proposed by the
authors, which is called the 4-clique motif scale-free network,
hereafter, since it has a power-law distribution and consists of
4-vertex complete graphs. For both networks, we obtain the
explicit expressions for their coherence, which also tends to
constants as the networks grow. We show that the structural
properties are responsible for the small coherence on these
studied networks.
II. P RELIMINARIES
In this section, we introduce some basic concepts in graph
theory and electrical networks and describe the consensus
problems to be studied.
A. Graph and Matrix Notation
We consider a symmetric network system as an undirected
graph G consisting of a pair (V, E), where the vertex/node
set V = {1, 2, · · · , N } refers to N nodes with dynamics,

and the edge set E contains M unordered vertex pairs {i, j},
i, j ∈ V , representing links between vertices that can directly
communicate. We use |·| to denote the cardinality of a set, thus
N = |V | and M = |E|. The adjacency matrix A is the matrix
representation of graph G, which is defined as an N × N
symmetric matrix with aij = aji = 1 if the pair {i, j} ∈ E,
and aij = 0 otherwise. Let Ni be the set of neighbors for
PN
P
vertex i; then the degree of i is di = j∈Ni aij = j=1 aij .
The degree matrix D of graph G is defined as a diagonal
matrix with its ith diagonal entry equal to di . The Laplacian
matrix of G is defined as L = D − A. For a connected graph
G, its Laplacian matrix L is positive semi-definite and has a
unique zero eigenvalue corresponding to the eigenvector 1N ,
which represents the 1 × N vector with all ones [47]. Thus all
eigenvalues of L can be ordered as 0 = λ0 < λ1 6 λ2 · · · 6
λN −1 in a connected network. Moreover,
PN −1 the sum of all nonzero eigenvalues is 2M , that is i=1 λi = 2M .
B. Electrical Networks

An electrical network associated with graph G is a network
of resistances, where every edge in G is replaced by a unit
resistance. In the case without confusion, we also use G to
denote the electrical network corresponding to graph G. The
resistance distance between vertices i and j in G, denoted by
Ωij , is defined as the potential difference between them when
a unit current is injected at i and extracted from j. It has been
proved that the resistance distance is a metric [48]. Then, the
resistance distance between any pair of nodes is symmetric,
that is, Ωji = Ωij for two arbitrary vertices i and j. It has
been established [48] that Ωji can be exactly represented in
terms of the elements of the pseudoinverse L† for L:
Ωji = Ωij = L†ii + L†jj − 2L†ij .

(1)

The effective resistance of an electrical network has many
interesting properties.
Lemma II.1. (Foster’s Theorem [49]) In an electrical network
G = (V, E),
X
Ωij = N − 1.
(2)
i<j,
(i,j)∈E

Lemma II.2. (Sum rule [50]) For any two different vertices
i and j in an electrical network G = (V, E),
X
di Ωij +
(Ωik − Ωjk ) = 2 .
(3)
k∈Ni

For a network G = (V, E), many graph invariants relevant to resistance distance have been defined. Much studied
examples include the Kirchhoff index [48], the multiplicative
degree-Kirchhoff index [51], and the additive degree-Kirchhoff
index [52]. These three invariants are defined, respectively, by
X
Ωij ,
(4)
R(G) =
i,j∈V
i<j

R∗ (G) =

X

i,j∈V
i<j

di dj Ωij ,

(5)

3

and
R+ (G) =

X

(di + dj )Ωij .

(6)

i,j∈V
i<j

Since L† 1N = 0, from (1) we obtain
R(G) =

N
−1
X

1 X
1
.
Ωij = N · tr L† = N ·
2
λi
i=1

(7)

i,j∈V

C. First-Order Leader-Free Noisy Consensus Dynamics
In the first-order consensus problem, the state of the system
is given by a vector x ∈ RN , where the i-th entry xi ∈ R
denotes the state of vertex i. Let x(t) ∈ RN denote the system
state at time t. Each vertex utilizes only local information
to adjust its state, and the states of vertices are subject to
stochastic disturbances. The first-order dynamics in a stochastic consensus problem without any leader can be described
by
X
dxi (t) = −
aij [xi (t) − xj (t)]dt + dWi (t) ,
(8)

TABLE I
S CALINGS OF AVERAGE GRAPH DISTANCE µ AND COHERENCE HFO
SOME TYPICAL NETWORK STRUCTURES .

FOR

Network Structure

µ

HFO

path [27]
1-dimensional torus [23, 27]
1-dimensional Cayley graph [53]
regular ring lattice [30]
Vicsek fractal [24]
T-fractal [24]
Peano Basin fractal [24]
2-dimensional torus [23]
2-dimensional Cayley graph [53]
Farey graph [30]
Koch graph [32]
d-dimensional torus (d > 3) [23]
d-dimensional Cayley graph (d > 3) [53]
star graph [27]
complete graph [27]

N
N
N
N

N
N
N
N

N log 3/ log 5
N log 2/ log 3
N 1/2
N 1/2
N 1/2
log N
log N
N 1/d
N 1/d
1
1

N log 3/ log 5
N log 2/ log 3
N 1/2
log N
log N
log N
log N
1
1
1
N −1

D. Related Work

The first-order network coherence HFO and its scaling
behavior in different networks have been extensively studied.
in which Wi (t) is a Wiener process. Let W (t) be the vector Table I lists the asymptotic scalings for HFO in some networks
of N uncorrelated Wiener processes; then, we can write (8) previously studied in the literature.
From Table I, we can observe that the leading behavior
in matrix form as
for HFO in different networks is rich. For a network with
dx(t) = −Lx(t)dt + dW (t) .
(9) N vertices, HFO can behave linearly, sub-linearly, logarithmically, inversely with N , or independently of N . For example,
It is known that when the agents are subject to external in the path graph [27], 1-dimensional torus [23, 27], 1disturbances, the vertex states fluctuate around the average of dimensional Cayley graph [53], and regular ring lattice [30],
the states of all vertices. We characterize the variance of these HFO ∼ N ; in some fractal tree-like graphs [24] including
fluctuations by the concept of network coherence [22–24].
Vicsek fractal, T fractal, and Peano Basin fractal, HFO grows
sub-linearly
with N as HFO ∼ N θ with 0 < θ < 1; in
Definition II.1. The first-order network coherence without
leaders is defined as the mean steady-state variance of the 2-dimensional torus [23], 2-dimensional Cayley graph [53],
Farey graph [30], and Koch graph [32], HFO ∼ ln N ; in the
deviation from the average of the current vertex states:
complete graph [27], HFO ∼ 1/N ; while in d-dimensional


N
N
torus
(d > 3) [23], d-dimensional Cayley graph (d > 3) [53],


1 X
1 X
var xi (t) −
xj (t) . (10) as well as star graph [27], HFO is a constant, irrespective of
HFO := lim
t→∞ N


N j=1
N.
i=1
It can be proved [27] that among all N -vertex graphs, the
The output of the system is given by
first-order network coherence HFO is minimized uniquely in
N −1
y(t) = Π x(t),
(11) the complete graph KN , with HFO (KN ) = 2N 2 . When
N → ∞, HFO (KN ) → 0. In this sense, the complete
where Π is the projection operator defined as graph has the optimal structure that has the best performance
Π := IN − N1 1N 1⊤
for noisy consensus dynamics. However, complete graphs
N , with IN being the identity matrix
of order N . HFO is related to an H2 norm [27] formulated are dense, with the degree of each vertex being N − 1.
by (9) and (11):
Extensive empirical work indicates that real-world networks

Z ∞


2
are often sparse, having a small constant average degree [34].
⊤
1
1
(H2 )
e−L t Π⊤ Πe−Lt dt =
= tr
tr L† . Moreover, most realistic networks are scale-free [35] and
HFO =
N
N
2N
0
(12) small-world [36]. Table I shows that the first-order network
coherence HFO depends on the structure of networks. Then,
According to (7), HFO depends on the N − 1 nonzero interesting questions arise naturally: What is the minimum
eigenvalues of Laplacian matrix L, and similarly, the Kirchhoff scaling of HFO for sparse networks? Is this minimal scaling
achieved in real scale-free networks?
index R(G) for graph G:
In the sequel, we first provide a lower bound 1/(2ρ) for the
N −1
R(G)
1 X 1
first-order network coherence HFO for all networks with aver=
.
(13)
HFO (G) =
2N i=1 λi
2N 2
age degree ρ. Then we study the first-order network coherence
j∈Ni

4

HFO for some real scale-free networks and show that HFO
is constant. We also study the first-order network coherence
HFO on two random scale-free networks, BA network [35]
and HDRAN [44, 45], which converges to a constant. Finally,
we study analytically HFO in two deterministic scale-free
networks: pseudofractal scale-free web [46] and the 4-clique
motif scale-free network, the first-order network coherence for
which also tends to a constant. Thus, scale-free topology is
advantageous to noisy consensus dynamics.
III. L OWER AND

UPPER BOUNDS FOR FIRST- ORDER

NETWORK COHERENCE

In this section, we provide a lower bound and an upper
bound for first-order network coherence HFO in an arbitrary
graph. We first introduce a lemma [54].
Lemma III.1. Let G be an N -vertex graph. Then λ1 = λ2 =
· · · = λN −1 if and only if G is a complete graph.
Theorem III.2. For a graph G with N vertices, M edges, and
average degree ρ = 2M
N , the first-order network coherence
N
1
1
HFO ≥ 4M
− 2M
+ 4MN
, with equality if and only if G is
1
when N is large.
the complete graph; further, HFO ≥ 2ρ
Proof: Applying the Cauchy-Schwarz inequality to (13)
yields
N −1
N −1
N −1
1 X 1 X λj
1 X 1
=
2N i=1 λi
2N i=1 λi j=1 2M
!2
N
−1 r
X
1
(N − 1)2
1
>
=
· λi
4M N i=1
λi
4M N

HFO =

=

1
1
N
−
+
.
4M
2M
4M N

(14)

N
1
1
By Lemma III.1, HFO = 4M
− 2M
+ 4MN
if and only if G
is the complete graph.
Since ρ = 2M
N and 2M = ρN > 2(N − 1),

lim HFO >

N →∞

1
.
2ρ

(15)

This completes the proof.
In addition to the lower bound, we also provide an upper
bound for the first-order network coherence HFO of a graph
G in terms of its average graph distance (also called average
path length) µ.
Theorem III.3. For a graph G with N vertices and average graph distance µ, the first-order network coherence
−1
µ, with the equality if and only if G is a tree.
HFO 6 N4N
When N is large, HFO 6 µ4 .
Proof: Note that in any graph, the effective resistance Ωij
between a pair of vertices i and j is less than or equal to their
shortest path length δij [48]. Then,
HFO =

µ N (N2−1)
N −1
R(G)
6
=
µ.
2N 2
2N 2
4N

(16)

When G is a tree, Ωij = δij [48], and thus the equality holds.

For large N ,
lim HFO 6

N →∞

µ
.
4

(17)

This completes the proof.
For a network G, it is highly desirable that its first-order
network coherence is small. Theorem III.2 indicates that for
1
large sparse graphs with small constant ρ, 2ρ
is the smallest
value we can obtain for the first-order network coherence
HFO . A network is said to be optimal if its first-order network
1
. We refer to a large sparse network as almost
coherence is 2ρ
optimal if its first-order coherence is a constant.
Table I shows that for the d-dimensional torus (d > 3),
the d-dimensional Cayley graph (d > 3), and the star graph,
the first-order network coherence is a constant. In fact, the
star graph SN has the smallest HFO among all trees with N
vertices. HFO for SN does not grow with N but converges to a
constant. For d-dimensional tori and d-Cayley graphs (d > 3),
their HFO is also a constant, but their average distance grows
with N .
As mentioned above, most real-world networks are sparse
and have a power-law degree distribution. However, the behavior of first-order network coherence for realistic networks
has not been studied thus far. In what follows, we will study
the first-order network coherence for some real-life scalefree networks, as well as random and deterministic network
models. We will show that for all of these considered sparse
networks, their first-order network coherence does not grow
with the network size but converges to small constants. Thus,
scale-free networks have almost optimal network coherence.

IV. N ETWORK C OHERENCE

FOR

R EALISTIC N ETWORKS

In this section, we evaluate the coherence of some realworld networks that have power-law degree distributions. We
use a large collection of networks of different orders that are
chosen from different domains.
In Table II we report the network coherence for some
real-world, scale-free undirected networks. All data are taken
from the Koblenz Network Collection [55]. The considered
real networks are representative, including social networks,
information networks, technological networks, and metabolic
networks. The networks are shown in increasing order of the
number of vertices. The smallest network has approximately
3 × 102 vertices while the largest network has about 6 × 105
vertices.
Table II shows that for real scale-free networks with
2 < γ 6 3, their coherence HFO is generally small. For
all networks, HFO lies between its lower bound 1/(2ρ) and
upper bound µ/4. Moreover, for each network, its HFO is
significantly smaller than µ/4; for most networks, HFO is
closer to 1/(2ρ) than µ/4. In fact, as observed for many other
properties (e.g., clustering coefficient [36]), the coherence HFO
of real networks does not increase with the number of vertices
N ; instead, it seems to be independent of N and tends to small
constants.

5

TABLE II
BASIC STATISTICS AND FIRST- ORDER COHERENCE OF SOME REAL - WORLD
NETWORKS .

Network

N

M

γ

1
2ρ

HFO

µ
4

Zachary karate club
David Copperfield
Hypertext 2009
Jazz musicians
PDZBase
Haggle
Caenorhabditis elegans
U. Rovira i Virgili
Hamsterster friendships
Protein
Hamster full
Facebook (NIPS)
Human protein (Vidal)
Reactome
Route views
Pretty Good Privacy
arXiv astro-ph
CAIDA
Internet topology
Brightkite

34
112
113
198
212
274
453
1,133
1,858
1,870
2,426
2,888
3,133
6,327
6,474
10,680
18,771
26,475
34,761
58,228

78
425
2,196
2,742
242
2,124
2,025
5,451
12,534
2,203
16,631
2,981
6,149
146,160
12,572
24,316
198,050
53,381
107,720
214,078

2.161
3.621
1.284
5.271
3.034
1.673
1.566
1.561
2.461
2.879
2.421
4.521
2.132
1.363
2.462
4.261
2.861
2.509
2.233
2.481

0.109
0.066
0.013
0.018
0.109
0.219
0.056
0.052
0.037
0.212
0.037
0.242
0.127
0.011
0.129
0.110
0.024
0.124
0.081
0.068

0.203
0.151
0.021
0.051
0.707
0.236
0.135
0.170
0.176
0.730
0.142
0.675
0.388
0.138
0.365
0.721
0.128
0.361
0.319
0.359

0.602
0.634
0.414
0.559
1.332
0.606
0.666
0.902
0.863
1.703
0.897
0.967
1.210
1.053
0.926
1.871
1.049
0.969
1.229
0.942

V. N ETWORK C OHERENCE IN R ANDOM S CALE - FREE
M ODEL N ETWORKS
In this section, we study the coherence for two typical
stochastic scale-free model networks, that is, Barabási-Albert
(BA) networks [35] and high dimensional random Apollonian
networks (HDRAN) [44, 45]. The main reason for studying
these two networks is that they capture the generating mechanisms for some real scale-free networks.
A. Coherence for Barabási-Albert Networks
The BA network model [35] is the most well known random
scale-free model. The algorithm of the BA model is as follows.
Starting from a small connected graph, at each time step, we
create a new vertex and connect it to m different vertices that
are already present in the network. The probability that the
new vertex connects to an old vertex i is proportional to the
degree of i. We repeat the growth and preferential attachment
procedure, until the network grows to the ideal size N . When
N is large, the average degree of BA networks approaches
2m. The degree distribution of BA networks exhibits a powerlaw form, with the power exponent γ being 3, regardless of
m. BA networks are small-world, with their average path
length increasing approximately logarithmically with N . In
addition, there are many cycles with different lengths in BA
networks [56].
According to the generating algorithms, we create different
networks with various number of vertices. For all of these
generated networks, we calculate their coherence based on
(12). Figure 1 shows the coherence of BA networks with
various m = 2, 4, 6, 8. From the figure, we observe that the
coherence of these networks does not grow with the network

Network Coherence

0.25

For each network, we indicate the number of nodes N , the number of edges
1
M , power-law exponent γ, the lower bound for coherence 2ρ
, the coherence
for the largest connected component HFO , and the upper bound for coherence
µ
.
4

m=2
m=4
m=6
m=8

0.20

0.15

0.10

0.05

0

10000

20000

Number of vertices

Fig. 1. Simulation results for the coherence of BA networks with different
m. For all networks, the construction starts from the 8-vertex complete graph.

size N but converges to an m-dependent constant: the larger
the parameter m, the smaller the network coherence.
B. Coherence for High Dimensional Random Apollonian Networks
We continue to study the coherence for d-dimensional (d ≥
2) random Apollonian networks. We will see that the behavior
of coherence for HDRAN is similar to that observed in BA
networks. The d-dimensional (d ≥ 2) random Apollonian
networks are constructed as follows. We first generate a d + 2vertex complete graph, or d + 2-clique. We say that a d + 1clique is active if it was never chosen before. At each time
step, we select randomly an active d + 1-clique and create
a new vertex and connect this new vertex to every vertex of
the d + 1-clique chosen. We repeat the procedure of selecting
active d+1-cliques and creating new vertices, until the network
grows to a given size N . For the large N , the average degree
of HDRAN tends to 2(d + 1).
The HDRAN display the prominent properties observed
in real-world networks [45]. First, they are scale-free, since
their degree distribution obeys a power-law, with the power
1
exponent being γ = 2 + d−1
. Second, they are small-world,
with their average path length growing logarithmically with
the number of vertices. Third, their clustering coefficient is
large and tends to a d-dependent constant, increasing with d.
Finally, by construction, there are many cycles with various
length in HDRAN.
In Figure 2, we report the numerical results about the
coherence for HDRAN with various d and N . From Figure 2,
we can observe that with the growth of HDRAN, the network
coherence converges to a constant that depends on the dimension parameter d: The higher the dimension d, the lower the
network coherence. This phenomenon is consistent with our
intuition.
VI. N ETWORK C OHERENCE FOR D ETERMINISTIC
S CALE - FREE N ETWORKS
To further uncover the behavior of coherence in scale-free
networks, in this section we derive closed form expressions

6

Network Coherence

0.20

d=2
d=3
d=4
d=5

0.16

0.12

0.08

0.04
0

25000

50000

Number of vertices

Fig. 2. The coherence for d-dimensional random Apollonian networks with
various d.

F0

F1

F2

Fig. 3. The first few iterations of pseudofractal scale-free web.

for the network coherence of two deterministic scale-free
networks, the pseudofractal scale-free web [46] and 4-clique
motif scale-free network, both of which are constructed by
edge iterations. These two networks are representative of a
class of deterministic models for scale-free networks, since
they display the classic properties observed in most real-world
networks. Due to their special construction, we can derive
exact results of coherence for both networks.
A. Coherence for Pseudofractal Scale-free Web
The pseudofractal scale-free web after g (g ≥ 0) iterations,
denoted by Fg , is constructed in the following manner. Initially
(g = 0), the network F0 consists of a triangle of 3 vertices
and 3 edges. At each iteration g ≥ 1, for each existing edge
e in Fg−1 we add a new vertex and connect it to both end
vertices of e. Figure 3 shows networks F0 , F1 , and F2 . By
construction, it is easy to verify that in network Fg , there
g+1
are Ng = 3 2 +3 vertices and Mg = 3g+1 edges. Then, the
g+1
average degree of Fg is ρ = 4×3
3g+1 +3 , which is approximately
4 when g is large enough.
The pseudofractal scale-free web is simultaneously scalefree and small-world [46]. It has a power-law distribution
ln 3
with the power exponent being γ = 1 + ln
2 . Its average
path length grows logarithmically with the number of vertices,
when g is large. Moreover, it has a large average clustering
coefficient that tends to a constant 54 when g is large. In
addition to these topological properties, many combinatoric

properties of the pseudofractal scale-free web have also been
well studied, such as minimum dominating sets [57], the
number of spanning trees [58], and the distribution of cycles
of different length [37].
Theorem VI.1. The network coherence for the pseudofractal
scale-free web Fg , g ≥ 0, is

1
50 · 33g+3
HFO (Fg ) =
112 · 3g+2 (3g+1 + 3)2
− 35 · 32g+2 2g+1 + 48 · 32g+2 + 30 · 3g+2 2g+1

(18)
− 14 · 3g+2 + 225 · 2g+1 ,

which asymptotically converges to a constant when g → ∞:
25
lim HFO (Fg ) =
.
(19)
g→∞
84
Proof: According to (13), to find the coherence for the
pseudofractal scale-free web Fg , we can first determine its
Kirchhoff index. By replacing G in Theorem 5.3 in [59] with
F0 , we obtain the Kirchhoff index R(Fg ) of Fg , which reads
1 −(g+2) 
R(Fg ) =
50 · 33g+3 − 35 · 32g+2 2g+1
3
112
+ 48 · 32g+2 + 30 · 3g+2 2g+1

(20)
− 14 · 3g+2 + 225 · 2g+1 .

Plugging (20) into (13) leads to (18), which provides a closed
form expression for HFO (Fg ). When g → ∞, (19) is
immediate from (18).
We note that the lower bound for HFO (Fg ), given in terms
1
= 18 . Thus, the actual value
of the average degree ρ, is 2ρ
25
84 of the network coherence HFO (Fg ) is about as 2.38 times
the lower bound 81 , which means that the pseudofractal scalefree web has an almost optimal structure for noisy consensus
without leaders.
B. Coherence for 4-clique Motif Scale-free Network

In this subsection, we propose an variant of the pseudofractal scale-free web and study its network coherence. The variant
is also iteratively constructed and scale-free, which consists
of 4-vertex complete graphs, we thus call it 4-clique motif
scale-free network. We next briefly introduce the construction
method, structural properties. and network coherence of firstorder consensus dynamics for the 4-clique scale-free motif
network, while we omit the details of computation or proofs
due to the limitation of space.
We denote by Tg the 4-clique motif scale-free network after
g (g ≥ 0) iterations. Initially (g = 0), T0 is a 4-vertex complete
graph. For g ≥ 1, Tg is obtained from Tg−1 by performing the
following operations: for each edge e in Tg−1 , we create a new
edge e′ and connect each end-vertex of e′ to both end-vertices
of edge e. For network Tg , let Vg be the set of its vertices, let
V̄g be the set of vertices generated at iteration g, and let Eg
be the set of all edges. It is easy toderive that in network Tg
there are Ng = |Vg | = 52 6g+1 + 4 vertices and Mg = 6g+1
g+1
edges. Thus the average degree of Tg is ρ = 65×6
g+1 +4 , which is
approximately 5 when g is large. Figure 4 illustrates networks
T0 and T1 .

7

Lemma VI.3. The multiplicative degree-Kirchhoff index, additive degree-Kirchhoff index, and Kirchhoff index of network
Tg are, respectively,

1 g g+2
·2 3
13 · 2g+1 3g − 5 · 3g+1 + 4 ,
5
9 
R+ (Tg ) =
169 · 22g+2 32g − 55 · 2g+1 32g+1
275

+ 11 · 2g+3 3g + 35 · 3g+1 + 11 ,
3 
R(Tg ) =
13 · 22g+1 32g+2 − 11 · 2g 32g+2
275

+ 13 · 2g+2 3g + 7 · 3g+2 − 11 + 36 · 2−g .
R∗ (Tg ) =

T0

T1

The 4-clique motif scale-free network also displays some
common properties of real-world networks. It has a power-law
ln 2
degree distribution with exponent γ equal to 2 + ln
3 . It has
the small-world effect, with the average path length growing
as a logarithmic function of the number of vertices and the
265
. Thus, both
clustering coefficient tending to a high value 306
networks Tg and Fg exhibit similar structural properties; it is
then expected that their dynamical properties (e.g., network
coherence) also bear a strong resemblance to each other.
We now derive the expression for the coherence HFO of
first-order noisy consensus in Tg . We will show that HFO (Tg )
converges to a constant with the growth of the network. To this
(g)
end, we first determine the Kirchhoff index for Tg . Let Ωij be
the effective resistance between a pair of nodes i and j in Tg .
For network Tg+1 , the following Lemma gives the evolution
of effective resistance between any pair of old nodes, namely,
those nodes already present in Tg , and shows that the effective
resistance between any two nodes in Tg+1 can be expressed
in terms of those pairs of old nodes in Tg .
Lemma VI.2. Let {i, j} be a unordered pair of vertices in
(g+1)
satisfies:
Tg+1 ; the effective resistance Ωij
(g)

= 12 Ωij .
1) If i, j ∈ Vg , then Ωij
(g+1)
= 12 .
2) If i, j ∈ V̄g+1 and {i, j} ∈ Eg+1 , then Ωij
(g)

(g+1)
Ωij

=
3) If i ∈ V̄g+1 , j, l ∈ Ni ∩ Vg , then
4) If i ∈ V̄g+1 , j ∈ Vg , k, l ∈ Ni ∩ Vg , then
(g)

(g+1)

Ωij

=

(g)

8

Ωjl
8

(g)

(g+1)

=

(g)

(g)

Theorem VI.4. For network Tg , g ≥ 0, the first-order
coherence is

3
HFO (Tg ) = (6g+1 + 4)−2 13 · 22g+1 32g+2 − 11 · 2g 32g+2
88

+ 13 · 2g+2 3g + 7 · 3g+2 − 11 + 36 · 2−g .
(27)

lim HFO (Tg ) =

g→∞

,

(g)

3
1
1
R(Tg+1 ) = Mg2 − Ng (Ng − 1) + Mg (Ng − 2)
2
4
4

1
+
R(Tg ) + R (Tg ) + R∗ (Tg ) , (24)
+
2

R∗ (Tg+1 ) =9 3Mg2 − Mg Ng + 18R∗ (Tg ) ,
(25)
27
3
3
9
R+ (Tg+1 ) = Mg2 − Mg − Ng (Ng − 1) − Mg Ng
2
2
4
4
+ (3R+ (Tg ) + 6R∗ (Tg )) .
(26)

2
g+1
g+1
+ 4 , Mg = 6 , and the initial
Considering Ng = 5 6
conditions R∗ (T0 ) = 27, R+ (T0 ) = 18, and R(T0 ) = 3,
the above recursive equations (24), (25), and (26) are solved
to obtain the expressions for R∗ (Tg ), R+ (Tg ), and R(Tg ) as
given in the lemma.
Lemma VI.3, together with (13), leads to the following
theorem.

+ 38 .

which is also true for j ∈ {k, l}, and is reduced to case
3).
5) If i, j ∈ V̄g+1 , {i, j} ∈
/ Eg+1 , k, l ∈ Ni ∩ Vg , and
p, q ∈ Nj ∩ Vg , then
Ωij

(23)

In the limit of large g (g → ∞),

(g)

3 + 2Ωjl + 2Ωjk − Ωkl

(22)

Proof: Using the technique and procedure similar to
those in [59], we can derive the following recursive relations
governing the evolution for R(Tg ), R∗ (Tg ), and R+ (Tg ).

Fig. 4. Illustration for the 4-clique motif networks T0 and T1 .

(g+1)

(21)

(g)

(g)

(28)

Therefore, in large networks Tg , the first-order network
39
coherence converges to a small constant 176
, much smaller
than 1. We remark that the lower bound for HFO (Tg ) given in
1
, lower than the actual value
terms of the average degree is 10
39
176 , with the actual value being about 2.22 times the lower
bound. Thus, similar to the pseudofractal scale-free web, the
4-clique motif scale-free networks also has an almost optimal
structure for noisy consensus dynamics.

6 + Ωkq + Ωkp + Ωlp + Ωlq − (Ωkl + Ωpq )
.
8

Using Lemmas II.1, II.2, and VI.2, we can derive the recursive relations for the Kirchhoff index R(Tg ), multiplicative
degree-Kirchhoff index R∗ (Tg ), and additive degree-Kirchhoff
index R+ (Tg ) for network Tg , and thus obtain their exact
expressions in terms of g.

39
.
176

VII. R ESULT A NALYSIS

In the preceding sections, we have studied the first-order
noisy consensus dynamics in real-world and model scale-free
networks. The results show that in all considered networks,
the network coherence is very small and does not depend on
the number of vertices, but converges to constants. Thus, all

8

of these networks are almost optimal in the sense that they
are very robust to Gaussian noisy in consensus dynamics.
Since the first-order coherence of a network is determined
by all non-zero eigenvalues of its Laplacian matrix, which is
in turn influenced by the structure of the network, the small
constant coherence observed for studied networks are due to
their structural properties, especially the scale-free behavior
and cycles of various length, which can be understood from
the following heuristic arguments.
As shown in (13), the coherence is closely related to
resistance distance, which is bounded by the shortest-path
distance. In a scale-free network, there exist vertices with
large degree that are linked to many other vertices in the
network, which results in the small-world phenomenon that
the average path length grows at most logarithmically with
the number of vertices in the network [34]. Moreover, in many
realistic and model scale-free networks, there are many cycles
with different lengths, which lead to various alternative paths
of different lengths between many vertex pairs. As a result,
the average resistance distance over all pairs of vertices does
not increase with the growth of the network. Below, by way
of illustration we show that neither power-law behavior nor
cycles alone can guarantee a constant network coherence.
In [30], it is shown that in the small-world Farey network,
the network coherence HFO scales logarithmically with the
number of vertices N as HFO ∼ ln N . However, in the
pseudofractal scale-free web, HFO is a constant, independent
of N . Note that both Farey network and pseudofractal scalefree web are small-world and highly clustered. Moreover, there
are many cycles at different scales in both networks. The
reason for the distinction of their coherence lies in, at least
partially, the scale-free property of the pseudofractal scale-free
web that is absent in the Farey network. On the other hand,
the coherence HFO for the Koch network [32] is a logarithmic
function of N , despite its scale-free structure. The reason the
coherence for the Koch network is not a constant is because
it has only triangles, lacking cycles of different length.
VIII. C ONCLUSION
Various real-life networks are sparse and loopy, displaying the striking scale-free and small-world properties, which
heavily affect the behaviors of diverse dynamics occurring
on these networks. In this paper, we have studied first-order
consensus dynamics with disturbances in scale-free networks,
with an emphasis on the network coherence. We first provided a lower bound and an upper bound for coherence in
a general network, with the lower bound being half of the
reciprocal of the average degree. We then studied the network
coherence for some representative real-world networks with
the scale-free property, and found that their coherence is
very small, irrespective of the size of the networks. We
also studied numerically the coherence for Barabási-Albert
networks and high dimensional Apollonian networks, which
converges to constants when the networks grow. Finally, we
studied analytically the coherence for two deterministic scalefree networks, obtaining explicit expressions for the network
coherence, which converge to small constants. Our results

indicate that scale-free networks are resistant to stochastic
disturbances imposed on the consensus algorithm. We argued
that the scale-free and loopy structure is responsible for the
robustness against the noise.
R EFERENCES
[1] N. A. Lynch, Distributed algorithms. San Francisco,
CA: Morgan Kaufmann, 1996.
[2] J. N. Tsitsiklis, “Problems in decentralized decision making and computation,” Ph.D. dissertation, Massachusetts
Institute of Technology, 1984.
[3] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,”
Proc. IEEE, vol. 95, no. 1, pp. 215–233, Jan. 2007.
[4] W. Sun, E. G. Ström, F. Brännström, and M. R. Gholami, “Random broadcast based distributed consensus
clock synchronization for mobile networks,” IEEE Trans.
Wirel. Commun., vol. 14, no. 6, pp. 3378–3389, 2015.
[5] G. Cybenko, “Dynamic load balancing for distributed
memory multiprocessors,” J. Parallel Distrib. Comput.,
vol. 7, no. 2, pp. 279–301, 1989.
[6] S. Muthukrishnan, B. Ghosh, and M. H. Schultz, “Firstand second-order diffusive methods for rapid, coarse,
distributed load balancing,” Theor. Comput. Syst., vol. 31,
no. 4, pp. 331–354, 1998.
[7] R. Diekmann, A. Frommer, and B. Monien, “Efficient
schemes for nearest neighbor load balancing,” Parallel
Comput., vol. 25, no. 7, pp. 789–812, 1999.
[8] N. Amelina, A. Fradkov, Y. Jiang, and D. J. Vergados,
“Approximate consensus in stochastic networks with
application to load balancing,” IEEE Trans. Inf. Theory,
vol. 61, no. 4, pp. 1739–1752, 2015.
[9] J. A. Fax and R. M. Murray, “Information flow and
cooperative control of vehicle formations,” IEEE Trans.
Autom. Control, vol. 49, no. 9, pp. 1465–1476, Sep. 2004.
[10] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms and theory,” IEEE Trans. Autom. Control, vol. 51, no. 3, pp. 401–420, Mar. 2006.
[11] D. V. Dimarogonas and K. J. Kyriakopoulos, “On the
rendezvous problem for multiple nonholonomic agents,”
IEEE Trans. Autom. Control, vol. 52, no. 5, pp. 916–922,
May 2007.
[12] L. F. Giraldo and K. M. Passino, “Dynamic task performance, cohesion, and communications in human groups,”
IEEE Trans. Cybern., vol. 46, no. 10, pp. 2207–2219,
2016.
[13] Q. Li and D. Rus, “Global clock synchronization in
sensor networks,” IEEE Trans. Comput., vol. 55, no. 2,
pp. 214–226, 2006.
[14] W. Yu, G. Chen, Z. Wang, and W. Yang, “Distributed
consensus filtering in sensor networks,” IEEE Trans.
Syst., Man, Cybern. B, Cybern., vol. 39, no. 6, pp. 1568–
1577, 2009.
[15] S. Zhu, C. Chen, W. Li, B. Yang, and X. Guan, “Distributed optimal consensus filter for target tracking in
heterogeneous sensor networks,” IEEE Trans. Cybern.,
vol. 43, no. 6, pp. 1963–1976, 2013.

9

[16] A. H. Sayed, “Adaptation, learning, and optimization
over networks,” Foundations and Trends in Machine
Learning, vol. 7, no. 4-5, pp. 311–801, 2014.
[17] V. Matta, P. Braca, S. Marano, and A. H. Sayed,
“Diffusion-based adaptive distributed detection: Steadystate performance in the slow adaptation regime,” IEEE
Trans. Inf. Theory, vol. 62, no. 8, pp. 4710–4732, 2016.
[18] G. Biau, K. Bleakley, and B. Cadre, “The statistical
performance of collaborative inference,” J. Mach. Learn.
Res., vol. 17, no. 1, pp. 2200–2228, Jan. 2016.
[19] S. Motsch and E. Tadmor, “Heterophilious dynamics
enhances consensus,” SIAM Rev., vol. 56, no. 4, pp. 577–
621, 2014.
[20] X. Wu, Y. Tang, J. Cao, and W. Zhang, “Distributed consensus of stochastic delayed multi-agent systems under
asynchronous switching,” IEEE Trans. Cybern., vol. 46,
no. 8, pp. 1817–1827, 2016.
[21] S. Patterson and B. Bamieh, “Leader selection for optimal network coherence,” in Proc. 49th IEEE Conf.
Decision Control. IEEE, 2010, pp. 2692–2697.
[22] ——, “Network coherence in fractal graphs,” in Proc.
50th IEEE Conf. Decision Control, Dec. 2011, pp. 6445–
6450.
[23] B. Bamieh, M. Jovanovic R, P. Mitra, and S. Patterson, “Coherence in large-scale networks: Dimensiondependent limitations of local feedback,” IEEE Trans.
Autom. Control, vol. 57, no. 9, pp. 2235–2249, Sep. 2012.
[24] S. Patterson and B. Bamieh, “Consensus and coherence
in fractal networks,” IEEE Trans. Control Netw. Syst.,
vol. 1, no. 4, pp. 338–348, Sep. 2014.
[25] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed average
consensus with least-mean-square deviation,” J. Parallel.
Distrib. Comput., vol. 67, no. 1, pp. 33–46, Jan. 2007.
[26] B. Bamieh, M. Jovanovic R, P. Mitra, and S. Patterson,
“Effect of topological dimension on rigidity of vehicle
formations: Fundamental limitations of local feedback,”
in Proc. 47th IEEE Conf. Decision Control, Dec. 2008,
pp. 369–374.
[27] G. F. Young, L. Scardovi, and N. E. Leonard, “Robustness of noisy consensus dynamics with directed communication,” in Proc. Amer. Control Conf., Jun. 2010, pp.
6312–6317.
[28] R. Rajagopal and M. J. Wainwright, “Network-based
consensus averaging with general noisy channels,” IEEE
Trans. Signal Process., vol. 59, no. 1, pp. 373–385, 2011.
[29] Y. Yang and R. S. Blum, “Broadcast-based consensus with non-zero-mean stochastic perturbations,” IEEE
Trans. Inf. Theory, vol. 59, no. 6, pp. 3971–3989, 2013.
[30] Y. Yi, Z. Zhang, Y. Lin, and G. Chen, “Small-world
topology can significantly improve the performance of
noisy consensus in a complex network,” Comput. J.,
vol. 58, no. 12, pp. 3242–3254, 2015.
[31] J. He, M. Zhou, P. Cheng, L. Shi, and J. Chen, “Consensus under bounded noise in discrete network systems:
An algorithm with fast convergence and high accuracy,”
IEEE Trans. Cybern., vol. 46, no. 12, pp. 2874–2884,
2016.
[32] Y. Yi, Z. Zhang, L. Shan, and G. Chen, “Robustness

[33]

[34]

[35]

[36]

[37]

[38]
[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]
[48]
[49]

[50]

[51]

of first-and second-order consensus algorithms for a
noisy scale-free small-world Koch network,” IEEE Trans.
Control Syst. Technol., vol. 25, no. 1, pp. 342–350, 2017.
Z. Zhang and F. Comellas, “Farey graphs as models for
complex networks,” Theor. Comput. Sci., vol. 412, no. 8,
pp. 865–875, Mar. 2011.
M. E. J. Newman, “The structure and function of complex networks,” SIAM Rev., vol. 45, no. 2, pp. 167–256,
Jun. 2003.
A.-L. Barabási and R. Albert, “Emergence of scaling in
random networks,” Science, vol. 286, no. 5439, pp. 509–
512, 1999.
D. J. Watts and S. H. Strogatz, “Collective dynamics of
‘small-world’ networks,” Nature, vol. 393, no. 6684, pp.
440–442, Jun. 1998.
H. D. Rozenfeld, J. E. Kirk, E. M. Bollt, and D. BenAvraham, “Statistics of cycles: how loopy is your network?” J. Phys. A, vol. 38, no. 21, p. 4589, 2005.
K. Klemm and P. F. Stadler, “Statistics of cycles in large
networks,” Phys. Rev. E, vol. 73, no. 2, p. 025101, 2006.
Z. Zhang and B. Wu, “Pfaffian orientations and perfect
matchings of scale-free networks,” Theor. Comput. Sci.,
vol. 570, pp. 55–69, 2015.
Y. Jin, H. Li, and Z. Zhang, “Maximum matchings and
minimum dominating sets in Apollonian networks and
extended Tower of Hanoi graphs,” Theoret. Comput. Sci.,
vol. 703, pp. 37–54, 2017.
R. Pastor-Satorras and A. Vespignani, “Epidemic spreading in scale-free networks,” Phys. Rev. Lett., vol. 86,
no. 14, p. 3200, 2001.
F. C. Santos, M. D. Santos, and J. M. Pacheco, “Social diversity promotes the emergence of cooperation in public
goods games,” Nature, vol. 454, no. 7201, pp. 213–216,
2008.
Y.-Y. Liu, J.-J. Slotine, and A.-L. Barabási, “Controllability of complex networks,” Nature, vol. 473, no. 7346,
pp. 167–173, 2011.
T. Zhou, G. Yan, and B.-H. Wang, “Maximal planar
networks with large clustering coefficient and powerlaw degree distribution,” Phys. Rev. E, vol. 71, no. 4,
p. 046141, 2005.
Z. Zhang, L. Rong, and F. Comellas, “High-dimensional
random Apollonian networks,” Physica A, vol. 364, pp.
610–618, 2006.
S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes,
“Pseudofractal scale-free web,” Phys. Rev. E, vol. 65,
no. 6, p. 066122, 2002.
R. Merris, “Laplacian graph eigenvectors,” Linear Algebra Appl., vol. 278, no. 1-3, pp. 221–236, 1998.
D. J. Klein and M. Randić, “Resistance distance,” J.
Math. Chem., vol. 12, no. 1, pp. 81–95, 1993.
R. M. Foster, “The average impedance of an electrical
network,” Contributions to Applied Mechanics (Reissner
Anniversary Volume), pp. 333–340, 1949.
H. Chen, “Random walks and the effective resistance
sum rules,” Discrete Appl. Math., vol. 158, no. 15, pp.
1691–1700, 2010.
H. Chen and F. Zhang, “Resistance distance and the

10

[52]

[53]

[54]
[55]

[56]

[57]

[58]

[59]

normalized Laplacian spectrum,” Discrete Appl. Math.,
vol. 155, no. 5, pp. 654–661, 2007.
I. Gutman, L. Feng, and G. Yu, “Degree resistance
distance of unicyclic graphs,” Trans. Combin., vol. 1,
no. 2, pp. 27–40, 2012.
E. Lovisari and S. Zampieri, “Performance metrics in
the consensus problem: a survey,” IFAC Proceedings
Volumes, vol. 43, no. 21, pp. 324–335, 2010.
R. Merris, “Laplacian matrices of graphs: a survey,”
Linear Algebra Appl., vol. 197, pp. 143–176, 1994.
J. Kunegis, “Konect: The koblenz network collection,” in
Proc. 22nd Int. Conf. World Wide Web, 2013, pp. 1343–
1350.
G. Bianconi and A. Capocci, “Number of loops of size h
in growing scale-free networks,” Phys. Rev. Lett., vol. 90,
no. 7, p. 078701, 2003.
L. Shan, H. Li, and Z. Zhang, “Domination number
and minimum dominating sets in pseudofractal scale-free
web and Sierpiński graph,” Theoret. Comput. Sci., vol.
677, pp. 12–30, 2017.
Z. Zhang, H. Liu, B. Wu, and S. Zhou, “Enumeration of
spanning trees in a pseudofractal scale-free web,” EPL
(Europhysics Letters), vol. 90, no. 6, p. 68002, 2010.
Y. Yang and D. J. Klein, “Resistance distance-based
graph invariants of subdivisions and triangulations of
graphs,” Discrete Appl. Math., vol. 181, pp. 260–274,
2015.

