text:
Learning Hyperedge Replacement Grammars for Graph Generation

The discovery and analysis of network patterns are central to the scientific enterprise. In the present work, we developed and evaluated a new approach that learns the building blocks of graphs that can be used to understand and generate new realistic graphs. Our key insight is that a graph's clique tree encodes robust and precise information. We show that a Hyperedge Replacement Grammar (HRG) can be extracted from the clique tree, and we develop a fixed-size graph generation algorithm that can be used to produce new graphs of a specified size. In experiments on large real-world graphs, we show that graphs generated from the HRG approach exhibit a diverse range of properties that are similar to those found in the original networks. In addition to graph properties like degree or eigenvector centrality, what a graph"looks like"ultimately depends on small details in local graph substructures that are difficult to define at a global level. We show that the HRG model can also preserve these local substructures when generating new graphs.

Introduction
Teasing out signatures of interactions buried in overwhelming volumes of information is one of the most basic challenges in scientific research. Understanding how information is organized and how it evolves can help us discover its fundamental underlying properties. Researchers do this when they investigate the relationships between diseases, cell functions, chemicals, or particles, and we all learn new concepts and solve problems by understanding the relationships between the various entities present in our everyday lives. These entities can be represented as networks, or graphs, in which local behaviors can be understood, but whose global view is highly complex.
Discovering and analyzing network patterns to extract useful and interesting patterns (building blocks) is critical to the advancement of many scientific fields. Indeed the most pivotal moments in the development of a scientific field are centered on discoveries about the structure of some phenomena [1]. For example, biologists have agreed that tree structures are useful when organizing the evolutionary history of life [4,5], and sociologists find that triadic closure underlies community development [6,7]. In other instances, the structural organization of the entities may resemble a ring, a clique, a star, a constellation, or any number of complex configurations.
Unfortunately, current graph mining research deals with small pre-defined patterns [8,9] or frequently reoccurring patterns [10,11,12,13], even though interesting and useful information may be hidden in unknown and non-frequent patterns. Principled strategies for extracting these complex patterns are needed to discover the precise mechanisms that govern network structure and growth. In-depth examination of this mechanism leads to a better understanding of graph patterns involved in structural, topological, and functional properties of complex systems. This is precisely the focus of the present work: to develop and evaluate techniques that learn the building blocks of real-world systems that, in aggregate, succinctly describe the observed interactions expressed in a network.
These networks exhibit a long and varied list of global properties, including heavy-tailed degree distributions [14], and interesting community structures [15] to name a few. Recent work has found that these global properties are products of a graph's local properties [17,18]. In the present work, our goal is to learn the local structures that, in aggregate, help describe the interactions observed in the network and generalize to applications across a variety of fields like computer vision, computational biology, and graph compression.
The key insight for this task is that a network's clique tree encodes robust and precise information about the network. A hyperedge replacement grammar (HRG), extracted from the clique tree, contains graphical rewriting rules that can match and replace graph fragments similar to how a context-free grammar (CFG) rewrites characters in a string. These graph fragments represent a succinct, yet complete description of the building blocks of the network, and the rewriting rules of the HRG describe the instructions on how the graph is pieced together.
The HRG framework is divided into two steps: 1) graph model learning and 2) graph generation. After reviewing some of the theoretical foundations of clique trees and HRGs, we show how to extract an HRG from a graph. These graph rewriting rules can be applied randomly to generate larger and larger graphs. However, scientists typically have a specific size in mind, so we introduce a fixed-size graph generation algorithm that will apply HRG rules to generate a realistic graph of a user-specified size.
Finally, we present experimental results that compare the generated graphs with the original graphs. We show that these generated graphs exhibit a broad range of properties that are very similar to the properties of the original graphs and outperform existing graph models across a variety of graph comparison metrics.

Preliminaries
The new work in this paper begins where previous work [21,22,23,24] left off. However, before we begin, some background knowledge is crucial to understand the key insights of our main contributions.
We begin with an arbitrary input hypergraph H = (V, E), where V is a finite set of vertices and E ⊆ V + is a set of hyperedges. A hyperedge e ∈ E can connect one or more ordered vertices and is written e = (v 1 , v 2 , . . . , v k ). Common graphs (e.g., social networks, Web graphs, information networks) are a particular case of hypergraphs where each edge connects exactly two vertices. For convenience, all of the graphs in this paper will be simple, connected and undirected, although these restrictions are not vital. In the remainder of this section, we refer mainly to previous developments in clique trees and their relationship to hyperedge replacement grammars in order to support the claims made in sections 3 and 4.

Clique Trees
All graphs can be decomposed (though not uniquely) into a clique tree, also known as a tree decomposition, junction tree, join tree, intersection tree, or cluster graph. Within the pattern recognition community, clique trees are best known for their role in exact inference in probabilistic graphical models, so we introduce the preliminary work from a graphical modeling perspective; for an expanded introduction, we refer the reader to Chapters 9 and 10 of Koller and Friedman's textbook [25].
is a tree CT , each of whose nodes η is labeled with a V η ⊆ V and E η ⊆ E, such that the following properties hold: 2. Edge Cover: For each hyperedge e i = {v 1 , . . . , v k } ∈ E there is exactly one node η ∈ CT such that e ∈ E η . Moreover, v 1 , . . . , v k ∈ V η .

Definition 2.2
The width of a clique tree is max(|V η − 1|), and the treewidth of a graph H is the minimal width of any clique tree of H.
Unfortunately, finding the optimal elimination ordering and corresponding minimal-width clique tree is NP-Complete [26]. Fortunately, many reasonable approximations exist for general graphs: in this paper, we employ the commonly used maximum cardinality search (MCS) heuristic introduced by Tarjan and Yannikakis [27] to compute a clique tree with a reasonably-low, but not necessarily minimal, width.
Simply put, a clique tree of any graph (or any hypergraph) is a tree. Each of whose nodes we label with nodes and edges from the original graph, such that vertex cover, edge cover and the running intersection properties hold, and the "width" of the clique tree measures how tree-like the graph is. The reason for the interest in finding the clique tree of a graph is because many computationally difficult problems can be solved efficiently when the data is constrained to be a tree. Figure 1 shows a graph and its minimal-width clique tree (showing V η for each node η). We label nodes with lowercase Latin letters. We will refer back to this graph and clique tree as a running example throughout this paper.

Hyperedge Replacement Grammar
The key insight for this task is that a network's clique tree encodes robust and precise information about the network. An HRG, extracted from the clique-tree, contains graphical rewriting rules that can match and replace graph fragments similar to how a context-free Grammar (CFG) rewrites characters in a string. These graph fragments represent a succinct, yet complete description of the building blocks of the network, and the rewriting rules of the HRG describe the instructions on how the graph is pieced together. For a thorough examination of HRGs, we refer the reader to the survey by Drewes et al. [28]. Definition 2.3 A hyperedge replacement grammar is a tuple G = N, T, S, P , where 1. N is a finite set of nonterminal symbols. Each nonterminal A has a nonnegative integer rank, which we write |A|.

2.
T is a finite set of terminal symbols.
4. P is a finite set of production rules A → R, where • A, the left hand side (LHS), is a nonterminal symbol.
• R, the right hand side (RHS), is a hypergraph whose edges are labeled by symbols from T ∪ N . If an edge e is labeled by a nonterminal B, we must have |e| = |B|.
• Exactly |A| vertices of R are designated external vertices and numbered 1, . . . , |A|. The other vertices in R are called internal vertices.
When drawing HRG rules, we draw the LHS A as a hyperedge labeled A with arity |A|. We draw the RHS as a hypergraph, with external vertices drawn as solid black circles and the internal vertices as open white circles.
If an HRG rule has no nonterminal symbols in its RHS, we call it a terminal rule. If an HRG rule has exactly one nonterminal symbol in its RHS, we call it a unary rule. Definition 2.4 Let G be an HRG and P = (A → R) be a production rule of G. We define the relation H ⇒ H * (H * is derived in one step from H ) as follows. H must have a hyperedge e labeled A; let v 1 , . . . , v k be the vertices it connects. Let u 1 , . . . , u k be the external vertices of R. Then H * is the graph formed by removing e from H , making an isomorphic copy of R, and identifying v i with the copies of u i for each i = 1, . . . , k.
Let ⇒ * be the reflexive, transitive closure of ⇒. Then we say that G generates a graph H if there is a production S → R and R ⇒ * H and H has no edges labeled with nonterminal symbols.
In other words, a derivation starts with the symbol S, and we repeatedly choose a nonterminal A and rewrite it using a production A → R. The replacement hypergraph fragments R can itself have other nonterminal hyperedges, so this process repeats until there are no more nonterminal hyperedges. The following sections illustrate these definitions more clearly.

Learning HRGs
The first step in learning an HRG from a graph is to compute a clique tree from the original graph. Then, this clique-tree directly induces an HRG, which we demonstrate in this section.

Binarization
Just as context-free string grammars are more convenient to parse if put into Chomsky normal form (CNF), we also assume, without loss of generality, that our HRG also follows CNF. This means that each rule's right-hand side has at most two nonterminals. By the HRG induction methods presented later in this section, each clique tree node η yields an HRG rule, and the number of children of η determines the number of nonterminals on the right-hand side of the resulting rule. Thus, it suffices for the clique tree to have a branching factor of at most two. Although the branching factor of a clique tree may be greater than two, it is always easy to binarize it. There is more than one way to do this; we use the following scheme. Let η be a clique tree node with children η 1 , . . . , η d , where d > 2 (here d corresponds to the number of children for a given parent node). These are labeled with bags V η , V η 1 , . . . , V η d , respectively. Make a copy of η; call it η , and let V η = V η . Let the children of η be η 1 and η , and let the children of η be η 2 , . . . , η r . See Fig. 2 for an example. Then, if η has more than two children, apply this procedure recursively to η .
It is easy to see that this procedure terminates and results in a clique tree whose nodes are at most binary-branching and still has the vertex cover, edge cover, and running intersection properties for H.

Clique Tree Pruning
Later we will introduce a dynamic programming algorithm for constructing graphs that require every leaf node of the clique tree to have at least one internal vertex. Clique tree algorithms, such as the MCS algorithm used in this paper, do no guarantee these conditions. Fortunately, we can just remove these leaf nodes from the clique tree.
The bottom-right clique tree node in Fig. 1 is such an example because f is an external vertex; that is, f exists in its parent. Because no internal vertices exist in this leaf node, it is removed from the clique tree. The clique tree node with vertices e and f is now a leaf, as illustrated in the left side of Fig. 3. Vertices e and f in the new leaf node are still both external vertices, so this clique tree node must also be removed creating a final clique tree illustrated in the right side of Fig. 3.

Clique Trees and HRGs
Here we show how to extract an HRG from the clique tree. Let η be an interior node of the clique tree CT , let η be its parent, and let η 1 , . . . , η m be its children. Node η corresponds to an HRG production rule A → R as follows. First, |A| = |V η ∩ V η |. Then, R is formed by: • Adding an isomorphic copy of the vertices in V η and the edges in E η • Marking the (copies of) vertices in V η ∩ V η as external vertices  We choose nonterminal symbol N for the LHS, which must have rank 3 because η has 3 vertices in common with its parent. The RHS is a graph whose vertices are (copies of) V η = {b, c, d, e}. Vertices c, d and e are marked external (and numbered 1, 2, and 3, arbitrarily) because they also appear in the parent node. The terminal edges are E η = {(b, c), (b, d)}. There is only one child of η, and the nodes they have in common are b and e, so there is one nonterminal hyperedge connecting b and e.
Next we deal with the special cases of the root and leaves.
Root Node. If η is the root node, then it does not have any parent cliques, but may still have one or more children. Because η has no parent, the corresponding rule has a LHS with rank 0 and a RHS with no external vertices. In this case, we use the start nonterminal symbol S as the LHS, as shown in Fig. 5. The RHS is computed in the same way as the interior node case. For the example in Fig. 5, the RHS has vertices that are copies of c, d, and e. In addition, the RHS has two terminal hyperedges, Leaf Node. If η is a leaf node, then the LHS is calculated the same as in the interior node case. Again we return to the running example in Fig. 6. Here, we focus on the leaf node {a, b, e}, outlined in bold. The LHS has rank 2, because η has two vertices in common with its parent.
The RHS is computed in the same way as the interior node case, except no new nonterminal hyperedges are added to the RHS. The vertices of the RHS are (copies of) the nodes in η, namely, a, b, and e. Vertices b and e are external because they also appear in the parent clique. This RHS has two terminal hyperedges, E η = {(a, b), (a, e)}. Because the leaf clique has no children, it cannot produce any nonterminal hyperedges on the RHS; therefore this rule is a terminal rule.

Top-Down HRG Rule Induction
We induce production rules from the clique tree by applying the above extraction method top down. Because trees are acyclic, the traversal order does not matter, yet there are some interesting observations we can make about traversals of moderately sized graphs. First, exactly one HRG rule will have the special starting nonterminal S on its LHS; no mention of S will ever appear in any RHS. Similarly, the number of terminal rules is equal to the number of leaf nodes in the clique tree. Larger graphs will typically produce larger clique trees, especially sparse graphs because they are more likely to have a greater number of small maximal cliques. These larger clique trees will produce a large number of HRG rules, one for each clique in the clique tree. Although it is possible to keep track of each rule and its traversal order, we find, and will later show in the experiments section, that the same rules often repeat many times. Figure 7 shows the 4 rules that are induced from the clique tree illustrated in Fig. 1 and used in the running example throughout this section.

Graph Generation
In this section, we show how to use the HRG extracted from the original graph H (as described in the previous section) to generate a new graph H * . Ideally, H * will be similar to or have features that are akin or analogous to the original graph H. We present two generation algorithms. The first generates random graphs with similar characteristics to the original graph. The second is like it but generates random graphs that have a specified number of nodes.

Stochastic Generation
There are many cases in which we prefer to create very large graphs in an efficient manner that still exhibit the local and global properties of some given example graph. Here we describe a simple stochastic hypergraph generator that applies rules from the extracted HRG to efficiently create such graphs.
In larger HRGs we usually find many A → R production rules that are identical. We chose to consider rules that are identical modulo a permutation of their external vertices to be equivalent as well. We can merge these duplicates by matching rule-signatures in a dictionary and keep a count of the number of times that each distinct rule has been seen. For example, if there were some extra Rule #5 in Fig. 7 that was identical to, say, Rule #3, then we would simply note that we saw Rule #3 two times.
To generate random graphs from a probabilistic HRG (PHRG), we start with the special starting nonterminal H = S. From this point, H * can be generated as follows: (1) Pick any nonterminal A in H ; (2) Find the set of rules (A → R) associated with LHS A; (3) Randomly choose one of these rules with probability proportional to its count; (4) Choose an ordering of its external vertices with uniform probability; (5) Replace A in H with R to create H * ; (5) Replace H with H * and repeat until there are no more nonterminal edges.

Fixed-Size Generation
A problem we find with the stochastic generation procedure is that, although the generated graphs have the same mean size as the original graph, the variance is much too high to be useful. So we want to sample only graphs whose size is the same as the original graph's, or some other userspecified size. Naively, we can do this using rejection sampling: sample a graph, and if the size is not right, reject the sample and try again. However, this would be quite slow. Our implementation uses a dynamic programming approach to sample a graph with specified size, while using quadratic time and linear space, or approximately while using linear time and space.
More formally, the learned PHRG defines a probability distribution over graphs, P (H * ). But rather than sampling from P (H * ), we want to sample from P (H * | |H * | = n), where n is the desired size.
Here, the stochastic generation sampling procedure is modified to rule out all graphs of the wrong size, as follows. Define a sized nonterminal X ( ) to be a nonterminal X together with a size > 0. If n is the desired final size, we start with S (n) , and repeatedly: 1. Choose an arbitrary edge labeled with a sized nonterminal (call it X ( ) ).

Choose a rule from among all rules with LHS X.
3. Choose sizes for all the nonterminals in the rule's RHS such that the total size of the RHS is .
4. Choose an ordering of the external vertices of the rule's RHS, with uniform probability.

Apply the rule.
A complication arises when choosing the rule and the RHS nonterminal sizes (steps 2 and 3) because the weights of these choices no longer form a probability distribution. Removing graphs with the wrong size causes the probability distribution over graphs to sum to less than one, and it must be renormalized [29]. To do this, we precompute a table of inside probabilities α[X, ] for = 1, . . . , n, each of which is the total weight of derivations starting with X and yielding a (sub)graph of size exactly . These are computed using dynamic programming, as shown in Algorithm 1.
If X → R is a HRG rule, define size(R) to be the increase in the size of a graph upon application of rule (X → R). If size is measured in vertices, then size(R) is the number of internal vertices in R.
Rules that are unary and have zero size require some special care because they do not change the size of the graph. If there is a unary size-zero rule X → Y , we need to ensure that α[Y, ] is computed before α[X, ], or else the latter will be incorrect. Thus, in Algorithm 1, we start by forming a weighted directed graph U whose nodes are all the nonterminals in N , and for every unary rule X p − → Y , there is an edge from X to Y with weight p. We perform a topological sort on U , and the loop over nonterminals X ∈ N is done in reverse topological order.
However, if U has a cycle, then no such ordering exists. The cycle could apply an unbounded number of times, and we need to sum over all possibilities. Algorithm 2 handles this more general Algorithm 1: Compute inside probabilities (no cycles of size-zero unary rules) compute digraph U of unary size-zero rules; topologically sort U ; assert (U is acyclic); for ← 1, . . . , n do for X ∈ N in reverse topological order do for rules X case [30]. We precompute the strongly connected components of U , for example, using Tarjan's algorithm, and for each component C, we form the weighted adjacency matrix of C; call this U C .
gives the total weight of all chains of unary rules within C. So, after computing all the α[X, ] for X ∈ C, we apply the unary rules by treating the α[X, ] (for X ∈ C) as a vector and left-multiplying it by U * C . Some tricks are needed for numerical stability; for details, please see the released source code at https://github.com/nddsg/PHRG/.
In principle, a similar problem could arise with binary rules. Consider a rule X → R where R is zero-size and has two nonterminals, Y and Z. If α[Y, 0] > 0, then α[X, ] is defined in terms of α[Y, ], which could lead to a circularity. Fortunately, we can avoid such situations easily. Recall that after clique tree pruning (Sec. 3.2), every leaf of the clique tree has at least one internal vertex. In terms of HRG rules, this means that if R has no nonterminals, then size(R) > 0. Therefore, we have α[X, 0] = 0 for all X, and no problem arises.
Once we have computed α, we can easily sample a graph of size n using Algorithm 3. Initially, we start with the sized start nonterminal S (n) . Then, we repeatedly choose an edge labeled with a sized nonterminal X ( ) , use the table α of inside probabilities to recompute the weight of all the rewriting choices quickly, sample one of them, and apply it.

Pruning inside probabilities
The slowest step in the above method is the precomputation of inside probabilities (Alg. 2), which is quadratic in the number of vertices. To speed up this step up, we observe that randomly generated graphs tend to be highly unbalanced in the sense that if a rule has two nonterminal symbols, one is usually much larger than the other (see Figure 8). This is related to the fact, familiar with the study of algorithms, that random binary search trees tend to be highly unbalanced [31].
Therefore, we can modify Algorithm 2 to consider only splits where at most (say) 1000 nodes go to one nonterminal and the rest of the nodes go the other. This makes the algorithm asymptotically linear. else if R has nonterminals Y and Z then for

Experiments
Here we show that HRGs contain rules that succinctly represent the global and local structure of the original graph. In this section, we compare our approach against some of the state-of-theart graph generators. We consider the properties that characterize some real-world networks and compare the distribution of graphs generated using Kronecker Graphs, the Exponential Random Graph, Chung-Lu Graphs, and the graphs produced by the probabilistic hyperedge replacement graph grammar. Like HRGs, the Kronecker and Exponential Random Graph Models learn parameters that can be used to approximately recreate the original graph H or a graph of some other size such that the probabilistically generated graph holds many of the same properties as the original graph. The Chung-Lu graph model relies on node degree sequences to yield graphs that maintain this distribution. The probabilistically generated graphs are likely not isomorphic to the original graph. We can, however, still judge how closely the probabilistically generated graph resembles the original graph by comparing several of their properties.

real-world Datasets
To get a holistic and varied view of the strengths and weaknesses of HRGs in comparison to the other leading graph generation models, we consider real-world networks that exhibit properties that are both common to many networks across different fields, but also have certain distinctive properties.
The six real-world networks considered in this paper are described in Table 1. The networks vary in their number of vertices and edges as indicated, but also vary in clustering coefficient, diameter, degree distribution and many other graph properties. Specifically, Karate Club graph is else if R has nonterminals Y and Z then for k ← 1, . . . , ; sample sized RHS R from P (R); choose ordering of the external vertices of R; H ← H{X ( ) → R}; a network of interactions between members of a karate club; the Protein network is a protein-protein interaction network of S. cerevisiae yeast; the Enron graph is the email correspondence graph of the now defunct Enron corporation; the arXiv GR-QC graph is the co-authorship graph extracted from the General Relativity and Quantum Cosmology section of arXiv; the Internet router graph is created from traffic flows through Internet peers; DBLP is the co-authorship graph from the DBLP dataset; Amazon is the co-purchasing network from March 12, 2003; and, finally, Flickr is a network created from photos taken at the same location. In the following experiments, we use the larger networks (arXiv, Routers, Enron, DBLP, Amazon, Flickr) for network generation and the smaller networks (Karate, Protein) for a special graph extrapolation task. Datasets were downloaded from the SNAP and KONECT dataset repositories.  Figure 8: When an HRG rule has two nonterminal symbols, one is overwhelmingly likely to be much larger than the other. This plot shows, for various grammar rules (one LHS per row, one RHS per colored line), the probability (log scale) of apportioning 1024 nodes between two nonterminal symbols. This plot is best viewed in color.

Methodology
We compare several different graph properties from the four classes of graph generators (fixed-size HRG, Kronecker, Chung-Lu and exponential random graph (ERGM) models) to the original graph H. Other models, such as the Erdős-Rényi random graph model, the Watts-Strogatz small world model, the Barabási-Albert generator, etc. are not compared here because Kronecker, Chung-Lu and ERGM have been shown to outperform these earlier models when matching network properties in empirical networks. Kronecker graphs operate by learning an initiator matrix and then performing a recursive multiplication of that initiator matrix to create an adjacency matrix of the approximate graph. In our case, we use KronFit [32] with default parameters to learn a 2 × 2 initiator matrix and then use the recursive Kronecker product to generate the graph. Unfortunately, the Kronecker product only creates graphs where the number of nodes is a power of 2, i.e., 2 x , where we chose x = 15, x = 12, x = 13, and x = 18 for Enron, ArXiv, Routers and DBLP graphs respectively to match the number of nodes as close as possible.
The Chung-Lu Graph Model takes, as input, a degree distribution and generates a new graph of the similar degree distribution and size [33].
Exponential Random Graph Models are a class of probabilistic models. Their usefulness lies in that they directly describe several structural features of a graph [34]. We used default parameters in R's ERGM package [35] to generate graph models for comparison. In addition to the problem of model degeneracy, ERGMs do not scale well to large graphs. As a result, DBLP, Enron, Amazon, and Flickr could not be modelled due to their size, and the arXiv graph always resulted in a degenerate model. Therefore ERGM results are omitted from this section.
The main strength of HRG is to learn the patterns and rules that generate a large graph from only a few small subgraph-samples of the original graph. So, in all experiments, we make k random samples of size s node-induced subgraphs by a breadth first traversal starting from a random node in the graph [36]. By default we set k = 4 and s = 500 empirically. We then compute tree decompositions from the k samples, learn HRGs G 1 , G 2 , . . . , G k , and combine them to create a single grammar G = i G i . Unless otherwise noted, we generate 20 graphs each for the HRG, Chung-Lu, and Kronecker models and plot the mean values in the results section. We did compute the confidence intervals for each of the models but omitted them from the graphs for clarity. In general, the confidence intervals were small for HRG, Kronecker, and Chung-Lu.

Graph Generation Results
Here we compare and contrast the results of approximate graphs generated from the HRG, Kronecker, and Chung-Lu models. Before presenting each result, we briefly introduce the graph properties that we used to compare the similarity between the real networks and their approximate counterparts. Although many properties have been discovered and detailed in related literature, we focus on five of the principal properties from which most others can be derived.

Global Measures
A key goal of graph modelling to preserve certain network properties of the original graph (i.e., H as introduced in 2). Graphs generated using HRG, Kronecker, or Chung-Lu are analyzed by studying their fundamental network properties to assess how successful the model performs in generating graphs from parameters and production rules learned from the input graph. First, we look at  the degree distribution, eigenvector centrality, local clustering coefficient, hop plot, and assortative mixing characteristics, and draw conclusions on these results.

Degree Distribution.
The degree distribution of a graph is the distribution of the number of edges connecting to a particular vertex. Figure 9 shows the results of the degree distribution property on the six real-world graphs. Recall that the graph results plotted here and throughout the results section are the mean averages of 20 generated graphs. Each of the generated graphs is slightly different from the original graphs in their own way. As expected, we find that the power law degree distribution is captured by existing graph generators as well as the HRG model.

Eigenvector Centrality.
The principal eigenvector is often associated with the centrality or "value" of each vertex in the network, where high values indicate an important or central vertex and lower values indicate the opposite. A skewed distribution points to a relatively few "celebrity" vertices and many common nodes.
The principal eigenvector value for each vertex is also closely associated with the PageRank and degree value for each node. Figure 10 shows the eigenvector scores for each node ranked highest to lowest in each of the six real-world graphs. Because the x-axis represents individual nodes, Fig. 10 also shows the size difference among the generated graphs. HRG performs consistently well across all graphs, but the log scaling on the y-axis makes this plot difficult to discern. To more concretely compare the eigenvectors, the pairwise cosine distance between eigenvector centrality of H and the mean eigenvector centrality of each model's generated graphs appear at the top of each plot in order. HRG consistently has the lowest cosine distance followed by Chung-Lu and Kronecker.
Hop Plot. The hop-plot of a graph shows the number of vertex-pairs that are reachable within x hops. The hop-plot, therefore, is another way to view how quickly a vertex's neighborhood grows as the number of hops increases. As in related work [16] we generate a hop-plot by picking 50 random nodes and performing a complete breadth first traversal over each graph. Figure 11 demonstrates that HRG graphs produce hop-plots that are remarkably similar to the original graph.

Mean Clustering Coefficients.
A vertex's clustering coefficient is a measure of how well connected its neighbors are [40]. For each vertex in the graph, its clustering coefficient is the ratio of the number of edges in its ego-network (i.e., local neighborhood) to the total number of possible edges that could exist if the vertex's neighborhood was a clique. Calculating the clustering coefficient for each node is a computationally difficult task and difficult plot aesthetically, so we sampled 100 nodes from the graph randomly. Figure 12 shows the average clustering coefficients for the sampled nodes as a function of its degree in the graph. Like the results from Seshadhri et al., we find that the Kronecker and Chung-Lu models perform poorly at this task [15].
Local Degree Assortativity. The global degree assortativity of a graph measures its tendency to have high-degree vertices connect to high-degree vertices and vice versa measured as a Pearson correlation coefficient. The local degree assortativity is measured for each vertex as the amount that each vertex contributes to the overall correlation, i.e., how different the vertex is from its neighbors. Figure 13 shows the degree assortativity for each vertex from each generated graph. The last three graph metrics, k-core, local clustering coefficient, and local degree assortativity, all showed a relatively poor performance of the Chung-Lu and Kronecker graph generators. HRG modelled the k-core and local clustering coefficients rather well but had inconsistent results in the local degree assortativity plots.

Canonical Graph Comparison
The previous network properties primarily focus on statistics of the global network. However, there is mounting evidence which argues that the graphlet comparisons are a complete way to measure the similarity between two graphs [18,17]. The graphlet distribution succinctly describes the number of small, local substructures that compose the overall graph and therefore more completely represents the details of what a graph "looks like." Furthermore, it is possible for two very dissimilar graphs to have the same degree distributions, hop plots, etc., but it is difficult for two dissimilar graphs to fool a comparison with the graphlet distribution. Table 2: Graphlet Statistics and Graphlet Correlation Distance (GCD) for six real-world graphs.
First row of each section shows the original graph's graphlet counts, remaining row shows mean counts of 10 runs for each graph generator. We find that the HRG model generates graphs that closely approximate the graphlet counts of the original graph. Table 2 shows the mean graphlet counts over 10 runs for each graph generator. We find that graphlet counts for the graphs generated by HRG follow the original counts more closely, and in many cases much more closely, than the Kronecker and Chung-Lu graphs.
Graphlet Correlation Distance Recent work from systems biology has identified a new metric called the Graphlet Correlation Distance (GCD). The GCD computes the distance between two graphlet correlation matrices -one matrix for each graph [19]. It measures the frequency of the various graphlets present in each graph, i.e., the number of edges, wedges, triangles, squares, 4cliques, etc., and compares the graphlet frequencies of each node across two graphs. Because the GCD is a distance metric, lower values are better. The GCD can range from [0, +∞], where the GCD is 0 if the two graphs are isomorphic.
The rightmost column in Tab. 2 shows the GCD results. Unfortunately, the node-by-node graphlet enumerator used to calculate the GCD [19] could not process the large Amazon and Flickr graphs, so only the summary graphlet counts are listed for the two larger graphs [20]. The results here are clear: HRG significantly outperforms the Chung-Lu and Kronecker models. The GCD opens a whole new line of network comparison methods that stress the graph generators in various ways. We explore many of these options next.

Graph Extrapolation
Recall that HRG learns the grammar from k = 4 subgraph-samples from the original graph. In essence, HRG is extrapolating the learned subgraphs into a full-size graph. This raises the question: if we only had access to a small subset of some larger network, could we use our models to infer a larger (or smaller) network with the same local and global properties? For example, given the 34-node Karate Club graph, could we infer what a Karate Club might look like if it's membership doubled? Chung-Lu Kronecker Figure 14: GCD of graphs extrapolated in multiples up to 32x from two small graphs. HRG outperforms Chung-Lu and Kronecker models when generating larger graphs. Lower is better.
Using two smaller graphs, Zachary's Karate Club (34 nodes, 78 edges) and the protein-protein interaction network of S. cerevisiae yeast (see Table 1), we learned an HRG model with k = 1 and s = n, i.e., no sampling, and generated networks of size-n * = 2x, 3x, . . . , 32x. For the protein graph, we also sampled down to n * = x/8. Powers of 2 were used because the standard Kronecker model can only generate graphs of that size. The Chung-Lu model requires a size-n * degree distribution as input. To create the proper degree distribution we fitted a Poisson distribution (λ = 2.43) and a Geometric Distribution (p = 0.29) to Karate and Protein graphs respectively and drew n * degree-samples from their respective distributions. In all cases, we generated 20 graphs at each size-point.
Rather than comparing raw numbers of graphlets, the GCD metric compares the correlation of the resulting graphlet distributions. As a result, GCD is largely immune to changes in graph size. Thus, GCD is a good metric for this extrapolation task. Figure 14 shows the mean GCD scores; not only does HRG generate good results at n * = 1x, the GCD scores remain mostly level as n * grows.

Infinity Mirror
Next, we characterize the robustness of graph generators by introducing a new kind of test we call the infinity mirror. 1 One of the motivating questions behind this idea was to see if HRG holds sufficient information to be used as a reference itself. In this test, we repeatedly learn a model from a graph generated by an earlier version of the same model. For HRG, this means that we learn a set of production rules from the original graph H and generate a new graph H * ; then we set H ← H * and repeat whereby learning a new model from the generated graph recursively. We repeat this process ten times and compare the output of the 10th recurrence with the original graph using GCD.
We expect to see that all models degenerate over ten recurrences. The question is, how quickly do the models degenerate and how badly do the graphs become? Figure 15 shows the GCD scores for the HRG, Chung-Lu and Kronecker models at each recurrence (we have also validated the Infinity Mirror tests with other variations to the Chung-Lu model including the Block Two-Level Erdős-Rényi Model with similar results [41]). Surprisingly, we find  that HRG stays steady, and even improves its performance while the Kronecker and Chung-Lu models steadily decrease their performance as expected. We do not yet know why HRG improves performance in some cases. Because GCD measures the graphlet correlations between two graphs, the improvement in GCD may be because HRG is implicitly homing in on rules that generate the necessary graph patterns.

Infinity Mirror Model Size
The number of production rules derived from a given graph using Fixed-Size Graph Generation. Fig. 16 shows the number of nodes in graphs after 1, 5, and 10 feedback iterations. The trend for each input graph varies slightly, but in general the model-size (i.e., the number of production rules derived) stays flat.

Sampling and Grammar Complexity
We have shown that HRG can generate graphs that match the original graph from k = 4 samples of s = 500-node subgraphs. If we adjust the size of the subgraph, then the size of the clique tree will change causing the grammar to change in size and complexity. A large clique tree ought to create more rules and a more complex grammar, resulting in a larger model size and better performance; while a small clique tree ought to create fewer rules and a less complex grammar, resulting in a smaller model size and a lower performance.
To test this hypothesis, we generated graphs by varying the number of subgraph samples k from 1 to 32, while also varying the size of the sampled subgraph s from 100 to 600 nodes. Again, we generated 20 graphs for each parameter setting. Figure 17 shows how the model size grows as the sampling procedure changes on the Internet Routers graph. Plots for other graphs show a similar growth rate and shape but are omitted due to space constraints.
To test the statistical correlation we calculated Pearson's correlation coefficient between the model size and sampling parameters. We find that the k is slightly correlated with the model size on Routers (r = 0.31, p = 0.07), Enron (r = 0.27, p = 0.09), arXiv (r = 0.21, p = 0.11), and DBLP (r = 0.29, p = 0.09). Furthermore, the choice of s affects the size of the clique tree from which the grammars are inferred. So its not surprising that s is highly correlated with the model size on Routers (r = 0.64), Enron (r = 0.71), arXiv (r = 0.68), and DBLP (r = 0.54) all with p 0.001. Because we merge identical rules when possible, we suspect that the overall growth of the HRG model follows Heaps law [42], i.e., that the model size of a graph can be predicted from its rules; although we save a more thorough examination of the grammar rules as a matter for future work.

Model size and Performance
One of the disadvantages of the HRG model, as indicated in Fig. 17, is that the model size can grow to be very large. But this again begs the question: do larger and more complex HRG models result in improved performance?
To answer this question, we computed the GCD distance between the original graph and graphs generated by varying k and s. Figure 18 illustrates the relationship between model size and the GCD. We use the Router and DBLP graphs to shows the largest and smaller of our datasets; other graphs show similar results, but we omit their plots due to space. Surprisingly, we find that the performance of models with only 100 rules is similar to the performance of the largest models. In the Router results, two very small models with poor performance had only 18 and 20 rules each. Best fit lines are drawn to illustrate the axes relationship where negative slope indicates that Model Size GCD DBLP Figure 18: GCD as a function of model size. We find a slightly negative relationship between model size and performance, but with quickly diminishing returns. We show best-fit lines and their equations; the shorter fit line in the Routers plot ignores the square outlier points.
larger models perform better. Outliers can dramatically affect the outcome of best-fit lines, so the faint line in the Routers graph shows the best fit line if we remove the two square outlier points. Without removing outliers, we find only a slightly negative slope on the best fit line indicating only a slight performance improvement between HRG models with 100 rules and HRG models with 1,000 rules. Pearson's correlation coefficient comparing GCD and model size similarly show slightly negative correlations on Routers (r = −0.12, p = 0.49), Enron (r = −0.09, p = 0.21), ArXiv (r = 0.04, p = 0.54), and DBLP (r = −0.08, p = 0.62)

Runtime Analysis
The overall execution time of the HRG model is best viewed in two parts: (1) rule extraction, and (2) graph generation. Unfortunately, finding a clique tree with minimal width i.e., the treewidth tw, is NP-Complete. Let n and m be the number of vertices and edges respectively in H. Tarjan and Yannikakis' Maximum Cardinality Search (MCS) algorithm finds usable clique trees [27] in linear time O(n+m), but is not guaranteed to be minimal.
The running time of the HRG rule extraction process is determined exclusively by the size of the clique tree as well as the number of vertices in each clique tree node. From Defn. 2.1 we have that the number of nodes in the clique tree is m. When minimal, the number of vertices in the largest clique tree node max(|η i |) (minus 1) is defined as the treewidth tw. However, clique trees generated by MCS have max(|η i |) bounded by the maximum degree of H and is denoted as ∆ [43]. Therefore, given an elimination ordering from MCS, the computational complexity of the extraction process is in O(m · ∆). In our experiments, we perform k samples of size-s subgraphs. So, when sampling with k and s, we amend the runtime complexity to be O(k · m · ∆) where m is bounded by the number of hyperedges in the size-s subgraph sample and ∆ ≤ s.
Graph generation requires a straightforward application of rules that is linear in the number of edges in the output graph.
We performed all experiments on a modern consumer-grade laptop in an unoptimized, unthreaded python implementation. We recorded the extraction time while generating graphs for the size-to-GCD comparison in the previous section. Although the runtime analysis gives theoretical upper bounds to the rule extraction process, Fig. 19 shows that the extraction runtime is highly correlated to the size of the model in Routers (r = 0.68), arXiv (r = 0.91), Enron (r = 0.88), and DBLP (r = 0.94) all with p 0.001. Simply put, more rules require more time, but there are diminishing returns. So it may not be necessary to learn complex models when smaller HRG

Graph Guarantees
In earlier work we showed that an application of HRG rules corresponding to a traversal of the clique tree will generate an isomorphic copy of the original graph [24].
Unlike the Kronecker and Chung-Lu graph generators, which are guaranteed to generate graph with power-law degree distributions, there are no such guarantees that can be made about the shape of graphs generated by HRGs. The reason is straightforward: the HRG generator is capable of applying rules in any order, therefore, a wide variety of graphs are possible, although improbable, given an HRG grammar.
But the lack of a formal guarantees give the HRG model flexibility to model a large variety of graphs. For example, given a line-graph, the HRG model will generate a new graph that looks, moreor-less, like a line-graph. If given a random graph, characterized by a binomial degree distribution, then HRG is likely to generate a new graph with a binomial degree distribution.

Conclusions
This paper describes a new generative network framework that learns a hyperedge replacement grammar (HRG) given a simple, general graph and grows new graphs. The inference (or model learning) step uses clique trees (also known as junction trees, tree decomposition, intersection trees) to extract an HRG, which characterizes a set of production rules. We show that depending on how HRG grammar rules are applied, during the graph generation step, the resulting graph is isomorphic to the original graph if the clique tree is traversed during reconstruction. More significantly, we show that a stochastic application of the HRG grammar rules creates new graphs that have very similar properties to the original graph. The results of graphlet correlation distance experiments, extrapolation, and the infinity mirror are particularly exciting because our results show a stark improvement in performance over several existing graph generators.
Perhaps the most significant finding that comes from this work is the ability to interrogate the generation of substructures and subgraphs within the grammar rules that combine to create a holistic graph. Forward applications of the technology described in this work may allow us to identify novel patterns analogous to the previously discovered triadic closure and bridge patterns found in real-world social networks. Thus, an investigation into the nature of the extracted rules and their meaning (if any) is a top priority.
In the future, we plan to investigate differences between the grammars extracted from different types of graphs; we are also interested in exploring the implications of finding two graphs which have a large overlap in their extracted grammars. Among the many areas for future work that this study opens, we are particularly interested in learning a grammar from the actual growth of some dynamic or evolving graph. Within the computational theory community, there has been a renewed interest in quickly finding clique trees of large real-world graphs that are closer to optimal. Because of the close relationship of HRG and clique trees are shown in this paper, any advancement in clique tree algorithms could directly improve the speed and accuracy of graph generation.
We encourage the community to explore further work bringing HRGs to attributed graphs, heterogeneous graphs and developing practical applications of the extracted rules. Given the current limitation related to the growth in the number of extracted rules as well as the encouraging results from small models, we are also looking for sparsification techniques that might limit the model's size while still maintaining performance.


extfieldsofstudy:
Engineering
Computer Science

text:
Ergodic Mutual Information for Generalized Fadings

Novel expressions for the ergodic mutual information (EMI) under BPSK modulation of single-input single-output (SISO) systems operating in generalized fading channels, namely Rayleigh, Nakagami-$m$, Rician, $\eta$-$\mu$ and $\kappa$-$\mu$, are derived. Different from the conventional results of the EUI, our developed expressions contain only the simplest numerical calculations, but no any Meijer's G-functions, which must be implemented in the specific computing software.

I. INTRODUCTION
Ergodic mutual information (EMI) is an important performance measurement metric in wireless multi-path channels, indicating the maximal transmission rate. Many researches on the EMI in fading scenarios have been presented in the past decades, including Rayleigh [1], Nakagami-m [2], Rician [3] fading channels, and generalized fading channels, namely η-µ and κ-µ [4]. However, all of these works assumed the input signals followed Gaussian distribution. In fact, a practical implementation is the case where the channel inputs are drawn from discrete constellations, the importance of which we cannot emphasize too much. Although the works in [5] have derived the recursive expression for the EMI under BPSK in Nakagami-m fading channels, the computation complexity is prohibitively high for large m.
In this paper, we derive novel expressions for the ergodic mutual information of single-input single-output systems under BPSK operating both in specific fading channels, including Rayleigh, Nakagami-m and Rician, and in generilized fading channels, including η-µ and κ-µ. It seems difficult to derive the closed-form exact formulas of EMI, thus we develop some simple closed-form approximate formulas, with high precision, to estimate the maximal transmission rate. Notably, our proposed expressions encompass no complicated structures, such as the commonly-used Meijer's G-functions in the conventional works. To the best of our knowledge, this is the first time to propose a comprehensive analysis for the ergodic mutual information with finite-alphabet inputs under general multi-path fading types.
The remaining parts of this manuscript is structured as follows: Section II presents the derived ergodic mutual information for generalized fadings. In Section III, simulation results are provided. Finally, Section IV concludes the paper. Denote f (·) as the probability density function (PDF) of the instantaneous Signal to Noise Ratio (SNR) per symbol. Then, the ergodic mutual information is defined as where I (·) represents the instantaneous input-output mutual information as a function of the SNR γ.

A. AWGN
Assume that the transmitted data stream are independent and identically distributed (i.i.d.) zero-mean binary symbols with equal probabilities, then the input-output mutual information in terms of the SNR γ under BPSK modulation over additive white Gaussian noise (AWGN) channels can be formulated as [6] An approximate formula of I (γ), with compact form and high precision, is expressed as [7] where ϑ = 0.6507. And the precision of Equ.

B. Rayleigh Fading Scenario
The PDF of received SNR in Rayleigh fading channels can be written as whereγ denotes the average SNR.
Lemma 1. The ergodic mutual information in Rayleigh fading channels is approximated aŝ Proof. On the basis of Equ. (3) and Equ. (4), the ergodic mutual information is derived as follows: The PDF of received SNR under Nakagami-m fading is given by Lemma 2. The ergodic mutual information under Nakagamim fading is approximated aŝ Proof. On the basis of Equ. (3) and Equ. (7),

D. Rician Fading Scenario
The PDF of received SNR under Rician fading is given by where n!Γ(n+1) is the 0-th order modified Bessel function of the first kind.
Lemma 3. The ergodic mutual information under Rician fading is approximated aŝ Proof. On the basis of Equ. (3) and Equ. (11), in which the step "(a)" is based on [8,Equ. (3.326.2)] and the step "(b)" is based on the Taylor series expansion of exp(x) = +∞ n=0 1 n! x n .

E. η-µ Fading Scenario
The PDF of received SNR under η-µ fading is given by [9] f ( 1 4 z 2 ) n n!Γ(ν+n+1) is the modified Bessel function of the first kind. It is well known that the η-µ fading holds two formats depending on the correlation in the main cluster. Moreover, h and H are functions of η and varies from one format to another. More specifically, in Format Lemma 4. The ergodic mutual information under η-µ fading is approximated aŝ Proof.
where the step "(a)" is due to [8, Equ. (3.326.2)], the step "(b)" is due to the Legendre duplication formula and the step "(c)" is due to the following Taylor series [10] 1 Notably, for any format of η-µ fading, it is easy to prove that h H + ϑγ 2µH > 1 with the expressions listed on the last page, thus Equ. (18) can be directly utilized.

III. SIMULATION
In this part, numerical and simulation results are provided to demonstrate the feasibility and validity of the former derivations. Notably, Rayleigh, Rician, η-µ and κ-µ fading can all be generated from Gaussian randoms, and the Nakagamim fading can be directly obtained by the Matlab function random(). Fig. 1 compares the approximated and simulated ergodic mutual information in terms ofγ for AWGN, Rayleigh and Nakagammi-m channels. Firstly, let us focus on the scenario of AWGN, whose approximated values are calculated by Equ. (3). As it shows, the simulated results meet accurately with the derivations, which suggests that Equ. (3) possesses high approximation precision and it is accurate enough to apply Equ. (3) into the estimation of mutual information. Most importantly, it can be observed that the approximation matches the empirical distribution for both Rayleigh and Nakagamim fading. Besides, it can be seen from this figure that the Nakagami-m fading channel tends to be AWGN as m grows. Then, Fig. 2 shows the ergodic mutual information as a function ofγ under Rician fading for selected value of K. It can be seen that the derivations meet tightly the results given via numerical simulations for all K and SNR. Moreover, with the increment of K, the positive effect from multi-path fading degrades, which contributes to the convergence trend toward AWGN in the graph above. Later, Fig. 3 and Fig. 4 move on to illustrate more generalized fading types, i.e. η-µ and κ-µ fadings. In Fig. 3, both Format 1 and Format 2 are presented to validate Equ. (15). As can be seen from both Fig. 3 and Fig. 4, the analytical results match well with the simulations.


Enhanced approach using trust based decision making for secured wireless streaming video sensor networks

The advances in the expanse of image sensors have made it conceivable to make high-resolution picture sensors easily accessible. The amelioration of wireless interactive media sensor networks are found to be greatly increased due to the day to day usage of cameras, microphones and smart devices. A secured multi-hop routing mechanism is addressed in surveillance areas which could be incorporated to the multimedia sensors that are capable of peruse the detected data comprises of recorded images and videos. Also, malevolent sensor hubs could be interjected into the vigilance area in an untrusted environment. In this contemplated venture, a novel lightweight trust decision-making framework is accomplished for QoS clustering to give secure routing in both intercluster and intracluster communication. A quantifiable aberrant trust value is the variable determined by the Cluster Head (CH) for its Cluster Member (CM) inside the cluster. The LEACH (Low Energy Adaptive Clustering Hierarchy) protocol is adopted for group formation and also for the exchange of the trust values among the master nodes, member nodes and Base station. In this way, the correspondence overhead, likelihood of dynamic assaults for example sinkhole and black hole assaults mount by eavesdroppers can be reduced by maintenance of trust values by cluster heads rather than cluster members. Besides, in wireless streaming video sensor networks this approach authorizes us to predict and counteract malicious untrusted and flawed nodes. Simulation results using NS-2 is examined and the suggested trust decision-making model escalates the dependability, elasticity and low memory aloft in comparison with the current trust models adopted for wireless video sensor network security.

Introduction
In the digital world, wireless multimedia sensor networks (WMSNs) are mainly facilitated by the modest, cheaper and novel technologies in radio communication, media transfer and digital standards. In smart agriculture and industrial applications sensor motes are meant for measuring temperature, humidity and other physical properties, Likewise, for capturing and processing video and audio sensory information WMSN interconnects self-governing devices from various extremities [1] to the surveillance station. WSNs are flattering cost effective, power consuming, versatile, and feasible [2] expected because of the elevation in usage of microelectro-mechanical systems (MEMS). Most of the researchers in video sensor networks focusing on minimizing power consumption and maximizing the transmission power [3] but the real value is data reliability. Typically the primary origin of vitality in a sensor mote is a battery; so the life time for any hub relies upon the life of the battery itself. Therefore numerous Media Access Control (MAC) conventions have been proposed to expedite data transfer by enabling an disabling occasionally instead of keeping the channel in ON status for the entire duration e.g. SMAC [4]. Information transmission in ecological, security, and wellbeing observing requires Quality of Service (QoS) combining with Quality of Equipment (QoE) apprehensive system in addition to a specific end goal to guarantee productive use of the assets and viable access. Envisioning precise real time image data can be carried out by deploying larger scale, video enabled wireless surveillance networks in the aforethought regions. In this kind of context, a few complex mission programs frequently require cryptographic mechanisms with the intention to gain protection in addition with QoS and QoE. For example, Wireless Video Sensor Networks (WVSNs) adopted in maximum of the defense applications require an excessive stage of security. Hence, it is crucial to build with ease conversation mechanisms between nodes of the community [5]. Authentication, Confidentiality and Integrity can be accomplished by Cryptographic primitives. Conversely, to combat attacks such as tampering of messages, packet dropping and Denial of Service (DOS) attacks, a secured mechanism that provides a completely trusted system is greatly addressed [6].
Customary trust administration blueprints that have been produced for wired and radio transmission systems could not be applied for interactive media sensor systems on account of higher utilization of assets, for example, memory and power assets [7]. In maintaining the QoS and QoE the power consumption is highly focused in clustering by adopting various clustering protocols. Trust Based LEACH is proposed in this paper aims at to assign power consumption at every node in the video sensor networks uniformly. Data gathering and restricted harmonization between nodes is supported by LEACH so as to minimize the resource consumption among the nodes [8]. The trust values are manipulated between the nodes using simple mathematical calculations which requires minimum computation time and less memory overhead [9]. However the trust decision making system requires the nodes to calculate the trust values during the network creation itself so that the possibility of the intrusion of untrusted nodes are considerably reduced. If the nodes performs the necessary actions of the specific networking rules the trust values are increased. Presumption of a trusted domain which may not be reasonable for each applications [10] as suggested by conventional research work in video sensor systems.
The suggested work depends on the trust values to ensure the security of the video sensor networks. The absolute aspiration of the venture is to provide the secure correspondence over a radio enabled video sensor networks by outlining a lightweight and reliable trust framework for WSNs against various attacks injected Eavesdroppers from various locations. Furthermore the proposed framework builds up a trust-based structure for clustered WVSNs, as well as the component that decreases the probability of malevolent motes being chosen (or chose) as synergetic and authorized nodes. The light weight trust management system is implemented in NS-2 simulation tool for clustering and secure routing in the network with eavesdropper nodes. Performance evaluation results shows that the proposed system shows the elevation in Packet Successful Delivery Ratio and contraction in Loss of Aggregated data, energy consumption, resilience, end to end delay when compared with existing Group-Based Trust Management Scheme for wireless sensor networks (GTMS) [11].

Literature retrospect
In order to enhance the secure and dependable trust system for the WVSNs, the review enforces to surf the related works and selected papers are discussed in this section to gain the related information for the implementation of trusted sensor network. Several suggested combat methods relies on the random key pre-distribution techniques [12][13][14]. To resolve this issue In [15], the researchers formulated the one way hash function to hash the keys for each periodic rounds According to this approach using the one-way hash function all the keys are hashed. Once the participating node in the WVSN accepts the key it will be hashed. Hence for each rounds the newly hashed keys will be chosen by the nodes for ensuring the security.
But the aforesaid mechanisms consumes energy and memory so that to preserve the predefined activities of wireless video sensor networks. In military surveillance areas the video and image files consumes more amount of memory and battery life which will affect the QoS and QoE in the intended networks. In addition with the QoS steering algorithms [16,17], QoS MAC procedures [18], and cross-layer QoS solutions [19] numerous mechanisms are proposed to address the QoS maintenance in contrasting layers of the network stack.
By examining above issues Rui Dai et.al [20,33] designed a load balancing mechanism using correlation aware differential coding scheme to minimize the network congestion often occurred in the media network. This work fully focuses on the even distribution of energy consumption throughout the network. As the visual information can examine the sight only inward the field, the FoV (Field of View) depends on the four factors the location (P), the sensing radius (R), the sensing direction (V), and the offset angle (α).focal length is depends on the projection (2D or 3D). By calculating the focal length of the distributed camera networks the interrelationship between two cameras are calculated by rend these flows into various paths inured to reduce the network traffic. The proposed QoS routing algorithm attains efficient conveyance of ocular data. However the calculation of the focal length remains time consuming in the large scale networks with high priority traffic where the visual data needs to be reached soon.
Focusing on low latency to real-time traffic, An Adaptive MAC Protocol with QoS support (AMPQ) for heterogeneous wireless sensor networks is suggested by Marion Souil [21]. In his work high channel usability is achieved by hybrid nature of the video sensor networks by enabling and disabling the assertion in the MAC layer. In radio based video sensor networks the couple of traffics are mostly involved such as backdrop traffic and multimedia abundance. These are often occurred by the external factors such as climate and gleaming. According to his study the main intention is to prioritized ocular and streaming data with high priority and data with less preference. According to the probability values the latency and throughput is distributed. Thus this protocol facilitates the QoS standards and furnish the adaptability and robustness of the multimedia networks. Besides keeping the flexibility of the network, several other factors are not meet in the system such as transfer rate, flawless allotment of resources and bandwidth restrictions.
To overcome the issues in AMPQ, Arar et al. [22] proposed a method of targeting information sharing amidst all layers in the cluster based WVSN so as to make the network more adaptive. Cross layer framework is investigated to optimize the resources in addition to the ocular & streaming distortion and packet mislaying during the allotment of resources among multiple interactive media sensors. A proximal minimization algorithm is proposed in the study f1or achieving the optimal distribution of energy, bandwidth and correspondence rate for achieving QoS. This framework is extended for motes combining multiple sources for battery power by harvesting energy to a maximum extent by targeting the balance between sustainable and grid sources. This method greatly helps in distributing the energy in the clustered sensor networks by adopting accurate cluster head election schemes. The (AMO) Animal Migration Optimization algorithm is proposed by X. Li et.al [23] as an advancement of cross layer clustered networks. This framework mainly targets on the clustering formation and successor mote recognition.
In cross-layer designs, the protection based surveillance networks get facilitated by appropriate security mechanisms by providing high encoding power as the proposed system provides optimal energy and processing capability. Nonetheless the interruption of the malevolent nodes is highly vulnerable and makes the network to be fatal. In addition with the optimal resource allocation and maintenance of QoS requirements, protecting the sensitive data from the trusted sources is more important. To address the security issues many QoS enabled security mechanisms are proposed by researchers. In reputation-based framework [24], for sensor networks a Bayesian formulation using beta reputation system is preferred to evaluate their trustworthiness in which each node preserve the status for other nodes. Since the network employs cryptographic primitives but it alone cannot prevent malicious attachment of data from internal rivals or predatory nodes. By considering the above flaws, In QoS clustered networks, distributed trust assessment strategy is designed with the progressive structure for proficient data exchange [25,38] by comparing the trust values. This strategy provides consistent updating of objective trust and subjective trust in addition with maintenance of application layer security. More difficult issue is that the sensor motes might be tampered and perform pernicious assaults, for example, data dropping or information alterations to disturb ordinary activities of a WSN wherein SNs probably perform unattended tasks. Researchers have actualized a trust enabled steering scheme for dynamic WVSNs [26] to secure the WVSNs against attackers misleading the multi-hop data transfer. According to this system the two parameters such as t-instrument and r-certificate is maintained for individual node trust and dependability. In addition to that, for ensuring the trust and trustworthiness of its hosting node all participating nodes in the surveillance networks should be locally hold a mobile agent. By this way, mobile agents provide both inter and intra trust values. In some circumstances the mobile agent can be an eavesdropper node and there might be a chance of injecting the devastating attacks. To combat the above issues, a group based trust management scheme is proposed in which the group trust value is calculated at regular time intervals for ensuring trustworthiness during authentication, authorization, or key management [11]. All the participating nodes in the networks can ensure whether it enters into the trusted zone or cluster. By this way a resilient video sensor networks is built with group trust calculation.

Trust based decision making for secured wireless streaming video sensor networks
The proposed secure trust administration is to advance the defended data transfer in the remote sensor systems against mischievous hubs. In surveillance areas the images and videos captured by the sensors equipped with IP cameras can be altered by the adversaries [27]. They usually inject the passive attacks and active attacks in the network to make the whole process compromised. Some of the passive attacks such as tampering, radio jamming and message modification can be detected and prevented by various security mechanisms [28]. Image sensor nodes can be spoofed in by the enemy and can falsify the information during the communication occurred via data link. Sensor nodes yet to be sustainable to these assaults. In this way, one of the real difficulties in such systems is the manner by which to offer secure association amongst sensors and the base station and how to transfer the information while keeping up the security prerequisites without altering the restricted assets. But the recent studies do not focus on the preventive mechanism for active attacks [29]. The combat mechanisms focuses only on the encoding and novel key generation techniques. The suggested Trust Management System (TMS) will reduce the probability of compromised or malevolent nodes being function as participating nodes. The outline of the working model of the proposed framework is depicted in Fig. 1.
In this work, eavesdroppers inject the active attacks such as black hole and sink hole attacks in different clusters to make the network compromised. They usually perform their behavior [34] without any agreement or mutual cooperation among them. Here E1 will inject the blackhole attack and E2 will inject sinkhole attack during the cluster communication. The proposed trust-based mechanism will combat these attacks and moreover avoid these malicious nodes in the participation of data transfer permanently.

Our contributions
Based on the insights, an efficient investigation of a trustworthy administration framework for the clustered WVSNs focusing both trustworthiness and asset efficiency for maintaining the QoS is designed. In addition with the resource allocation, the surveillance networks need the security level to the atmost degree for the efficient and reliable communication. Many video sensor applications are equipped with sensors such as agricultural assisting robot [30], industrial automation [31,36], and smart vehicles [32,35] where security is not prioritized as it is dealt with the sensor data [37,39]. But in the sensitive applications such as military surveillance areas, cyber agencies and banking sectors the ocular and streaming data is the primary source which need high protection. To address the above issues the trust based formwork is suggested for providing the security from the network creation itself. The following are the contributions of the proposed ideology:

Cluster creation
The scattered motes in the video sensor networks are organized into simple clusters using LEACH protocol. Here the sensor nodes equipped with cameras are partitioned into small clusters. Initially nodes with high battery power is chosen as Cluster Head (CH). The nodes other than cluster heads which can quickly respond to the request messages forward from master nodes can group into clusters. The rest of the other nodes can join into the adjacent clusters. The resource allocation is performed through change in the election of cluster heads with probability k. The proposed trust framework helps in the determination of trusted steering motes through which an individual CM can send the trust values to the CH. The accumulated information is then transmitted from the corresponding CHs to the focal BS through different CHs.

Launching active attacks
In the proposed system the trust reliability is tested with the eavesdropper attackers E1 and E2 which endeavors to expand the effect of making the trusted nodes into malicious in different clusters by trading off the motes in each objective area. Specifically, the assailant could acquire more access by trading off quite small number of image sensors in different groups, as opposed to making them malevolent that are conspiring with each other. These malicious sensors could see or tamper the image and video data on sensor communications, act like genuine motes, disrupt the operation of the sensors by forcing themselves as motes in-the-center, and upsetting administration in many ways. Both malicious nodes thoroughly monitoring the transmission of packets and the trust decision making interactions throughout the network, launches active attacks such as in the clustered sensor network.

Trust evaluation
The framework for trust administration remote systems is a procedure that can be utilized to keep the basic verdict building of the systems. It helps the video sensors from parent network (trustors) to manage susceptibility about the future activities of another participating nodes (trusters).
Initially all nodes in the participating network are allowed to exchange the HELLO packets during the network creation itself. During the data transmission mode the cluster head calculate the number of successful and unsuccessful interactions. The motes which reply within the predetermined time limit can be claim for successful transmissions. Those

Establishing trusted path
All the image sensors working on the basis of trust values maintained inside the cluster as well as inter-cluster. The malevolent nodes if tried to participating in the network it has to share its trust values which may be not possible as it possess LOW trust value when it made ambiguous and delayed transmissions. The malicious node turns it into an untrusted node due to the dropping of packets both in inter and intra cluster levels. The suggested trust decision making framework should avoid the data transmission in the LOW trust path (such as the path where the black hole node and sink hole resides). Consequently the trust based system won't enable the noxious nodes to take part in the correspondence over some undefined time frame. The malignant hubs are not able to betray different sensor motes as the trust choice depends on the two assessment delivered by CHs and Base Station. The trusted way is designed for the transfer of information in the WVSNs.

Network model
The topology is created for WVSNs with specific number of nodes in the simulation field. All sensor nodes within the cluster and intercluster simultaneously send HELLO packets to the adjacent nodes at a specific time of 1 s and a speed of 1Mbps.The cluster members calculate the number of successful and unsuccessful transmissions during the node creation stage itself. NS-2 Version 2.35 simulator is used for showing the experimental results. We have tested with around 50 nodes scattered in the field size of 1000 m * 750 m.The delay in transmission is calculated parallel and saved in the patch file. Two hacker nodes are designed with normal transmitting rate at the time of creation. For configuring the communication UDP and NULL agents are widely preferred. The threshold limit is set and the nodes are allowed for exchanging the packets for the predefined time taken as 60 s. All the video sensor networks are fully depends on the sink node for the data gathering and aggregation. At the initial level itself the sink node is set in the simulation field itself. (Fig. 2).

Batch formation using LEACH protocol
For ensuring the QoS parameters in the WVSNs the resources such as battery life, storage capability and bandwidth are equally distributed among all nodes both inter cluster and intra cluster by adopting LEACH protocol. It normally uses TDMA fashion for organising the clusters. The nodes with strong transmission power is elected as Master nodes. The neighbouring node which can reply to the REQUEST message sent by master nodes within the threshold time forming one cluster. The remaining nodes can join with the adjacent clusters within its communication range. Normally LEACH protocol comprises of formation phase and transmission phase. The master nodes are chosen in the setup phase. In this stage the node with strongest received signal strength is elected as CH. All the member nodes can accept the Bjoin Packet^with their corresponding IDs to form one cluster.
In the data transmission phase, the master node is determined and the node IDs and count of failed and reached transmissions is sent to the adjacent CHs and also to the BS. When data is transmitted between nodes the election of CHs is simultaneously done with some probability k. Considering that the masters and members are sorted out into clustered QoS enabled WVSN with the assistance of a group formation scheme. Let us consider the master nodes and the sink nodes are trustworthy and won't be attacked and altered. Each master gives two way correspondences. One with the member node and another with base station. BS give multihop communication mode from members and also among the master nodes. The sink nodes also get the trust values as the CHs and CMs.
In the proposed scenario, One CM sensor node send message to base station node through CH and eavesdropper nodes will listen to the packet data as intermediate nodes as assumed.

Fig. 2 Network Creation
Upon monitoring the transmissions, the attacker could easily discover the recorded images and streaming data. Susceptibility of monitoring and eavesdropping are also encountered in the Network traffic. Using NS-2 tool clusters are organized in the network area (Fig. 3) and given various colors (red,black,blue,purple,brown,cyan) for differentiation. The attackers in node 2 and node 11 are not colluding with each other and they may be in different clusters injecting active attacks.

Compromised network with active attacks by eavesdropping nodes
After cluster formation the nodes are exchanging their cluster IDs to the corresponding master nodes. In this instance the adversary node makes itself as the sink hole attacker which has the capability of dropping or halting the communication over the sink node. The central part of the network i.e. sinknode sometimes experience the state in which all the packets will be dropped by the node targeting the sink node. Typically the member nodes expends the appropriate data from all sources and draw in towards the sink hub. Once receiving the RREQ the noxious hub dependably sends RREP without performing standard AODV (Adhoc On demand Distance Vector routing) tasks by advertising itself with the highest Destination Sequence number. Since AODV considers RREP with the goal arrangement number to be new, the RREP sent by the malignant hub is also dealt with fresh route. In this way, malignant hubs prevail with success of infusing Sink Hole assault in the system as in Fig. 4.
In the same way adversary 2 launches blackhole attack by attracting the node by advertising itself with the fresh route to have the high sequence number. Once the route is established all the media data will get dropped or may be altered. In our simulation, as shown in Fig. 5 Node 11 is the adversary 2 poses the packet dropping attack.
By running Perl Script cat out.tr | analyze. Perl in terminal, it is evident due to the presence of active attackers the functionality of the system is degraded. This results can be analyzed

Preventing active attacks by trust based mechanism in WVSNs
The general trust computational model used to calculate trust values in WSN is shown in Fig. 6. The trust decision making is solely depends on the number of flawless and failure transmissions in the network. The trust should be maintained both intercluster and intracluster for efficient and secured data transfer. The dispositional risk is the external factors which induce the change in trust values. These can be occur due to external factors network traffic, power constraints and memory outage.

Algorithm for Trust Decision Making
Initial condition: Node advertise with other node in the clustered sensor network.

Member-member trust
The calculation of the trust at member level is defined by the following eq. 1 Δt window of time S x, y positive interactions U x, y failure interactions

Master-member trust
The master node will normally exchanges the REQ packets inside the cluster. All the member shares their trust equivalent within the cluster as well as to the master nodes. In matrix 2 all the trust values are maintained by the master node as shown below Compute the Ma-Me by the following proven mathematical formula 3 Where, R ch,y is the Ma-Me on y by the CH as in eq. 4 r implies count of positive transmissions, and v denotes amount of negative transmissions w.r.t master node .

Ma-Ma trust calculation
The trust evaluation approach at CMs is defined by the following eq. 5 where. T i,j is the Ma-Ma trust value of the channel heads. Compute the Base station to the master trust value of a Cluster Head j by the Base Station by the following proven mathematical formula 7 Where, F bs,j is the Bs-Ma trust. If the malicious node having higher trust value need to participate in the data transmission then the data packets are transmitted through the black hole node and sink hole, the malicious nodes drops the data packets. Over a period of time the trust values of the adversary nodes becomes less and at that instance no communication allowed via that path as shown in simulation result Fig. 7. After the trust computation all the nodes with the high trust values are allowed to participate in the network. Node 2 and Node 11 are no longer participating in the data transmission as it holds the negative trust values.
When we analyzing the network performance by running the perl script in the simulator it shows a good elevation due to the secure communication.

Performance evaluation
To analyze the overall performance the metrics such as Dependability, Packet Loss, Energy consumption, Resilience and End to End Delay are taken for comparing the efficiency of the proposed system with the existing trust based systems. Summarization of the comparison results between our proposed Trust Management System (TMS) and GTMS framework [11] is shown in Table 1 as both the systems has similar networking functions. These below values are  Table 1.The comparative results reveals that the proposed system shows the increase in performance metrics when analyze with the present security mechanisms.
In Fig. 8a TMS provides comparatively high PDR thereby improves the network performance. In Fig. 8b it is noted that the obtained Loss Percentage of proposed TMS is comparatively less than the existing GTMS.
From the analysis of Fig. 8c, the energy consumption in TMS is much lower than that of GTMS with LEACH Protocol at the same round of simulation. From Fig. 8d, it is obvious that with increase in compromised nodes, the Fraction of Compromised Communication (FCC) in TMS is much lower than that of GTMS. The graph Fig. 8e is plotted by taking number of packets transmitted in X axis with respect to time in Y axis. The End to End delay produced by TMS is comparatively less when compared to GTMS. Furthermore X graph is plotted using the various metrics values obtained during the transmission of the data. The X graph is generated for energy consumption (Fig. 9), resilience ( Fig. 10) and End to End delay (Fig. 11) for showing the analysis of the proposed system with the existing LDTS [9] technique.

Conclusion
In this paper, trust management system with enhanced approach is proposed for the effective communication between the nodes. Due to the change in roles of the nodes resource efficiency is at most maintained for preserving QoS and QoE parameters. The resource allocation is performed accordingly when there is change in masters and members. In protected areas for maintaining the sensitive information in addition with QoS and QoE a secure data transfer is needed. Focusing on the secure data transfer, a novel trust based communication platform is suggested for transferring the multimedia content more efficiently by combating the active attacks. Though the attackers posing the attacks at any instance, by applying the trust calculations the adversary can be avoided in the participation of the network. This proposed system is also light weight as it requires only simple mathematical calculations and consumes less number resources. Moreover the proposed system is tested with the adversary intrusion to check its efficiency by analyzing whether it chooses the alternative paths. Simulation results shows that the proposed trust establishment strategy proves to be more efficient than the current mechanisms.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.