## Abstract

Network rewiring as a method for producing a range of structures was first introduced in 1998 by Watts & Strogatz (*Nature* **393**, 440–442. (doi:10.1038/30918)). This approach allowed a transition from regular through small-world to a random network. The subsequent interest in scale-free networks motivated a number of methods for developing rewiring approaches that converged to scale-free networks. This paper presents a rewiring algorithm (RtoS) for undirected, non-degenerate, fixed size networks that transitions from regular, through small-world and scale-free to star-like networks. Applications of the approach to models for the spread of infectious disease and fixation time for a simple genetics model are used to demonstrate the efficacy and application of the approach.

## 1. Introduction

A rewiring method for transitional networks was first introduced in 1998 by Watts & Strogatz [1]. This model allowed a probability of rewiring to control the transition from a regular via a small-world to random network, where the probability was equivalent to the number of rewiring operations. Subsequently, the introduction of scale-free networks [2,3] and the use of networks for modelling [4–6] increased interest in the transitional properties of networks. However, traditional scale-free models were based on growing networks, where new nodes and edges were introduced at each step of the algorithm. Although the growth process was initially argued to be essential for producing scale-free properties, a number of early works demonstrated that the introduction of new nodes was not necessary [7–9].

However, apart from [7], these approaches did add edges to an initial network configuration. A review article by Keller [10] suggested that scale-free networks are easy to generate via a variety of mechanisms. A number of scale-free models have subsequently been presented, using a rewiring process for a fixed number of nodes and edges. Kawachi [11] published a phase transition model that allowed a single parameter model transition from regular to scale-free, extending the Watts and Strogatz model. Variations of this model have been used to study the effect of network structure on processes such as genetic drift [12] and military communication [13], although this model often produced disconnected networks, and the convergence properties were not well defined. Other models for fixed network architectures that have stationary scale-free distributions under a range of conditions include Park & Lai [14], Ree [15,16] and Xie *et al.* [17]. The field of statistical mechanics has also been used to examine network construction [18,19], using the metaphor of temperature and total energy to determine the phase of the network. These methods demonstrate a flexible approach to network creation; however, they involve a number of parameters and are more complex than the approach presented here.

Although previous work has presented a range of network rewiring mechanisms for producing scale-free networks, the focus has been on the steady-state behaviour of the algorithms. However, there is also interest in using these methods to produce a broad range of network classes, and to examine the properties of a defined process operating on these networks as the network topology changes. For example, rewiring models (with a fixed number of nodes and edges) have been used in a range of fields for understanding how variations in connectivity affect process, including epidemiology [20], genetics [21] and theoretical biology [12]. In addition, work in the areas of complex systems [4] and evolutionary dynamics [22] use network structures for generalizing behaviour over a range of connectivities. The main emphasis has been on models that converge to scale-free networks, although there is no requirement that these should be the final converged state of the network.

The emphasis on scale-free networks as a rewiring steady-state is possibly owing to the historical interest in scale-free structures, motivated by their prevalence in nature. However, a method that not only allows the dynamics of a process to consider these types of networks, but also includes other representations, would allow a more complete understanding of the dynamics of a process. For example, a process on a star-like network is potentially quite different from scale-free or random networks [22]. Lieberman *et al.* [22] examined a range of graph structures and the general dynamics that they afford. In particular, they discussed the amplifying properties of star-like structures, noting that these types of networks could occur with cell differentiation, developmental systems and the immune system. Therefore, allowing a network to transition towards these amplifying network structures may offer additional insights into the dynamics of a process being modelled.

This paper presents a rewiring algorithm that transitions from a regular network, via small-world, random and scale-free, to a star-like network. Because many modelling processes require undirected, non-degenerate, connected networks we limit ourselves to this type of network, although extensions to directed networks would be straightforward. The purpose of the algorithm is to allow researchers to model processes across a range of networks without having to handcraft individual networks with different properties. The algorithm is not intended to mimic any natural or man-made process, however it does allow an ordered and continuously varying set of networks to be produced that cover a broad range of such structures. Example applications using this algorithm are shown in §3.

### (a) Definition of a star-like network

The standard definition of a star network is one with *N* nodes and *N*−1 edges, where one node has degree=*N*−1 and all other nodes have degree=1 [22]. A star-like network in this paper is produced by a rewiring procedure that attempts to create a star network, however the number of edges *E*>*N*−1. These edges are constrained in two ways: the network must be non-degenerate (no repeated edges between nodes), and the edges are undirected. In this case, we can calculate the smallest number of nodes that are required to use the edges that remain after a star network is created. Consider a network with *N* nodes and *E* edges (*E*>*N*). Because *N*−1 edges are used to form a star with a single node, *E*−(*N*−1) edges remain that must be rewired. The most compact arrangement to use these edges is a fully connected subgraph. The number of edges *E*_{M} used in a fully connected graph of *M* nodes is given by *E*_{M}=(*M*−1)+(*M*−2)+⋯+1=*M*(*M*−1)/2. Solving for *M*, assuming we are given *E*_{M} edges gives us the ceiling function for ⌈*M*⌉
*N* nodes and *E* edges (*E*>*N*), the limiting case would be a single node with (*N*−1) edges, and a fully connected subgraph of ⌈*M*⌉ nodes, where *E*_{M}=*E*−(*N*−1). For example, a network with *N*=500,*E*=2000 (mean degree *M*⌉=56. This defines the limiting case of a star-like network for our purposes.

## 2. Rewiring beyond scale-free

The algorithm presented here is based on the work of Ree [15,16], and so a brief review of the Ree algorithm is appropriate. Given a graph *G* with *N* nodes (vertices) and *E* edges, the Ree algorithm commences by selecting two random nodes *i* and *j* with degrees *k*_{i} and *k*_{j}. An edge from *i* is transferred to *j* with an exchange probability *R* defined by equation (2.1), where the case of a 0 degree node is ignored given the requirement for a connected graph. The exchange process requires an edge from *i* to be selected, and therefore, a connected vertex *p* with edge *e*_{ip} to be selected. Ree presents several options (smallest, random, largest) for selecting this *p*, with the selection of the smallest node being used for scale-free networks. Given the smallest degree node *p* connected to *i* the probability that the edge *e*_{ip} will be rewired to node *j* is given by *R*. In addition, to ensure the non-degenerate case, the following conditions must also be true: *p*≠*j* and the edge *e*_{pj} cannot already exist. If either of these conditions are true, then the rewiring procedure is aborted [16]. The steady-state scaling of this model is related to parameter *β* in equation (2.1) and the mean degree *N*. Ree shows [15] that this relationship results in either a steady-state exponential or power-law graph. For a non-degenerate, undirected graph the algorithm converges to a power-law when *α*_{c}(*β*) is an empirically derived formula (see [15]). However, the setting of *β* was quite sensitive to the initial regular network configuration, using the algorithm somewhat difficult to tune for different network configurations.

Although from a mathematical perspective, there is a great deal of interest in developing mechanisms that converge to a scale-free distribution, a general rewiring procedure that can produce a range of network properties is also desirable. Here, we introduce a modified version of the Ree algorithm (referred to as RegulartoStar (RtoS)) that commences with a regular graph and, through rewiring, produces small-world, power-law-like distributions and converges towards a star-like network.

### (a) The RtoS algorithm

Given a minimum degree *k*_{min} (for a star-like final network *k*_{min}=1) a single rewiring step of RtoS is defined as follows

(i) randomly select a giver node

*i*, where*k*_{i}>*k*_{min};(ii) preferentially select (equation (2.2)) a receiver node

*j*, where*k*_{j}≥*k*_{i};(iii) select the smallest degree node

*p*connected to*i*; and(iv) rewire edge

*e*_{ip}to node*j*creating edge*e*_{pj}.

Step 1 ensures that nodes with *k*≤*k*_{min} are not selected as either giver or receiver nodes and are therefore removed from the rewiring process. The preferential selection of the receiver node (step 2) means that scale-free properties are produced during the rewiring prior to convergence. Note that equation (2.2) uses the Iverson bracket to indicate the probability of selection is summed over just those nodes that satisfy *k*_{j}≥*k*_{i} and does not include the giver node *i*. Any node not satisfying these conditions is set to a selection probability of zero. Step 3 is based on the empirical results of Ree, and is also key in producing the final star-like network. This is clear by considering the transition of a network (such as shown in figures 1 and 2) towards a hub node with a large degree connected to nodes with a small degree. Connecting nodes with a small degree to the main hub node is an intermediate state that produces power-law-like structures and ultimately (depending on the number of edges and nodes) produces a star-like network.

The non-degeneracy of *N* requires the following conditions to be true for a successful rewiring: *j*≠*i* and edge *e*_{pj} does not exist. Although steps (i) … (iii) will always succeed, even in a converged network, the rewiring (step (iv)) will always fail when the network has converged. However, this step is not guaranteed to succeed each time, because the node *p* may already be connected to node *j*. This failed rewiring step is used to indicate when the rewiring process is near convergence. For all examples, in this paper, the algorithm is halted once step (iv) consecutively fails 1000 times.
*i* is reduced by one and all nodes with degree *k*=*k*_{min} are removed from the selection process. The algorithm converges to a star if *E*=*N*−1 (the minimum criteria for a connected network). In addition, the non-degenerate requirement means that a fully connected network is a fixed (converged) point. For *E*>*N*, a star-like network is generated in the limit, as previously described in §1a. Two example transition networks produced using RtoS, commencing with a regular ring with *N*=20 and mean degree

### (b) Properties of RegulartoStar

An analytical model describing the time-varying probability distribution *P*(*k*,*t*) for RtoS can at best only be approximated given the requirements of selecting nodes with certain characteristics. Because the stationary distribution for RtoS is a star-like structure, previous approaches to model *P*(*k*,*t*) are not appropriate. However, the number of rewirings to convergence, a useful property for rewiring normalization, can be approximated by examining the overall shape of this function for a range of *N*. The number of rewirings (*r*) to convergence for several networks and varying mean degree is shown in figure 2, where the points are measured data using RtoS. The shape of this rewiring pattern can be approximated by considering the base cases for rewiring a network with *N* nodes and mean degree *r*=0 if *S* is a scaling function. By fitting the data for small values of *N*, it was observed that *r* was proportional to *N* and *r*
*N* and small *N* increases the predicted number of rewirings is overestimated for *r* is given in appendix A; however, the bound is not very tight, because the rewiring constraints could not be incorporated in the model. We therefore use equation (2.3) to normalize the observed number of rewirings for all presented results.

The normalized mean clustering coefficient, path length, example networks and degree distributions from a regular ring to star-like network are shown in figure 3. The rewiring count *N* and *N*−1 edges are used for the star, the resulting clustering coefficient would be ≈0.2. Because *C*_{0}=0.667 for the example in figure 3 this gives a normalized clustering coefficient of ≈0.3. In the limit for *N*=500 and

The cumulative degree distribution for a range of rewirings is shown in figure 4. The equivalent random and scale-free network degree distributions are shown as a way of comparison. Although a true (straight line) scale-free distribution is not created, the similarity between RtoS and the Barabasi model is clearly shown when *r*=0.37 suggests that the distribution is not exactly exponential and appears to have some power-law properties.

Figure 5 shows the mean clustering coefficient *C*(*k*) versus degree (*k*). Of interest here is that when *C*(*k*)=*k*^{γ} with *γ*≈−1. This has been observed in data representing socioeconomic networks, suggesting a hierarchical organization [19,23]. Given that this same network (figure 4) shows some power-law properties suggests that the preferential selection of the receiver node in RtoS combines with the property of star-like hubs. The creation of cliques when RtoS has converged is clearly evident (*k*≤50 having *C*(*k*) close to 1.0.

## 3. Examples

Two examples will be used to demonstrate the efficacy of RtoS for examining the dynamics of a process over a range of network classes. The first example is based on Watts & Strogatz [1], where a simple model for the spread of infection is examined. At each time step, a node with an infectious individual can spread to neighbouring uninfected nodes with probability *d*. A node that has become infected is removed from the population after one time step, representing the condition that the infected individual has either died or become immune. The critical infectiousness *d*_{half}, representing the minimum infection probability required to infect half of the population, is shown in figure 6. The results show that the RtoS algorithm has produced networks with the same *d*_{half} properties as a random and scale-free network. In addition, the increase in *d*_{half} as the network starts to produce star-like structures is clearly evident. This result suggests that disease-resistant networks occur as hub-like nodes start to be produced, and is related to the clustering coefficient of the network. The model suggests that network structures produced when *d*_{half} increases beyond the value for regular networks (*d*_{half}=0.34) may have relevance in understanding biological population structures that appear to be disease resistant. This phase change is clearly evident in figure 6; however, the authors are not aware of work that considers these intermediate population structures that are approaching a star network.

The second example is a simple genetics model where the time to fixation (or loss) of mutations is considered. Here, each node represents an individual with a single allele (gene) that is either on or off. The population is randomly initialized with half of the population containing the mutation (on). Each time step the gene value at a node in the next generation is determined by randomly selecting from the neighbourhood (immediate nodes connected by an edge) of that node. The time to fixation of the population (all nodes have the same gene value) for a range of network rewirings is shown in figure 7. The fixation time is related to the path length; however, there is a change in fixation time between

## 4. Conclusion

This paper has presented a simple rewiring algorithm, RtoS, that allows a regular, non-degenerate, undirected network to transition through a range of properties before converging on a star-like distribution. The use of RtoS as a method for exploring the properties of a process model have been demonstrated, and shows that information can be obtained regarding process dynamics that would not be apparent if the rewiring converged to a scale-free or random network. Ideally, the properties of a network rewiring method should always produce a connected network. Although not presented here, disconnected networks were only produced (over 100 runs for a range of network size and

## Ethics

No ethical considerations required for this research.

## Data accessibility

Simulations were created, using the algorithms presented here. All data are reproducible, using the methods presented in this paper.

## Authors' contributions

P.A.W. carried out the simulation work, participated in the design and analysis, produced the initial draft of the paper. G.D. provided feedback on the design and analysis, contributed to writing the final paper, independently confirmed the results. P.A.W. and M.P. developed the mathematical model for convergence and the approximation for rewiring.

## Competing interests

We have no competing interests.

## Funding

Initial work was partly supported through the School of Business, University of Otago, as part of the primary authors sabbatical leave.

## Acknowledgements

We thank the Maths and Statistics department for feedback from a seminar given by the primary author. Prof. Spencer (University of Otago) must also be thanked for feedback on early developments of the research.

## Appendix A. Bounds on network rewiring

Consider a network with *N* nodes and *E* edges (double counted). Let *n*_{k} be the number of nodes with degree *k*. Then

Except that it allows multiple edges and self-loops, the following ‘move’ captures what we mean by a rewiring: choose a pair (*i*,*j*), where 1<*i*≤*j*<*N*−1 and *n*_{i},*n*_{j}≥1, then set

We start the network in a regular configuration: *s* and *m*, 1≤*m*≤*N*−1, such that

Note that the final state maximizes the *variance* of the node degrees. Because the mean of the node degrees is fixed, the final state maximizes
*S* always increases. Initially, *S*=*s*(*N*−1)^{2}+*m*^{2}+*N*−*s*−1. Therefore, we obtain the following upper bound on *r*

- Received April 1, 2016.
- Accepted September 1, 2016.

- © 2016 The Author(s)

Published by the Royal Society. All rights reserved.