arXiv:1711.00303v1 [] 1 Nov 2017

ASSESSING THE RELIABILITY POLYNOMIAL BASED
ON PERCOLATION THEORY
SAJADI, FARKHONDEH A.
Department of Statistics, University of Isfahan, Isfahan 81744,Iran;
f.sajadi@sci.ui.ac.ir
Abstract. In this paper, we study the robustness of network
topologies. We use the concept of percolation as measuring tool
to assess the reliability polynomial of those systems which can be
modeled as a general inhomogeneous random graph as well as scalefree random graph.

1. Introduction
The robustness is one of the structural properties of a complex system which measures its ability of continuing perform well, subject to
failures or attacks. It is needed to quantify the measure of robustness
in order to decide whether or not, a given system is robust. The most
common measure of robustness of a network to random failures of components is all-terminal reliability polynomial, the probability that there
is an operating communications link between any two components in
the system. The reliability of a system of interacting agents, can be determined by analyzing the reliability of the underlying graph. A graph
is a pair of two sets G = (V, E) where V is a set of nodes/vertices
and E is a set of edges/links that connect two elements of V . The
elements of a real system and the interactions patterns between them
are represented by nodes and edges in a graph, respectability. Suppose
we have a graph G for which the nodes are always operational but for
which each edge e ∈ E is independently operational with probability
pe ∈ (0.1). The (all terminal) reliability of G, denoted by Rel(G, pe )
is therefore defined to be the probability that the graph is connected
when each edge is (independently of the others) present with probability pe . In other words the probability that the operational edges form a
2010 Mathematics Subject Classification. Primary 60K35; Secondary 05C80,
62N05 .
Key words and phrases. Complex network, Random graph, Percolation threshold, Network Reliability. Scale-free network, Reliability polynomial.
1

2

SAJADI

spanning connected subgraph of G. Let set of operational edges S ⊆ E
be the state of network, i.e., the network is in state S when all edges
of S are operational and all edges E − S are failing. Let O be the set
of all operational states. Then Rel(G, pe ) is equal to
XY Y
(1.1)
Rel(G, pe ) =
pe (1 − pe ) .
S∈O e∈S

e∈S
/

By knowing all states, the reliability is easily but not efficiently computed. The most amenable case is that in which all of the edge probabilities are identical, say p. Therefore under the condition that for all
e ∈ E, pe = p we have simpler version of formula(1.1), which is called
F-form of the reliability polynomial, as follows
(1.2)

Rel(G, p) =

|E|
X

Fi (1 − p)i p|E|−i

i=0

where Fi is the number of connected spanning subgraphs of size |E|− i.
There are different forms of presentation for the reliability polynomial
[1]. Also there are methods to examine the possible states of the network, for example the factorization method [2]. However, computing
the reliability polynomial, Rel(G, pe ) is not easy in general. Even the
time required to calculate R(G, p) for an arbitrary connected graph G
grows exponentially with the size of the network, [3],[4].
Because of this difficulty, network designers have often relied upon
upper and lower bounds on Rel(G, p), [5],[6],[7],[8],[9],[10],[11]. It would
be of interest if one can obtain exact solutions for the reliability polynomial for some families of graphs G. In [12], the authors built a framework based on percolation theory to calculate the network reliability.
They considered homogeneous random graph models with Poisson degree distribution. But in the current work, the method which we used
to assess the reliability polynomial can be apply for more general random graph with arbitrary degree distribution. More precisely, in this
paper, we use the percolation concept as measuring tool to assess the
reliability polynomial of systems which can be modeled as a general
inhomogeneous random graph and scale-free random graph.
The rest of the paper is organized as follows. In Section 2 we describe
the inverse percolation process. In Section 3 we explain how to obtain
the threshold at which the network loses its connectivity. Section 4
presents the assessment of network reliability. Section 5 and 6, will
illustrate our method for two special case of real network which can be
modeled as inhomogeneous and scale free random graph, respectively.

ASSESSING THE REL BASED ON PERCOLATION

3

2. Inverse percolation process
Random graphs have been used extensively as models for various
types of real world networks. It provides techniques to analyze structure in a system of interacting agents, represented as a network. In
mathematics, networks are often referred to as graphs. A random
graph is a graph that is sampled according to some probability distribution over a collection of graphs. Random graphs are used to prove
deterministic properties of the graphs. The most basic property of a
graph is that of being connected. It has been shown that, the limiting
probability that a random graph possesses connectedness, jumps from
0 to 1 (or vice versa) very rapidly. There exists a threshold when a
transition occurs from not being connected to being connected. For
example for the binomial random graph Gn,p , where n is the number
of vertices of the graph and p ∈ (0, 1) is the probability that the edge
(u, v) is present, we say that a phase transition occurs if there exists
a function p(n) such that for p1 (n) << p(n), Gn,p1 (n) almost surely
does not have the property of being connected, but for p(n) << p2 (n),
Gn,p2 (n) almost surely has the property of being connected. Here p(n)
is the threshold. The most important transitions is the emergence of a
giant component, a connected component of size Θ(n) where n is the
size of V , (an = Θ(bn ), if there exist constants C, c and n0 , such that,
cbn ≤ an ≤ Cbn , for n ≥ n0 ). The macroscopic behavior of networks,
when faced with random removal of nodes or edges, is characterized
in terms of an inverse percolation process in a random graph. Percolation theory characterizes this property of random graphs, especially
infinitely large ones. It studies the behavior of the operational giant
component, ensuring the global well functioning of the network. Once
the random removal of nodes or edges is done (random failure process),
the size of giant component, is expected to decrease. Using percolation theory, one can predicts the presence of a threshold, above which
the network percolates, i.e., it has a giant component and below it the
giant component disappears, i.e. the network is fragmented in many
disconnected components of very small sizes. For a highly-connected
graph sequence, the giant component is unique when the limit superior
of the size of second-largest component by n is 0 for large n, [13].
3. The percolation threshold
Let pe be the probability that edge e is operational and qv be the
probability that the node v ∈ V is operational. By being operational
we mean that node/edge hasn’t failed or been removed from the graph.
In particular cases, when in turn, qv or pe are uniform, we will specify

4

SAJADI

them as node (q) or edge (p) operational probability. Let the degree
distribution of our graph be pk , i.e., a randomly chosen node has degree
k with probability pk . We choose an edge at random and follow it to
one of the nodes at its ends, then the number of edges incident on
that node, other than the one we arrived along, follows the following
distribution,
kpk
(3.1)
ṕk =
,
<k>
P
where < k >= k kpk , is the average degree for the entire graph.
Let euv = {u, v} be the edge between node u and node v, and p∗uv
be the probability that edge euv does not lead to a vertex connected
via the remaining edges to the giant component. Then we have the
following recursive expression,
Y
(3.2)
p∗uv = (1 − peuv ) + peuv
p∗vw
w

where product is taking over all w which are not equal to u and are a
neighbor of v. Now, the average overall probability p∗e that a randomly
chosen edge does not belong to the giant component is,
X
(3.3)
p∗e = 1 − pe + pe
ṕk (p∗e )k−1 := h(p∗e ) .
k

p∗e

h(p∗e )

The equation =
has the trivial solution p∗e = 1. Moreover if
dh
> 1 then p∗e = h(p∗e ) has a unique root in [0, 1). This
h́(1) := dp
∗ |p∗
e =1
e

condition h́(1) > 1 implies that
(3.4)

pe >

<

k2

<k>
.
>−<k>

The existence of a giant component has a threshold at <k2<k>
, (the
>−<k>
bond percolation threshold of the graph). Note that the lower bound
2>
for pc in (3.4) is meaningful, if <k
> 2, (the Molloy-Reed criterion
<k>
for existence of giant connected components,[14]).
4. The network reliability
Now we map the random failures process of a network into an inverse percolation problem. The inverse percolation problem consists
of finding the critical fraction of the edges for which the giant component disappears. Suppose g denotes the fraction of randomly removed
edges. The deletion of a fraction g of edges corresponds to a random
graph in which the edges are occupied with probability p = 1 − g. For
small g, the infinite cluster which is identified as the giant component

ASSESSING THE REL BASED ON PERCOLATION

5

is present. The threshold for the destruction of the giant component,
gc = 1 − pc , can be thus computed from the percolation threshold at
which the infinite cluster first emerges. In this case the phase transition corresponds to the separation of a region of damages which still
allow a connected network of appreciable size from a region in which
the system is totally fragmented, [15].
Let pe (t) be the probability that edge e is operational at time t,
(the reliability of edge e at time t). Also we define qv (t), to be the
probability that at time t the node v ∈ V is operational. According to
the previous section, if pe (t) is less than a critical point pc , the giant
cluster does not exist anymore. Define the instant at which this occurs
as the lifetime of the network.
It is known that [13], the binomial (uniform) random graph
 loses
n
its connectivity when the number of failed edges reaches 2 − [Mc ],
where Mc is the number of remaining edges at critical point. Since pc
is a threshold
 for a monotone property of being connected, we have
Mc = pc ∗ n2 ,[13].
Now using threshold pc , an assessment for the network reliability at
ˆ c (G, pe )(t) is given by the following equation:
time t, denoted by Rel
(4.1)

ˆ c (G, pe )(t) =
Rel

N
X
i=[Mc ]+1

X Y
A∈[N ]i

e∈A

pe (t)

Y

[1 − pe (t)] ,

e∈Ac


n
where
N
=
and [N ]i stand for the family of all i-element subsets
2


of 1, 2, ..., n2 . In case when, all of pe (t)’s are equal to p(t), we have

(4.2)

ˆ c (G, p)(t) =
Rel

 
N
X
N
p(t)i [1 − p(t)]N −i .
i

i=[Mc ]+1

In [12], authors have defined the probability that a node/edge is functional at a given time t by R(t). Then by the voting system based on
the cite percolation critical value, they presented the network reliability
at time t, Rs (t) by the following equation:
 
n
X
n
(4.3)
Rs (t) =
R(t)i [1 − R(t)]n−i ,
i
i=[n∗pc ]+1

where R(t) is the reliability of the generic node. In fact in their model,
they assumed the same reliability for all nodes. They also gave an
example in which different edges have different failure probability and

6

SAJADI

then they compared the numerical results with the result from equation (4.3). It is clear that when reliability of nodes (i.e., R(t)) are not
same, the network reliability cannot be obtained from equation (4.3).
ˆ c (G, p)(t) is an -approximation
In the following example we will see Rel
for the reliability polynomial [16]. In fact difference between the exact
and approximate values for the reliability polynomial is zero.
Example 4.1. The reliability of complete graph K4 where pe (t) = p(t)
for all edges e in E, at given time t is
Rel(K4 , p)(t) = p(t)6

(F0 = 1)
5

+ 6p(t) (1 − p(t)) (F1 = 6)
(4.4)

+ 15p(t)4 (1 − p(t))2

(F2 = 15)

+ 16p(t)3 (1 − p(t))3

(F3 = 16) ,

as any sub-graph on at least 4 edges is operational and sub-graphs
with 3 edges that are operational are those that are a spanning tree
of K4 . There are no operational states with 2 or fewer edges. On
1
the other hand,
 1for complete graph K4 , we have pc = 3 . Therefore
4
[Mc ] + 1 = [ 2 ∗ 3 ] + 1 = 3. Hence we get same value for the reliability
of K4 from equations (4.2) and (4.4).
ˆ c (G, pe )(t) is
The lifetime distribution of the network based on Rel
ˆ c (G, pe )(t))
d(1 − Rel
,
dt
and the network lifetime, T , is given by
Z ∞
ˆ c (G, pe )(t)dt .
T =
Rel
f (t) =

0

Also,
ˆ c (G, pe )(T ) = pc .
Rel

ˆ c (G, p)(t) in (4.1) by enumerating all elStill, the computing of Rel
i
ements in [N ] for large N , is not practicable. Thus we need to use
ˆ c (G, p)(t). One can think of
approximation methods for computing Rel
Poisson approximation method, which is used for Poisson binomial distribution( the distribution of the sum of independent and non-identical

ASSESSING THE REL BASED ON PERCOLATION

random indicators). Fix t > 0. Let µ(t) =
son approximation method,
ˆ c (G, p)(t) ≈
Rel

(4.5)

N
X
i=[Mc ]+1

P

e∈E

7

pe (t). Then by Pois-

µ(t)i e−µ(t)
.
i!

By Le Cam’s theorem [17], the approximation error for the Poisson
approximation method is
N
X
k=0

|

X Y
A∈[N ]k e∈A

pe (t)

Y

[1 − pe (t)] −

e∈Ac

X
µ(t)k e−µ(t)
|<2
pe (t)2 .
k!
e∈E

In the following section, we look at an application of these results to
some specific examples. We consider the system which can be modeled
as
a: Inhomogeneous binomial random graph, and
b: Scale-free random graph.
5. Inhomogeneous binomial random graph
If edges in the binomial random graph, have different probability
of being occupied, the resulting graph is called the inhomogeneous
binomial random graph and denoted by G(n, p), where p = {pe , e ∈ E},
[18]. The binomial random graph is retrieved when taking pe = p for
all e ∈ E. For this random graph, the degree distribution will be
asymptotically Poisson. Hence,
e−λ
, λ > 0.
k!
1
= <k>
.

pk = λk
Therefore, pc =

<k>
<k2 >−<k>

=

1
λ

Example 5.1. Suppose we have a graph G on 5 nodes and the vector
of edge probabilities at a given time t as follows:
(pe1 , pe2 , pe3 , pe4 , pe5 , pe6 , pe7 , pe8 )(t) =
(e−0.0379∗t , e−0.8795∗t , e−0.7818∗t , e−0.6949∗t , e−0.6841∗t , e−0.0732∗t , e−0.1629∗t , e−0.01045∗t ).
In Figure 1, graph G is presented.
For this graph the value of threshold pc is 0.421053. The plot of
ˆ
Relc (G, p)(t) verses t, 0 ≤ t ≤ 15 is shown in Figure 2.
ˆ c (G, p)(t) drops abruptly at pc = 0.421053. The correNote that Rel
sponding t for this threshold present the life time of network (between
4 and 5). In Figure 3, the evolution of the network G is studied.

8

SAJADI

Figure 1. Graph G with 5 nodes and 8 edges.

ˆ c (G, p)(t).
Figure 2. Plot of Rel

ASSESSING THE REL BASED ON PERCOLATION

9

Figure 3. Evaluation of G at discrete times t=0,1,...,11

6. Scale-free random graph
In the scale-free networks majority of the nodes have few neighbors
but a small portion of them have a large number of neighbors. Many of
them possess a power-law degree distribution, so that the probability
pk that a node has k neighbors scales with k as pk ∼ k −γ , where γ is
the power-law exponent [19]. Topologies of many real-world networks
are thought to be scale-free, such as World Wide Web, email networks,
networks of Internet routers, and protein-protein interaction networks.
Here we consider the degree distribution as follows:

(6.1)

pk =

(
0
k−γ e−k/κ
Liγ (e−1/κ )

if k = 0
if k ≥ 1,

10

SAJADI

where γ and κ are constant and Liγ (x) is the polylogarithm function:
Liγ (x) =

∞
X
xi
i=1

iγ

.

Figure 4 shows a power-law graph with exponent γ = 1.5.

Figure 4. An example power-law graph with γ = 1.5.
For power-law degree distribution, the giant component threshold is,
(6.2)

pc =

<k>
Liγ−1 (e−1/κ)
=
< k2 > − < k >
Liγ−2 (e−1/κ ) − Liγ−1 (e−1/κ )

The divergence of the second moment < k 2 > is generally a sufficient
condition to ensure the absence of a percolation threshold on a scalefree graph.
It is known that for γ > 3 a phase transition exists at a finite pc .
Whereas for 2 < γ < 3 the transition takes place only at pc = 0, [20].

ASSESSING THE REL BASED ON PERCOLATION

11

Example 6.1. Suppose we have a graph G in which its degree distribution is as follows:
k −γ
pk =
,k ≥ 1,
ζ(γ)
where ζ(.) is the Riemann zeta function. Therefore from (6.2) we have
pc =

ζ(γ − 1)
.
ζ(γ − 2) − ζ(γ − 1)

Note that Liγ (1) = ζ(γ). For many scale-free networks the degree exponent γ is between 2 and 3, [19]. The behavior of pc as a function of
γ is depicted in Figure 5. As the figure shows, for γ ≤ 3, pc = 0 and
hence the transition never takes place (unless the network is finite).
Also pc is between zero and one, only in the small range 3 < γ < 3.48
of the exponent γ. As an example of real world network, we consider

Figure 5. The function

ζ(γ−1)
ζ(γ−2)−ζ(γ−1)

for 0 < γ < 4

the internet. The degree distribution of the internet nodes follows a

12

SAJADI

power law :
(6.3)

pk = ck −γ ,

kmin ≤ k ≤ kmax ,

where c is normalization constant and kmin and kmax are the minimal
and maximal degrees, respectively, [21]. For this model we have

 γ−2 γ−21 3−γ
2<γ<3
k
kmax −1
(6.4)
pc = 3−γ min
 γ−2 1
γ > 3.
(k
)−1
γ−3

min

1
. Figure 6
For the internet, γ ≈ 2.5. Therefore, pc = (kmin kmax
)0.5 −1
ˆ c (G, p)(t) when G is a power-law graph with
shows the plot of Rel
γ = 2.5, kmin = 1, kmax = 11, |E| = 250 and edge operational probability pe (t) = e−0.25∗t . As Figure 6 shows, the lifetime of the network
is around t = 3.36.

ˆ c (G, p)(t), where G is power-law
Figure 6. Plot of Rel
with γ=2.5 .

ASSESSING THE REL BASED ON PERCOLATION

13

References
1. Colbourn C.J., (1993). Some open problems on reliability polynomials, ,in:
Congr. Numer. 93 , 187–202.
2. Larsson, C., (2014). Design of Modern Communication Networks: Methods and
Applications. 1st. Academic Press.
3. Colbourn, C. (1987). The Combinatorics of Network Reliability. Oxford University Press, New York.
4. Provan J. and Ball, M. (1983). The complexity of counting cuts and of computing
the probability that a graph is connected, SIAM J. Comput. vol. 12:777–788.
5. Lomonosov, M. and Polesskii,V. (1971). An upper bound for the reliability of
information networks. Problems Inform. Transmission vol. 7:337–339.
6. Lomonosov,M. and Polesskii,V. (1972). Lower bound of network reliability, Problems Inform. Transmission vol. 8:118–123
7. Kruskal, J. (1963). The number of simplices in a complex, in Mathematical
Optimization Techniques, R. Bellman, ed. University California Press. 251–278.
8. Stanley, R. P. (1975). The upper bound conjecture and CohenMacaulay rings,
Stud. Appl. Math. vol. 14:135–142.
9. Ball, M. and Provan,J. (1982). Bounds on the reliability polynomial for shellable
independence systems. SIAM J. Algebraic Discrete Methods, vol. 3:166–181.
10. Ball, M. Colbourn, C. and Provan,J. (1995). Network reliability, in Handbook
of Operations Research: Network Models. Elsevier North-Holland), 673–762.
11. Brown, J. and Colbourn, C. (1996). Non-Stanley bounds for network reliability,
J. Algebraic Combin. vol. 5:18–36.
12. Li, D., Zhang, Q., Zio, E., Havlin, S. and Kang, R., (2015). Network reliability
analysis based on percolation theory, Reliability. Reliability Engineering and
System Safety. 142.
13. Luczak, T. and Rucinski, A. (2000). Random Graphs., Wiley, New York.
14. Molloy, M. and Reed,B. (1995). A Critical Point for Random Graphs with a
Given Degree Sequence. Random Structures and Algorithms. vol. 6:161–180.
15. Pastor-Satorras, R. and Vespignani, A. (2004). Evolution and Structure of the
Internet: A Statistical Physics Approach. Cambridge University Press. New
York, NY, USA.
16. Kayi Lee, Hyang-Won Lee, Eytan Modiano. (2011). Reliability in Layered Networks with Random Link Failures. IEEE/ACM Transactions on Networking, vol.
19: 1835–1848.
17. Le Cam, L. ,(1960), An approximation theorem for the Poisson binomial distribution. Pacific Journal of Mathematics. vol. 10:1181–1197.
18. Remco van der Hofstad (2016). Random Graphs and Complex Networks: Volume 1. 1st. Cambridge University Press New York.
19. Albert, R. and Barabasi, A. L. (2002). Statistical Mechanics of Complex Networks, Review Modern Physics, vol. 74: 47–97.
20. Barabasi, A.L. and Posfai, M.(2016). Network Science. Cambridge, UK: Cambridge University Press.
21. Faloutsos, M., Faloutsos, P. and Faloutsos, C.(1999). On Power-law Relationships of the Internet Topology. ACM SIGCOMM 1999, Comput. Commun. Rev.
29, 251–262.

