# Scale-Free Random SAT Instances
## 2 Generation of Scale-Free Graphs  
Generating scale-free formulas has an obvious relationship with the generation of scale-free graphs. In this section, we review some graph generation methods developed by researchers on complex networks. A scale-free graph is a graph where node degrees follow a power-law distribution \(P(k)\sim k^{-\gamma}\), at least asymptotically, where exponent \(\gamma\) is around 3. A preferential attachment [25] has been proposed as the natural process that makes scale-free networks prevalent in nature. This process can be used to generate scale-free graphs as follows: Given two numbers \(n\) and \(m\), we start at time \(t=m+1\) with a clique of size \(m+1\) where all nodes have degree \(m\) (in the limit when \(n\) tends to infinity, the starting graph is not relevant). Then, at every time \(t=m+2,\ldots,n\), we add a new node (with index \(t\)), connected to \(m\) distinct and older nodes \(s<t\), such that the probability that a node \(s\) gets a connection to this new node \(t\) is proportional to the degree of \(s\) at time \(t\). This process generates a scale-free graph with asymptotic exponent \(\gamma=3\), average node degree \(\mathrm{E}[k]=2\,m\) and minimum degree \(k_{i}\geq m\), for all nodes. We can also prove that the expected degree of node \(i\) is \(\mathrm{E}[k_{i}]\sim i^{-\beta}\), for small values of \(i\), where \(\beta=0.5\). In order to explain the origin of scale-free networks where \(\gamma\
eq 3\), several models have been proposed [26]. One of these models is based on the _aging_ of nodes [27]. This means that the probability of a node \(s\) (created at instant \(s\)) obtaining a new edge at instant \(t\) is proportional to the product of its degree and \((t-s)^{-\alpha}\), where \(t-s\) is the _age_ of the node. This model generates scale-free graphs when \(\alpha<1\). When \(\alpha\to 0\), the exponents of the power-laws \(P(k)\sim k^{-\gamma}\) and \(\mathrm{E}[k_{i}]\sim i^{-\beta}\) are \(\gamma=3+4(1-\ln 2)\alpha\) and \(\beta=1/2-(1-\ln 2)\alpha\), respectively. Therefore, the value of \(\alpha\) may be used to tune the values of \(\gamma\) and \(\beta\). In the previous methods, _growth_ in the number of nodes is essential. There are other methods, usually called _static_, where the number of nodes is fixed from the beginning and during the process we only add edges. The simplest method, assuming uniform probability for all graphs with a scale-free degree distribution in the degree of nodes, is the _configuration method_, which can be implemented as outlined in the next paragraph. Given a desired number of nodes \(n\) and exponent \(\gamma\), for every node \(i\in\{1,\ldots,n\}\), generate a degree \(k_{i}\) following the probability \(P(k)=k^{-\gamma}/\zeta(\gamma)\), independently of \(i\). Here, \(\zeta(x)=\sum_{i=1}^{\infty}i^{-x}\) is the Riemann zeta function. Then, generate a graph with these node degrees, ensuring that all of them are generated with the same probability. This can be achieved, for instance, with an unfold-fold process: In the unfolding, we replicate node \(i\), with degree \(k_{i}\), into \(k_{i}\) new nodes with degree 1. Then, we randomly generate a graph where all nodes have degrees equal to one, ensuring that all 1-regular graphs with \(\sum_{i=1}^{n}k_{i}\) nodes are generated with the same probability. Then, in the folding, we merge the \(k_{i}\) nodes that came from the replication of \(i\), into the same node. When there is an edge between two nodes and these two nodes are merged, a self-loop is created. Similarly, when we have two edges \(i_{1}\leftrightarrow j\) and \(i_{2}\leftrightarrow j\) and \(i_{1}\) and \(i_{2}\) are merged, a duplicated edge is created. Therefore, we reject the resulting graph, if it contains self-loops or multiple edges between the same pair of nodes. Alternatively, we can also apply the Erdos-Renyi generation method to the unfolded set of nodes, with the average node degree equal to one.