{'fraction_non_alphanumeric': 0.03111370582781002, 'fraction_numerical': 0.010920704694529345, 'mean_word_length': 4.0820244328097735, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 14, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Analyzing Network Reliability Using Structural Motifs

This paper uses the reliability polynomial, introduced by Moore and Shannon in 1956, to analyze the effect of network structure on diffusive dynamics such as the spread of infectious disease. We exhibit a representation for the reliability polynomial in terms of what we call {\em structural motifs} that is well suited for reasoning about the effect of a network's structural properties on diffusion across the network. We illustrate by deriving several general results relating graph structure to dynamical phenomena.


I. INTRODUCTION
Characterizing networks in a way that is directly relevant to diffusion phenomena on the network is important, but difficult. We argue that the Network Reliability Polynomial [1] is a characterization that folds together static measures like degree, modularity, and measures of centrality into precisely the combinations that are most relevant to the dynamics. Thus knowledge of reliability can be used to infer structure, in the sense of network tomography. Furthermore, reliability concepts provide a new perspective for reasoning more generally about the consequences of structural changes.
In a companion to this paper [2], we have shown how the concept of network reliability together with an efficient, scalable estimation scheme can shed light on complicated dynamical trade-offs between local structural properties such as assortativity-by-degree and the number of triangles. Here we take a complementary approach, using a slightly different representation of the reliability polynomial to prove relationships between such structures and dynamics. We show how coefficients of the reliability polynomial can be interpreted in terms of structural motifs and their overlaps. Conversely, we illustrate how knowledge of these motifs and their overlaps can be used to infer important constraints on the dynamics of diffusion processes on the network.
In this paper we start by proposing a different representation of the reliability polynomial that uses struc-tural motifs as its building blocks. We further employ this notation to extract both perturbative and analytic estimation of reliability for several classes of graphs. We then show how we can apply this representation of the reliability polynomial to solve some well-known problems, which can guide us to possible future work.

II. NETWORK RELIABILITY
In this article we use the common notation of G(V, E) for a graph with V vertices and E homogeneously weighted edges. The graph may be directed or undirected, and it is possible to have multiple edges between two vertices. Colbourn [3] gives an inclusive introduction of the reliability concept, while Youssef [2] provides a brief derivation of the form of the reliability polynomial.

A. Reliability rules
A reliability rule, r, is a binary function on graphs. If r(g) = 1, we say that graph g is accepted.
There are many useful reliability rules. In this paper we shall discuss the following, which can all be evaluated by labeling the connected components of the graph: 1. two terminal: a graph is accepted if it contains at least one directed path from a distinguished vertex S (the source) to another distinguished vertex T (the terminus); 2. N -terminal: a graph is accepted if N particular vertices are in the same connected component; 3. attack rate (AR)-α: a graph is accepted if it contains at least one connected component of size α or greater; 4. all-terminal: a graph is accepted if it consists of a single connected component.
These rules are all coherent, i.e. adding an edge to a accepted subgraph does not make it unaccepted. The rules above are commonly used in percolation theory, graph theory or network analysis. In other contexts, one could imagine more specialized rules. For example, if the network were a contact network of people, one might classify the vertices, e.g. by age or gender, and demand that a threshold number of each class was in a connected component.

B. Reliability polynomials
The reliability R(G, r, x) of a base graph G with respect to the rule r with edge weights x is the probability that a subgraph of G formed by edges chosen independently at random with probability x is accepted by r. We will explicitly include the dependence on the graph G and the rule r in notation such as R(G, r, x) only when we wish to distinguish the reliability of two different graphs or two different rules. Then, as is well known, For computational convenience, we often prefer to work with normalized coefficients Here R k (respectively, P k ) is the number (respectively, fraction) of subgraphs of G with exactly k edges that are accepted by the rule, and P k ≤ P k+1 for a coherent rule. Note that, although this is a continuous polynomial in the variable x, it involves only a finite number of coefficients R k , k ∈ {0, . . . , E}. That is, R(x) is an element of an E + 1-dimensional vector space with basis elements There are, of course, many other bases we could choose for the reliability polynomial. An orthogonal basis, such as the first E + 1 Legendre polynomials, might have useful estimation properties. Here we use another non-orthogonal basis -the functions x k -because of its simplicity and its attractive interpretation. There is a unique mapping from coefficients in one basis to those in the other, which can be derived by expanding the factor (1 − x) E−k in Equation 1: where

C. Transformations between representations
The N k coefficients are signed integers. They are not particularly useful for computation, both because the alternating sum in Equation 4 is subject to severe roundoff error and because they may be combinatorially large. However, as in Equation 2, we can define a normalized version The N k are not necessarily in the range from [− E k , E k ], so this normalization does not constrain the M k to have absolute value less than 1. However, with this normalization, the transformation between P k and M k takes a particularly simple form: The transformation from P k to M k given by Equation 6 is invertible. We can write this in matrix form as T is a lower triangular matrix whose entries are the elements of Pascal's triangle, but with alternating signs by row and column. It is well known that this is the inverse of a lower triangular matrix whose entries are the elements of Pascal's Triangle (without any negative signs). Alternatively, from Equation 15, we have Thus P = T −1 M , with T −1 i,j = i j , as expected.
D. Statistical physics of reliability Equation 1 defines the partition function of a system: it is the sum over all possible system configurations of the probability of that configuration. A "configuration" in this case is just a subgraph of the base graph. Here, the sum has been rearranged in terms of classes of equiprobable configurations. In this form, the reliability rule is a constraint selecting which elements of each class of configurations are physically acceptable. This is analogous to decomposing the partition function for a spin system into a factor that depends on local interactions of spins and a factor that provides a constraint on the total energy of the system. In this case, however, there is no way to write the constraint in a functional form, even as the limit of a Dirac δ-function, as is commonly done with more physical constraints [4]. Indeed, it is well known that the reliability polynomial for the all-terminal rule is an evaluation of the two-parameter Tutte polynomial [5], T , which in turn can be viewed as an analytic extension of the partition function for a q-state Potts model [6]. Curiously, the reliability polynomial for all-terminal reliability corresponds to the Potts model with q = 0 [7].
We interpret this as a system in which the spins do not interact locally with each other, but only with an external field. This is consistent with selecting subgraphs of size k by choosing k edges independently at random. This independent selection sidesteps correlations between edges that are responsible for many difficulties in graph analysis. In this approach, the correlations are accounted for properly because we select subgraphs of a particular graph that embodies the correlations among edges.

E. A physical interpretation for N k
An Inclusion-Exclusion argument lets us express the reliability polynomial in terms of overlaps among structural motifs. We define a structural motif to be a minimal subgraph accepted by the rule, i.e. a minimal set of edges that guarantees that the graph containing them is accepted. Formally, a structural motif is a set M ⊆ E of edges such that the subgraph g(V, M) is accepted, i.e. r(g) = 1, and the subgraph g (V, M ) is not accepted if M ⊂ M (minimality).
Let us consider several important examples. In general, rules that place constraints on the size of connected components admit trees as structural motifs. For example, a spanning tree is a minimal acceptable subgraph, and thus a structural motif, for all-terminal reliability. Note that the use of "minimal" means that each edge in the subgraph is required for it to be accepted, and not that the subgraph itself contains no more edges than any other accepted subgraph. For example, for 2-terminal reliability, any loop-free path -not just the shortest paths -from vertex S to vertex T is a structural motif. For a coherent rule, adding an edge to a path creates an accepted, but no longer minimal, graph.
We motivate the Inclusion-Exclusion argument with a few straightforward examples.

Example 1: A single structural motif
Suppose the graph contains only one structural motif and that it is a set of k 0 edges. For example, for 2-terminal reliability, suppose that there is exactly one path between S and T , and that it has length k 0 . Then the motif will occur exactly once among all subgraphs of size k 0 . For k > k 0 , think of "using up" k 0 edges on the structural motif. This leaves E − k 0 other edges from which, because the rule is assumed to be coherent, any set of k − k 0 produces an acceptable subgraph of size k. Hence for this case

Example 2: Two disjoint structural motifs
Suppose the graph has exactly two structural motifs, and that both have k 0 edges, and no edge is in both. Arguing as above, for k < 2k 0 , R k is simply twice what it is for the case of a single motif. But when k = 2k 0 , the subgraph that consists of the union of the two motifs will have been counted twice instead of once. Similarly, for k > 2k 0 , the number of graphs overcounted is given by assigning 2k 0 of the edges and choosing the remaining k−2k 0 in the subgraph from among the remaining E−2k 0 in the base graph. Hence:

Example 3: Three disjoint structural motifs
Suppose the graph has exactly three structural motifs, that all three have k 0 edges, and that the three edge sets are disjoint. Again, when k 0 ≤ k < 2k 0 , each motif generates E−k0 k−k0 different reliable subgraphs, and for 2k 0 = k, three of these subgraphs are counted twice. But in this case, when k reaches 3k 0 , the subgraph consisting of all three motifs is first included three times (once for each motif), then excluded three times (once for each pair of motifs) with the net result that it must be included again:

Example 4: N disjoint structural motifs
Suppose the graph has exactly N structural motifs, that all have k 0 edges, and that the N edge sets are disjoint. (Thus N ≤ E/k 0 .) Applying the arguments above, with the convention that a b = 0 ∀b < 0, gives:

Example 5: Two overlapping structural motifs
Suppose the graph has exactly two structural motifs, that both have k 0 edges, and that the number of edges in the union of the two is k 0 + ∆. Arguing as in Example 1, we get a similar result, with 2k 0 replaced by k 0 + ∆: 6. The general case Suppose the graph has exactly N structural motifs. As above, its reliability polynomial will be determined by the size of each structural motif and the overlaps among them. Define N (l) k as the number of combinations of l structural motifs whose union contains exactly k edges. Also, define Then arguing as above gives In Appendix A, we present constraints on N k . Given the rather complicated relationship between R k and N k in Equation 15, it is somewhat surprising that R(x) can be expressed very simply in terms of N k . Consider the contribution of a single structural motif of size k 0 to R(x). Using Equation 15, Since the effect of each structural motif, and each motif overlap, is additive on R k , we can reduce the general case to sums like the above, so we immediately find: Thus the N k defined in Equation 14 are indeed the same coefficients as those introduced in Equation 4.

F. Alternative damage models
The reasoning above is all done in the context of the usual edge damage model introduced by Moore and Shannon. This damage model is appropriate for studying bond percolation. An entirely analogous set of arguments applies to a vertex damage model, in which a set of k vertices is chosen uniformly at random, producing a unique subgraph containing all the edges whose endpoints are both in the selected set of vertices. This damage model is appropriate for studying site percolation. Coefficients analogous to P k and N k can be derived (substituting the number of vertices V for the number of edges E wherever it appears) and structural motifs can be defined in terms of vertex removal instead of edge removal. The physical interpretation of N k in terms of these structural motifs is the same. It is likely that there are many other damage models with these properties. Here, we consider only the edge damage model, because it serves to illustrate the role of structural motifs and its analysis is simpler.

III. PERTURBATIVE ESTIMATES OF RELIABILITY
Since R(x) is defined for x in the interval [0, 1], it is tempting to think that the lowest-order term in x that appears in the reliability polynomial, i.e. N kmin x kmin , is a good estimate of its value. Unfortunately, because the coefficients N k may grow combinatorially and may be either positive or negative, the leading order coefficient may not be sufficient to determine behavior of the reliability polynomial far from 0. Nevertheless, evaluating the lowest-order term provides insight into the relationship between graph structure and reliability. In this section, we illustrate how the study of motifs and their overlaps could help estimate reliability under several different rules.

A. All-terminal reliability
Recall that the structural motifs for the all-terminal rule are spanning trees. Each such tree has exactly V − 1 edges. N V −1 is thus the number of spanning trees, so the lowest-order term in the reliability polynomial is [8] gives N V −1 in terms of a cofactor of the graph Laplacian matrix.

B. Any-α-terminal reliability
The structural motifs for the any-α-terminal reliability rule are minimal subgraphs that contain at least α vertices. The minimality constraint means that all structural motifs are trees with exactly α − 1 edges. Letting N (1) α−1 = t be the number of such trees, the leading order term in R(x) is tx α−1 . Higher-order terms depend on how the trees overlap. We can use this to establish lower and upper bounds on R(x). The lower bound is tight for one particular choice of α in the sense that there exists a graph with that reliability. The upper bound does not appear to be tight.
The lower bound is generated by graphs that minimize the coefficient of the next higher order term x α . This in turn requires that as many as possible of the motifs overlap in all but one edge. For example, beginning with a single tree, we can change one edge to any other edge that is not already in the tree and does not create a loop in the tree. There are at most E − (α − 1) ways to do this, depending on the graph. Thus there is a graph with t trees, each of which contains α vertices, each of which differs from any other by exactly 2 edges, if and only if t ≤ E + 2 − α. In this case, N Substituting into the expressions Eq 3 and Eq 4 and simplifying gives R(x) = x α−2 (1 − x) t for this case. As far as we know, this particular tree structure occurs only for α = E − 1. The graph in which it occurs has a central vertex of degree t connected to t linear chains of length E/t (thus t must divide E evenly). The trees contain every edge except the last edge on one of the chains.
An upper bound is generated by graphs in which all t structural motifs are disjoint. (This can be arranged for a connected graph.) In this case, we have by inspection that the only non-zero N coefficients are N (k) It is not obvious when such a graph exists.

IV. ANALYTICAL BOUNDS ON AR-α RELIABILITY
Satisfying the AR-α rule demands that the sum of squared component sizes equals or exceeds αV 2 . What do the motifs that achieve this look like? Consider a partition Π of V , i.e. a set of positive integers π i whose sum is V . The number of elements in Π varies from one partition to another. Then π i could represent the number of vertices in the ith connected component. Furthermore, if each component is a tree, the number of edges in the ith component is just π i − 1, hence the number of edges in the entire subgraph is i (π i − 1) = V − C, where C = |Π| is the number of components. There are many ways to assign vertices to components, even for a single Π. Each will generate a different motif, as long as the reliability condition i π 2 i ≥ αV 2 is satisfied. The smallest number of edges results from a subgraph with the largest number of components. The result is that k min , the size of the smallest structural motif, is the size of a subgraph with all isolated vertices except for one large tree with v vertices. k min can be determined by the constraint or Thus and N kmin is the number of different trees that can be made with k min edges.
In general, we expect structural motifs with k min edges to dominate the reliability, because they appear as coefficients of the lowest order non-zero term in x. However, if there are very few different trees with k min edges (specifically, if N kmin N 1+kmin x), the contribution of N kmin may be overcome by larger structural motifs.

V. RELIABILITY FOR COMPLETE BIPARTITE GRAPHS
Vertices in a complete bipartite graph are divided into two disjoint sets s 1 and s 2 with v 1 and v 2 vertices, respectively. Vertices in s 1 are not connected with vertices in s 1 and vertices in s 2 are not connected with vertices in s 2 . Bipartite graphs in which s 1 represents people and s 2 represents locations, e.g. buildings, can be used to derive a physical contact network relevant to disease spread [9]. In a complete bipartite graph, every vertex belonging to s 1 is connected with all vertices in s 2 . The total number of edges is |s 1 ||s 2 |. Complete bipartite networks can represent critical infrastructure networks such as sensor networks and Internet Exchange where multiple geographical locations are connected with few high traffic Ethernet switches [10].

B. ST-terminal reliability
There are two possibilities to address the ST-terminal reliability: 1) S ∈ s 1 and T ∈ s 2 and vice versa and 2) both S and T belong to either s 1 or s 2 .
1. S ∈ s 1 and T ∈ s 2 , a structural motif is a path from S to T with an odd number of edges. For every odd k, Table I summarizes the evaluation of the first seven N k coefficients using the first 3 possible overlaps.
2. When both S and T belong to either s 1 or s 2 , the structural motifs are paths composed of an even number of edges. Assume both S and T are in s 1 . For every even k and Table II summarizes the evaluation of the first 6 N k coefficients using the first 3 possible overlaps.
We illustrate the power of this approach by evaluating the all-terminal and ST -reliability for all connected graphs on V vertices with either V − 1, V , or V + 1 edges. For all-terminal reliability, the calculations below are a version of the well-known parallel-series graph reduction techniques for evaluating the Tutte polynomial of a graph, as explained in [5] and illustrated on a toy network in Figure 1. However, for other reliability rules, including ST-reliability, we know of no general method for obtaining these results so easily.
This graph is a tree.

All-terminal reliability
The only structural motif is the graph itself, and its all-terminal reliability is simply R AT (x) = x V −1 .

ST-reliability
There is exactly one path between any pair of vertices. If the length of that path is d, then the ST -reliability is This graph contains a single loop. The vertices of the loop may be attached to trees of arbitrary size. Figure 2 shows a schematic example of the graph's structure. Let the number of edges in the loop be denoted l.

All-terminal reliability
Each subgraph with exactly one edge deleted from the loop is a structural motif, and there are no others. Thus there are l motifs, and the union of any two or more motifs contains all E = V edges. Hence, using Equa-

ST-reliability
Either both S and T are on the loop, or only one is, or neither is. The possible cases are, in the notation of of these paths are l 1 and l 2 , where l 1 + l 2 = l.
where T 1 is an arbitrary vertex in the same tree as S 1 : Clearly, R ST (x) = x d , where d is the distance between S 1 and T 1 .
3. S = S 1 , T = T 2 , where T 1 is an arbitrary vertex that is neither on the loop nor in the same tree as S 1 : Denote the distance from T 2 to A by d 2 . Arguing as in the previous case, where one vertex is on the loop and the other is not. This is a special case of (3) with d 2 = 0.
This graph contains at least 2 loops. The loops either share one or more edges or they share a single vertex or they don't share anything. These possibilities are shown schematically in Figure 5. Let I 3 be the number of shared edges (this choice is arbitrary, depending on how the "loops" are identified). If I 3 > 0, there are two distinguished vertices at the ends of the segment shared by the loops, as shown in the top half of Figure 5. If no edges are shared between the loops, the graph appears as in the bottom half of Figure 5. The case in which the loops share one vertex but no edges is given by I 3 = 0 in the top half of the figure or s = 0 in the bottom -A and B coincide in that case.

All-terminal reliability
If s > 0, then any single edge from any 2 of the 3 parallel segments may be deleted to obtain a structural motif. There are N V −1 = l 1 l 2 + l 2 l 3 + l 1 l 3 ways to accomplish this. The unions of motifs must have either V or V + 1 edges.
Using the identity E k=0 N k = 1, we can obtain N V +1 and R AT (x) is If s = 0, then any single edge from each of the two loops may be deleted to obtain a structural motif. Using the notation of Figure 5b, let l a ≡ l 1 + l 2 and l b ≡ l 3 + l 4 . There are N V −1 = l a l b motifs. Once again, the unions of motifs will have either V or V + 1 edges. In this case, Given only values for R(x), we can distinguish between the two possible topologies and evaluate the lengths l. This is what we mean by network tomography. It is in this sense that R(x) characterizes the network Figure 5.

ST-reliability
We consider only the cases in which the source and terminus are both on one of the loops. As shown above, the remaining cases can be derived easily from these.
1. s > 0 and S and T are on the same segment between A and B: Without loss of generality, let the segment containing S and T be the segment labeled 1. There are three motifs. If there are d ≤ l 1 edges between S and T on segment 1, the other motifs contain l 1 + l 2 − d and l 1 + l 3 − d edges. Two pairs of motifs are disjoint; one pair has l 1 + l 2 + l 3 − d edges in its union. The triple of motifs has l 1 +l 2 +l 3 edges in its union. Hence (29) 2. s > 0 and S and T are on different segments between A and B: Assuming S on the first segment labeled as l 1 at distance d 1 ≤ l 1 from B and T on segment l 2 with d 2 ≤ l 2 far from B. There are four motifs with following sizes: d 1 +d 2 , l 1 +l 2 −d 1 −d 2 , d 1 + l 3 + l 2 − d 2 and l 1 − d 1 + l 3 + d 2 . Overlap of every pair of these motifs makes a total of six unions with sizes: l 1 + l 2 ,l 2 + l 3 + d 1 ,l 2 + l 3 + d 2 ,l 1 + l 2 + l 3 − d 1 ,l 1 + l 2 + l 3 − d 2 and l 1 + l 2 + l 3 . Then there are four triplets and one quartet of motifs all with the same unions size of l 1 + l 2 + l 3 .
This leads to: There are six pairs of motifs, and the sizes of their unions are distributed according to: There are four triplets and one quartet of motifs, and their unions all have size l a + l b + s. This yields We have confirmed these analytical results with numerical estimates of coefficients obtained from specific instances of graphs, for example see Figure 4. The analysis above could be extended to arbitrary numbers of edges for planar graphs using an Euler identity for the number of loops.

VII. APPLYING RELIABILITY CONCEPTS TO OTHER NETWORK ANALYSIS PROBLEMS
The representation of the reliability polynomial in terms of structural motifs provides a convenient organizing principle for thinking about general network analysis problems. As one example, consider the tradeoffs between two systems: one with only a few completely redundant reliable subsytems and another with more, but only partially redundant, ones. To study this we consider two extreme cases of overlap. One contains r 1 structural motifs of size k 1 , any two of which differ by only two edges. They are thus built using a total of 2r 1 + k 1 − 2 edges. The reliability of this combination can be written as: Using the same number of edges we can construct r 2 = 2r1+k1−2 k2 motifs of size k 2 that are completely disjoint. The reliability of this combination of motifs is: Knowing the reliability for these two cases, we are able to compare the reliability of networks with different configurations of structural motifs of different sizes. As an example we compared the reliability of a network composed of 20 motifs with 18 edges that are different from  6. Comparing reliability of a network of many subgraphs with large overlap and few motifs without any overlap. one another only in two edges with a network of 4 completely disjoint motifs of size 6. Figure 6 shows the reliability curves for these two networks and their difference as a function of x. The analysis shows that the network of disjoint motifs is more reliable for smaller values of x while it is the opposite for larger x values.
This approach could also be used to explore the number of spanning trees in a graph. A spanning tree is a subgraph of the network that includes all vertices [12][13][14]; therefore it can simply be evaluated by counting the number of structural motifs under the all terminal reliability rule. Another problem that can be addressed using this method is to identify chordless loops of various sizes in a network. A chordless loop is a sequence of vertices with more than 3 vertices if for all i = 1, · · · , k there is exactly one link from vertex v i to v i+1 and there is no other link between any two of the vertices in this sequence [15]. Recent studies on ecological networks have discovered the existence of many chordless cycles in these networks [16], therefore enumeration of all chordless cycles can make a significant impact on understanding the structure of these networks. An appropriately-designed reliability rule can be used to count the number of chordless cycles of different sizes.

VIII. CONCLUSION AND FUTURE WORK
In this paper we focused on the representation of the reliability polynomial in terms of structural motifs. We have shown that network reliability is simply related to the number of edges in unions of structural motifs N k (17). Whereas the coefficients P k of x k (1 − x) E−k are easy to estimate and hard to work with analytically, the coefficients N k of x k are hard to estimate but easy to work with analytically. To demonstrate this, we have derived closed-form expressions for N k for several types of graphs. The resulting expressions were confirmed by numerical estimation. We anticipate that this approach can lead us to a measure of edge centrality that relates the importance of an edge to the frequency of its appearance in different structural motifs [17]. While we can use numerical simulation to study specific large, realistic networks -including epidemiology on social networks [9,18,19] -we can use the notion of structural motifs to understand the differences between networks that are discovered in simulation. We expect this approach to be particularly useful in studying the stability and robustness of interconnected networks [20,21]. Several constraints apply to N k . A union of l motifs can have size k only if all possible unions of l − 1 of the same motifs have size less than k. This leads to a set of constraints of the form In addition, a union of l motifs can have size k only if all possible unions of l − 1 and l − 2 of the same motifs have size less than k. For instance, N k has the following upper bound Overall, since all structural motifs must be included in the subgraph of size E, we have