{'fraction_non_alphanumeric': 0.03455566567558639, 'fraction_numerical': 0.007036669970267592, 'mean_word_length': 4.5933111603843315, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exponential random graph models

Nowadays, exponential random graphs (ERGs) are among the most widely-studied network models. Different analytical and numerical techniques for ERG have been developed that resulted in the well-established theory with true predictive power. An excellent basic discussion of exponential random graphs addressed to social science students and researchers is given in [Anderson et al., 1999][Robins et al., 2007]. This essay is intentionally designed to be more theoretical in comparison with the well-known primers just mentioned. Given the interdisciplinary character of the new emerging science of complex networks, the essay aims to give a contribution upon which network scientists and practitioners, who represent different research areas, could build a common area of understanding.

of a particular graph G is proportional to e H(G) , where H(G) = i θ i x i (G). In the Hamiltonian, {x i } is the set of graph observables upon which the relevant constraints act, and {θ i } is a set of ensemble parameters which we can vary so as to match the properties of the model network to the real-world network under investigation.

•
Adjacency matrix: is a matrix with rows and columns labelled by graph vertices i and j, with elements A ij = 1 or 0 according to whether the vertices, i and j, are connected/adjacent or not. In the case of an undirected graph with no self-loops or multiple edges (the so-called simple graph), the adjacency matrix is symmetric (i.e. A ij = A ji ) and has 0s on the diagonal (i.e. A ii = 0).
Accordingly, for a simple directed graph the symmetry condition may not be fulfilled, i.e. it can be that A ij = A ji .
• Reciprocity: describes tendency of vertex pairs to form mutual directed connections between each other.
• Clustering: describes tendency of nodes to cluster together. Clustering is measured by the clustering coefficient which calculates the average probability that two neighbors of a vertex are themselves nearest neighbors.

Definition
A graph consists of a set of objects or individuals, called nodes (points, vertices), connected by links (edges). The idea of a graph is a powerful simplification for different phenomena -a way of specifying pairwise relations among a collection of items or agents. Graph models are introduced in order to mimic the patterns of connections in real networks, in an effort to understand the implications of those patterns, or just to describe, how network structures originate, and how they evolve over time.

Introduction
Many of the networks we observe in the real world exist in only one realization (instantiation) that we can study. There is only one Internet, only one World Trade Web, and only one network of social ties formed, for example, between filmmakers through their past collaboration in film projects. Only one realization of a given network does not mean, however, that this concrete realization is the only possible that the network may have. Common sense suggests that in other circumstances different link configurations in the considered networks could arise. In particular, the Internet evolves, therefore one can see its different structural realizations if one looks at different times. By definition, all the snapshots of the Internet are its plausible realizations. It is also reasonable to assume that growing in slightly different conditions (we might say, in a parallel world) the structure of such an alternative Internet would probably have been similar to the real Internet. That is, all plausible realizations of the Internet should have some basic features in common, even if they differ in smaller details. Of course, similar considerations also apply to other types of networks, including economic and financial networks, biological networks, and, obviously, social networks.
Considerations of this kind lead us naturally to the concept of statistical ensemble of networks, which is the collection of all possible realizations that the considered network may reasonably be expected to attain, G = {G}, plus probability distribution, P (G), over G. In the exponential random graph model each graph, G, appears with the probability, P (G) ∝ e H(G) , that is exponential in the so-called graph Hamiltonian, H(G), which determines various networks' properties within the ensemble.
In the following, we show what does it mean "to create" an ensemble of ERGs with a given set of properties, such as a given number of edges, or a given value of the clustering coefficient 1 . We explain the concept of the network Hamiltonian, which is the key point of ERG theory. Our theoretical derivations are accompanied by example calculations. In particular, the classical random graph model popularized by Erdös and Rènyi is reformulated in the language of ERGs.
Other important examples are also 1 The clustering coefficient is a measure of the extent to which nodes in a graph tend to cluster together [9]. discussed, such as the generalized random graphs, the reciprocity model, the so-called two-star model, and Strauss's model of transitive networks. A short training in Monte Carlo simulations, to which the ERG model lends itself admirably, is given. Finally, we also place an emphasis on deep connections of the model with basic principles of equilibrium statistical physics and information theory. In doing so, we argue that these models are not merely an ad hoc formulation studied mainly for their mathematical convenience, but a true and correct extension of statistical mechanics to the world of networks.
An excellent basic discussion of exponential random graphs addressed to social science students and researchers is given in [1; 26]. This essay is intentionally designed to be more theoretical in comparison with the well-known primers just mentioned. Given the interdisciplinary character of the new emerging science of complex networks [3], the essay aims to give a contribution upon which network scientists and practitioners, who represent different research areas, could build a common area of understanding.

Historical Background
The first truly general ensemble model of networks was introduced by Solomonoff and Rapoport in 1951 [28], who considered the collection of all undirected simple graphs with a fixed number of vertices, N, in which every pair of nodes was connected with an edge with probability p. In the late 1950s and early 1960s, the model was fairly extensively studied by Erdös and Rènyi, see e.g. [10; 11]. Ever since it is known as Bernoulli model or Erdös-Rènyi model. We mention this because this particular ensemble of graphs was indeed the first example of the ERG model, and we will meet it again when we will be discussing concrete examples of exponential random graphs.
The exponential random graph model, as we discuss it in this essay, was first proposed in the early 1980s by Holland and Leinhardt [18], who built on statistical foundations laid by Bessag [5]. Substantial further developments were made by Frank and Strauss [12; 29], and continued to be made by other authors throughout 1990s [1].
Nowadays, exponential random graph models are in common use within the social network analysis (SNA) community [1; 26] we restrict ourselves to simple graphs with a fixed number of nodes N. A simple graph has, at most, one link between any pair of vertices and it does not contain self-loops connecting vertices to themselves. There exists a one-to-one correspondence between simple graphs and symmetric matrices of size N with elements A ij equal to either 0 or 1 (see Fig. 1). If we know that the network has N nodes and there is no reason to think that N will change (or change significantly), and if we know that the direction of the edges does not matter, then the set of simple graphs is a sensible choice for G. Thus, we have measurements of one or more graph observables and we have also specified plausible realizations of the network. The aim is to choose probability distribution P (G) over the set of all possible network realizations, G = {G}. In the exponential random graph model one assumes that the probability distribution, P (G), has the form 2 where Z is called the partition function and can be calculated form the normalization condition 2 The question, of making the best choice of a probability distribution, P (G), given only a relatively small number of constraints on that distribution, is addressed in the section Connections with Information Theory and Statistical Physics.
which implies The network Hamiltonian in Eq. (1) is given by where {x i (G)} are the values of the observables {x i } for a graph G, while {θ i } = θ 1 , θ 2 , . . . θ r are ensemble parameters, which are said to be conjugated to observables in such a way that the value, x * i , as measured in the real network is equal to the corresponding average value within the ensemble, i.e.

Fluctuations
Once the probability distribution P (G) over G is given, see Eq.
(1), we can use it to calculate estimates of other quantities of interest within the ensemble. For example, the expectation value of a quantity y is given by This expression provides the best-guess at the value of the quantity y given the only An interesting special case arises when the quantity y is itself one of the primary network observables, e.g. y = x j . One may ask: Why we would want to do this, given that, since x * j is used as an input to our model, cf. Eq. (5), we already know its expectation value. The answer is that, to define the ensemble we need to fix the param- The value of x j within the considered ensemble is given by where is called the free energy, which is a function of r variables {θ i } (alike the partition function, Z).
Similarly to Eq. (7), one can show that the second derivative of the free energy, F , with respect to θ j gives the mean square fluctuations of x j , i.e.
In statistical physics, the last expression is known as the fluctuation-response relation.
The l.h.s. of Eq. (9) describes fluctuations in x j , whereas its r.h.s. characterizes susceptibility of the observable to its conjugated ensemble parameter θ j . The susceptibility is defined as the derivative of x j with respect to θ j , and describes what happens with x j , when one changes its conjugate parameter θ j , which determines/represents external conditions related to x j .

Connections with Information Theory and Statistical Physics
Let us define the problem 4 . Thus, let G be a graph in the set of possible network realizations G and let P (G) be the probability of that graph within the ensemble. We would like to choose P (G) so that the expectation value of each of our graph observables . . x r within the ensemble is equal to its observed value {x * i }. Due to maximum entropy principle of information theory [8], which amounts to the second law of thermodynamics in statistical physics [2], the best choice of probability distribution P (G) is the one that maximizes the Shannon/Gibbs entropy, subject to the constraints given by Eqs. (2) and (5).
At this stage, one may ask: What does it mean the best choice in this context?
In his book on networks (see [20], p. 568) Mark Newman explains that the maximum entropy choice is best in the sense that it makes the minimum assumptions about the distribution other than those imposed upon us by the constraints. There are choices of distribution we could make that would satisfy the constraints but would effectively make additional assumptions. For instance, some choices might make a particular graph or graphs highly probable while other graphs, only slightly different, are given far lower probabilities. These would be considered bad choices in the sense that they assume things about the ensemble for which we have no supporting evidence. The entropy as given by Eq. (10) is precisely a measure of the amount of assumption that goes into a particular choice of distribution P (G), or more precisely it is the amount of antias-sumption or ignorance, and by maximizing it we minimize unjustified assumptions as much as possible.
The maximization of the entropy, Eq. (10), subject to the constraints of Eqs. (2) and (5), can be done by the method of Lagrange multipliers. Introducing Lagrange multipliers α and {θ i } one finds that the maximum value of the entropy, S, is achieved for the distribution satisfying the following expression for all graphs G ∈ G. This gives which implies, cf. Eq. (1), where

Examples
In the following we discuss five examples illustrating the ERG model. The model of classical random graphs, which is also known as the Bernoulli model or Erdös-Rényi model, is the first example. It is the simples ensemble of ERGs, and it can be solved exactly, meaning that one can calculate its partition function and the corresponding derivatives.
Next, we discuss generalized random graphs, i.e. maximally random networks with a given node degree sequence, which appear to be among the most important network models in the contemporary science of complex networks. Over the past decade, they have been used extensively as a reliable test bed to study dynamical processes on networks. Then the reciprocity model is worked out, which is an important example of the historical significance in social network analysis and mining. One says that the idea of exponential random graphs was born along with the model. It is also worth to note that the reciprocity model, like the classical and generalized random graphs, is exactly solvable.
It would be a mistake, however, to think that all or most of exponential random graph models can be exactly solved. Most are not, and to make progress one must turn ily. Namely, the two-star model can produce two radically different classes of networks for the same values of the ensemble parameters 5 . In physics, the feature is known as spontaneous symmetry breaking, and it is understood to accompany phase transitions which give rise to interesting phenomena, such as ferromagnetism or superconductivity.
In the field of social networks, the comprehension of these phenomena is unfortunately rather limited. The symmetry breaking is thought to be, at the least, troubling, although, if presented in the right context, it could be an important/insightful concept used, for example, in the theory of social change.

Classical random graphs
Suppose, one knows only the expected number of edges, E , that the undirected network has. Thus, the Hamiltonian of the corresponding ERG model is given by 5 In the sense of the occurrence probability of a given graph, P (G), it means that the most probable network realizations can be completely different.
where θ is the ensemble parameter (so-called external field), whose value determines E .
In order to proceed, one has to calculate the partition function, Z, of the ensemble. When the network Hamiltonian is a simple function of elements A ij (G) of the adjacency matrix, as is the case of Eq. (14) above, where then the standard way to perform the sum over G in Eq. (3) is to sum over the elements A ij . In the case of simple graphs, the only allowed values for A ij are 0 and 1, with Hence, the resulting partition function underlying the considered From this expression one can calculate the free energy, cf. Eq. (8), and the average number of edges is the ERG model, cf. Eq. (7), The last expression can be rearranged to get the value of the only ensemble parameter, At this point, it is insightful to show that the considered ensemble of exponential random graphs is equivalent to the so-called binomial model, which is an alternative definition of the ensemble of classical random graphs, that was famously studied by Erdös and Rényi. In classical random graphs with N vertices, every pair of nodes is connected with a given probability p. Consequently, the total number of edges is a random variable with the expectation value Note, that the last expression agrees with Eq. (19) above, when Eq. (22) shows that there is a direct relationship between the ensemble parameter, θ, in the ERG model and the connection probability, p, in the well-known classical random graphs.
The equivalence between the two models becomes even more apparent when looking at the probability of obtaining a graph G (with N nodes and E edges) by the classical random graph construction procedure, which is and the probability of such a graph within the considered ERG model, cf Eq. (1), It is easy to see that, given Eq. (22), the two expressions coincide.

Generalized random graphs
Despite its general nature and simplicity, the classical random graph model 6 turns out to have severe shortcomings as a model of real-world networks. Probably the most important shortcoming is that the expected node degree distribution in classical random graphs, which is the Poisson distribution, significantly differs from the node degree distributions in the majority of real networks. To overcome this problem the so-called 6 which is described in the previous example and shown to be equivalent to the ERG model with an expected number of nodes generalized random graphs has been proposed, in which degrees of all vertices are drawn from a specified (e.g. power-law/scale-free) degree distribution [22].
Thus, suppose that, rather than measuring the total number of edges in a network, we measure degrees of all the nodes. Let us denote by k i the degree of a node i.
The complete set {k i } = k 1 , k 2 , . . . k N is called the node degree sequence of a network 7 .
The ERG model appropriate to such a set of observables has the following Hamiltonian [24] where {θ i } is the collection of N ensemble parameters (one parameter θ i for each node i). Noting that k i (G) = N j=1 A ij (G), Eq. (25) can be rewritten as Accordingly, the partition function for this ensemble is given by, cf. Eqs. (3) and (16), (1 + e (θ i +θ j ) ), (28) and the free energy, Eq. (8), becomes By differentiating the free energy, Eq. (29), with respect to θ j one gets the expression for the average degree of the node j, see Eq. (7), where 7 Note that, since i k i = 2E, we do not need to specify independently the number of edges is the connection probability between the nodes i and j, i.e. the average value of the element A ij of the adjacency matrix 8 .
In sparse networks, the probability of any individual edge is small, i.e. p ij ≪ 1.
In such networks Eq. (31) factorizes: Inserting the factorized probability into Eq. (30) one gets the following expression for the average connectivity of a node j where the handshaking lemma 9 has been used. Then, using Eq. (33), the connection probability can be written as The obtained formula for the connection probability between two nodes, i and j, is the one which is often encountered in the theoretical description of generalized random graphs.

Reciprocity model
A large number of real-world directed networks, including social networks, display the phenomenon of reciprocity [30; 17], i.e. the tendency of vertex pairs to form mutual directed connections between each other ("mutual dyads" in the parlance of social network analysis). In this section we discuss the reciprocity model proposed by Holland and Leinhardt [18]. 8 Let us note that Eq. (31) can be calculated using Eq. (6).
where E is the number of all directed edges, R stands for the number of vertex pairs with edges running between them in both directions, while β and γ are ensemble parameters that can be varied to obtain the desired number of all edges, E , and reciprocated edges, R . Using the elements of the adjacency matrix the Hamiltonian can be written as where the product A ij A ji = 0 only when both directed connections exist, i.e. A ij = 1 and A ji = 1.
and 10 A simple directed graph is a directed graph having no multiple edges or loops. Note that for varying values of the ensemble parameters, β and γ, the reciprocity parameter, r, changes from 0 (none of edges belongs to mutual dyad) to 1 (all existing edges are reciprocated).
One can also calculate the reciprocity parameter, r, which is the fraction of edges that are reciprocated:

Two-star model
In the two-star model one specifies the expected number of edges, E , and the expected numer of the so-called two-stars, V . Possible network realizations correspond to all undirected simple graphs with a given number of nodes, N. A two-star is a vertex connected by edges to two other vertices (see Fig. 3). Varying the number of two-stars allows one to control the extent to which edges in the network stick together, meaning that the edges share common vertices. If the only number of edges in a network is fixed, then sticking together is a random processes, i.e. edges may stick or they may not. On the other hand, if we assume a large number of two-stars, then the edges have to stick together to create the required value of V . In this way, the two-star model allows one to control the extent to which the edges gather together in clumps or are distributed more randomly.
i k j Fig. 3. A two-star meaning a vertex connected by edges to two other vertices.

The number of two-stars in a network is
and, therefore, the Hamiltonian of the model is given by where β and γ are two ensemble parameters, and E(G) was already given by Eq. (15).
is the same for all the pairs of nodes. Therefore, the third sum in Eq. (47) can be written as and, correspondingly, the Hamiltonian of the two-star model becomes equivalent to the Hamiltonian underlying classical random graphs, cf. Eq. (14), except that the ensemble parameter in the new Hamiltonian, i.e.
is a rather complicated function of the original parameters, β and γ, and the unknown connection probability, p.
where p, is the connection probability, Eq. (48), gives a self-consistent equation for the parameter p, which characterizes "density" of connections within the network, i.e.
In what follows, for convenience in solving for p, we define so that Eq. (56) becomes There is, however, a difficulty with Eq. These two solutions, however, correspond to very different network realizations. The first solution (the smaller value of p) characterizes sparse networks with a few edges, whereas the second one (the larger value of p) describes dense networks with many connections. If one were simulate the two-star model on a computer 13 , for the same parameter values one would in this regime sometimes observe a high-density network and sometimes low-density one, depending on initial conditions. In general, one would not be able to predict in advance which of these would occur. Worse yet, for C = 3 2 there are some values of p that are simply impossible to reach.
This interesting behavior is called spontaneous symmetry breaking. In physics, such a behavior is understood to accompany phase transitions. It is known to give rise to a number of important phenomena which rely on/emerge from collective behavior of the system's constituents. The well-known examples of such phenomena are spontaneous ordering or condensation/nucleation effects in the condensed matter physics. More frequently, however, it happens that researchers from disciplines other than physics strive to use these concepts to understand strange/surprising/unexplained observations. It seems that the borrowed from physics concepts of symmetry breaking and phase transitions may alow understanding properties of systems which are not of interest within the traditional domains of physics, but refer to widely circulated research on complex systems, which becomes more and more influential. In the SNA community, however, the prevailing view is that such a behavior, that a model can produce two radically different classes of networks for the same values of the model parameters is thought to be confusing/false. On the contrary, from the point of view of the physicists, the behavior is very intriguing/promising. It suggests, that there exist external conditions at which the (social) network becomes very fragile. In the real world, such a fragile/critical network may abruptly change its properties [16]. One says that the network is susceptible to external perturbations. Thus, why not to use the concepts to analyze revolutions, political conflicts, etc.
Finally, for the sake of completeness, one should note that the remaining three plots d), e) and f) in Fig. 4 correspond to the critical value of the parameter C = 1, above which the symmetry breaking appears, and below which it is absent.

Strauss's model of transitive networks
The famous Strauss model [29] was originally proposed as a model of a clustered network. In the model one specifies the expected number of edges, E , and the expected number of triangles 14 , T . Consequently, the network Hamiltonian is given by

Monte Carlo Simulations of ERGs
The mathematically tractable models are very rare in the exponential family of random graphs 15 [27; 19; 21]. In the method, one defines a move-set in the space of graphs and then repeatedly generates moves from this set, accepting them with probability where G ′ is the graph after performance of the move, and while rejecting them with probability 1 − p. Because of the exponential form of P (G), the acceptance probability which is given by Eq. (61) is particularly simple to calculate.
It can be written as where Let us also note, that with the help of ∆H, the condition for certain acceptance of a change, Eq. (60), becomes to implement and appear to converge quickly allowing one to study quite large graphs.
To be concrete, let us work out the Metropolis algorithm for classical random graphs, i.e. the ERG model with an expected number of edges, cf. Eq. (14). The ensemble can be obtained in the following way: 1.
At the beginning one creates any simple graph (i.e. its adjacency matrix) with a given number of nodes, N. The starting configuration may be, for instance, the edgeless graph.

2.
Next, in the following time steps, one randomly chooses a matrix element,

3.
The updating of elements A ij should be continued until the network observables stabilise around their mean values 16 . In the case of classical random graphs, the average number of edges, E , should place itself around the value, which is given by Eq. (15). Once numerical simulations stabilise, graphs which appear in the course of subsequent updates of the adjacency matrix appear to be correctly sampled network realizations of the studied ensemble.

Key Applications and Future Directions Bimodality and Symmetry Breaking in Social Networks
In working with exponential random graph models the aim is to create model networks with properties similar to those seen in real-world networks. From the statistical point of view, the ensemble approach seems to be a very logical one. The construction of the model using maximum entropy principle, which is a driving force behind many natural and manmade systems, is natural and ussually gives sensible results. However, the overwhelming opinion within the SNA community is that the two features of ERGs, i.e. spontaneous symmetry breaking, and the ranges of network properties that simply cannot be created using the models, while at the same time real-networks can and do display properties in these ranges, indicate that there is a fundamental flaw or gap in the reasoning behind ERGs. In view of the findings of the science of complex networks, it is not. A major problem with this model is that its Hamiltonian is designed for homogeneous systems, in which edges and triangles are uniformly distributed over the network. Unfortunately, such a homogeneity is not observed in real-world social networks, which are strongly inhomogeneous in terms of the local connectivity and the local clustering [3; 9]. Therefore, it seems that the simples way to overcome the problematic issues with Strauss's model is just to refine its Hamiltonian, because mathematics behind the model is correct [25].

Predictability and Prediction
One says that the ultimate proof of our understanding of natural and manmade systems is reflected in our ability to predict/controll them. In statistical physics, the problem of predictability/controllability is tackled with the help of fluctuation/stability theory and response theory -the two pillars on which non-equilibrium statistical mechanics is built.
In physics it is well-understood that interactions between individuals in a system often lead to an emergent global behavior. This behavior is not only imposed by external controllers/conditions, but may result from internal interactions/details.
These issues are closely related to the problem of possible microscopic realizations 17 In physics, the principle amounts to the second law of thermodynamics. 18 In particular, one should not forget that exponential random graph models can be only used to describe the so-called equilibrium networks. The (real-world) equilibrium network is the one, which is not evolving quickly and, therefore, its properties do not change abruptly.
of the system 19 , their macroscopic perception in terms of the system's phases, and the corresponding phase transitions (or symmetry breaking phenomena). Furthermore, given the ensemble approach to random graphs described in this essay, which directly corresponds to ensemble formulation of statistical physics, one can use and modify the well-known methods from physics (such as fluctuation-response relations, and Onsager reciprocal relations) to apply them to inference on, and analysis of exponential random graph models.
We already know that such generalizations can be done. To be concrete, the ideas have been already applied in purely theoretical considerations about ERGs [15].
Recently, one has also used them to discuss properties and predictability of real-world networks. In particular, having the mathematically tractable yet realistic ERG model of the world trade network, one has shown that bilateral trade fulfils a simple fluctuationresponse theorem describing the susceptibility of trade volume to changes in gross domestic products of trade partners [14; 13]. Therefore, one can also believe that the analogous quantitative response-like relations may also characterize social networks allowing, for example, to predict under which conditions the connected network may disintegrate into disconnected clusters. Cross-References