A Study of How the Watts-Strogatz Model Relates to an Economic System's Utility

Abstract

Watts-Strogatz model is a main mechanism to construct the small-world networks. It is widely used in the simulations of small-world featured systems including economic system. Formally, the model contains a parameters set including three variables representing group size, number of neighbors, and rewiring probability. This paper discusses how the parameters set relates to the economic system performance which is utility growth rate. In conclusion, it is found that, regardless of the group size and rewiring probability, 2 to 18 neighbors can help the economic system reach the highest utility growth rate. Furthermore, given the range of neighbors and group size of a Watts-Strogatz model based system, the range of its edges can be calculated too. By examining the containment relationship between that range and the edge number of an actual equal-size economic system, we could know whether the system structure has redundant edges or can achieve the highest utility growth ratio.

Academic Editor:He Huang

School of Information Science and Technology, Donghua University, Shanghai 201620, China

Received 7 February 2014; Revised 8 May 2014; Accepted 8 May 2014; 1 June 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In the 1990s, Watts and Strogatz [1] have shown that the connection topology of biological, technological, and social networks is neither completely regular [2] nor completely random [3] but stays somehow in between these two extreme cases [4]. To get the small-world network, they have proposed the Watts-Strogatz model (WS model) to interpolate between regular and random networks. Since then, a rapid surge of interest for small-world networks throughout natural and social sciences has witnessed the diffusion of new concepts.

Alexander-Bloch et al. [5] systematically explored relationships between functional connectivity, small-world featured complex network topology, and anatomical (Euclidean) distance between connected brain regions. Céline and Guy [6] developed new classification and clustering schemes based on the relative local density of subgraphs on geography and described how the notions and methods contribute on a conceptual level, in terms of measures, delineations, explanatory analyses, and visualization of geographical phenomena. Using the small-world approach Corso et al. [7] suggested a network model for economy. Based on evolving network model, the wealth distribution of a society was constructed qualitatively. Sparked by an increasing need in science and technology for understanding complex interwoven systems as diverse as the world wide web [8, 9], cellular metabolism, and human social interactions [10, 11], there has been an explosion of interest in network dynamics, the computational analysis of the structure, and function of large physical and virtual networks. Besides, some researchers focused on researching the mechanism of the WS model. Kleinberg [12] explained why arbitrary pairs of strangers should be able to find short chains of acquaintances that link them together.

Generally, the abovementioned researchers utilize the WS model as a modeling tool through which they construct the systems with their expertise. Their research looks at the system's "small-world" characteristics such as the average shortest path length [13], clustering coefficient [14], and degree distribution [15]. With the same route, we have built a small-world featured economic system and analyzed the correlation between the system structure and utility growth rate (UGR). A brief review of the works focused on utility is listed as follows. John et al. [16] discussed the economic utility function in the supply chain management covering logistics and marketing scheme. Ben and Mark [17] studied the relationship between net worth and economic performance measured by utility variation. Due to the broad implication of "utility," some researchers from entities other than economic system are drawn into the topic. Torrance [18] provided a new utility measurement and cost-utility analysis method in healthcare. Birati and Tziner [19] introduced the concept of economic utility into the training program usually representing major outlay for many corporations.

During our research we found out that the removal of edges (at least one in five) in the system would not raise any impact on the value of utility function. It can be deduced that there are redundant edges in this small-world featured economic system. Many studies on the network stability [20, 21] also revealed that some edges missing caused by the intentionally attack would not reduce the network connectivity and reliability, despite being considered the advantage of small-world network. However, in an economic system, the useless edges, bringing costs but no profits, are not expected.

The result inspires us to trace back the origins of these redundant edges, that is, the WS model. Since no modification to the group size and the connections among the nodes after the modeling process has been taken, we hypothesize that the system structure is the product of WS model. Equivalently, the WS model would surely exert influence on UGR, because of the proven fact that the system structure has impact on the economic system's performance [22, 23]. Normally, the WS model is expressed as a function with three parameters (group size, number of neighbors, and rewiring probability) controlling the modeling process. The fact is that, during the modeling process, "group size" is fixed and "rewiring probability" has nothing to do with the total amount of edges, and the only variable that may cause redundant edges is "number of neighbors." In this paper, our purpose is to find out how many neighbors and what rewiring probability can help the given size economic system reach the highest UGR and keep the redundant edges as little as possible. Once found, a benchmark network can be generated in accordance with these parameters, compared with which the amount of redundant edges can be detected.

The structure of the paper is designed as follows. Section 2 introduces the WS model and economy model. Based on the model and theory, Section 3 designs the experiment plans. Section 4 is the collection of experimental results. In Section 5, the main contributions of this research are summarized.

2. Literature Review

In this section, we will conduct a literature review on relevant studies. The review includes the description of WS model and economy model.

2.1. WS Model

The WS model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Watts and Strogatz in their joint Nature paper [1].

The mechanism of the model is as follows.

(1) Create a ring over n nodes.

(2) Each node in the ring is connected with its k nearest neighbors ( k - 1 neighbors if k is odd).

(3) For each edge in the " n -ring with k nearest neighbors," shortcuts are created by replacing the original edges u - v with a new edge u - w with uniformly random choice of existing node w at rewiring probability p .

The WS model is included in software package normally expressed as a function. The model contains three forms, including watts_strogatz_graph (), newman_watts_strogatz_graph () [24], and connected_watts_strogatz_graph () [25]. These three models have the approximately same mechanism described above but still there are differences. The watts_strogatz_graph () is in strict accordance with the mechanism. The newman_watts_strogatz_graph () differs in the third step, which is the rewiring probability substituted by the probability of adding a new edge for each node. The connected_watts_strogatz_graph () will repeat the steps in the mechanism till a connected watts-strogatz graph is constructed. In contrast with newman_watts_strogatz_graph (), the random rewiring does not increase the number of edges and is not guaranteed to be connected as in connected_watts_strogatz_graph ().

In NetworkX [26], a Python language software package [27] for the creation, manipulation, and study of the structure, dynamics, and functions of complex network, there is a random WS small-world graph generator: [figure omitted; refer to PDF] where n is the number of nodes in the graph, k is the number of neighbors each node connected to, and p is the probability of rewiring each edge in the graph.

2.2. Economy Model

This economy model derives from the one proposed by Wilhite [28] and is designed according to the definition of utility [29]. Utility is a means of accurately measuring the desirability of various types of goods and services and the degree of well-being those products provide for consumers. This measure is normally presented in the form of a mathematical expression utility function [30] and can be utilized with just about any type of goods or service that is secured and used by a consumer.

In this model, a certain amount of independent agents is created. Two types of goods, one of which must be traded in whole units and the other is infinitely divisible, are assigned to each agent as the existing wealth to circulate in the market. The portion of the goods is randomly assigned at the beginning of the experiment. There is no production and no imports; thus the aggregate stock of goods at the beginning of the experiment is the stock at the end.

Each agent's objective is to improve its own Cobb-Douglas utility function [31] in each period by engaging in voluntary trade. Formally, ^{U i} depends on the individual's existing wealth of _{g 1} and _{g 2} : [figure omitted; refer to PDF] where n is the amount of agents.

The entire economic society is composed of every transaction. A transaction is a process in which two nodes exchange the goods since one node's questing for a negotiating price chance is being responded. An opportunity for mutually beneficial transaction exists if the marginal rate of substitution (MRS) of two agents differs. MRS reflects the agent's willing to give up _{g 2} for a unit of _{g 1} . With the utility function in (1), the MRS of agent i is [figure omitted; refer to PDF] where ^{U [variant prime]} ( · ) is the first derivative of U .

The model assumes that each agent reveals its MRS. In the experiment, agents search for beneficial trade opportunities according to the MRS and then establish a price to initiate a transaction. Any agent can either trade _{g 2} for _{g 1} or trade _{g 1} for _{g 2} at the expense of price. Throughout these experiments, the trading price _{p i , j} between agent i and agent j is set according to the following rule: [figure omitted; refer to PDF] The questing node would pay _{p i , j} by _{g 2} to exchange one unit of _{g 1} . Meanwhile, the responding node would add _{p i , j} to its stock of _{g 2} and sell one unit of _{g 1} to the questing node. The transaction proceeds as long as the trade benefits each node's ^{U i} , and stops when one of the nodes is in lack of _{g 1} or cannot afford the price _{p i , j} . Each transaction is atomic in the experiments; namely, it would not suspend till the whole process is fulfilled. In the experiments, every active transaction will be considered as one time trade with two portions of trade volumes, since the income and outcome string are both taken into account.

Once a transaction stops, the questing node will search again for a new opportunity according to the trade rules until no node responds to it and so on. Another node is selected as questing node to engage in a transaction. The economy society evolves like this and stops at the network's equilibrium. The utility growth rate (UGR) is [figure omitted; refer to PDF] where ^{U e i} is the posttrade economic utility of node i .

Equilibrium is a point when agents cannot find trading opportunities that benefit any individuals. Feldman [32] studied the equilibrium characteristics of welfare-improving bilateral trade and showed that as long as all agents possess some nonzero amount of one of the commodities (all agents have some _{g 1} or all agents have some _{g 2} ), then the pairwise optimal allocation is also a Pareto optimal allocation. In this experiment, all agents are initially endowed with a positive amount of both goods; thus the equilibrium is Pareto optimal [33].

3. Experimental Design

A series of experiments are designed to run in the environment of Python program, aiming at finding out how many neighbors and what rewiring probability can help the given size economic system reach the highest UGR.

At the beginning of the experiments, artificial economy society is abstracted to a network composed of nodes and edges to conduct the analysis by the network theory. According to the economy model in Section 2.2, each society has agents (represented by nodes), trading rules (represented by edges), and goods _{g 1} and _{g 2} (represented by the endowment of each node).

The design can discuss any market with nodes in multiple of 10. We list the economic system at the group size from 10 to 200 in this paper. After the generation of nodes, a portion of the society wealth is assigned to each node and so does the same Cobb-Douglas utility it intends to maximize. Network structure defines the edges among the nodes, constraining the extent of trade partners each node can reach. Then the systems undertake the trading process keeping to the one defined in the economy model. Once the economic system reaches the equilibrium, the UGR of the system can be computed and bonded to the parameters set as the correspondence.

The network structures are generated by the random WS model complying with the mechanism in Section 2.1. This is the key process of the experiments. Different parameter sets (PS), including the group size (gs), the number of neighbors (nn), and the rewiring probability (rp), represented as PS = (gs, nn, rp) would be endowed to the WS model. The initial parameter set is PS = (10, 2, 0.01) and each variable would increase progressively. To enhance the operability, the parameters would increase linearly at different step size as follows.

(1) The group size starts at 10 and grows with a step size of 10.

(2) The number of neighbors starts at 2 and grows with a step size of 2. The WS model constraints that the number of neighbor each node attach to cannot exceed half of the group size and must be integer.

(3) The rewiring probability starts at 0.01 and grows with step size of 0.01.

The forming of a new parameter set would trigger the modeling and trading process.

A hierarchical nested loop is designed for fulfilling the incrementing as follows.

(1) Fixing gs and rp. After the succeeding modeling and trading process, increase nn by its step size. To generate sufficient experimental data, simulations are taken repeatedly under the same parameter set.

(2) Once nn reaches its upper bound, increase rp by its step size and go to (1).

(3) Once rp reaches its upper bound, the experiments stop.

Figure 1 describes the design of the experiment.

Figure 1: Experimental design.

[figure omitted; refer to PDF]

Figure 2 is an instance of a network assigned by the parameter set (20, 6, 0.02).

Figure 2: An instance of a small-world network.

[figure omitted; refer to PDF]

4. Experimental Result

In this section, we collected the results of the experiments. Figure 3 illustrates, under the same rp, the probability when nn takes a defined value so that the economic system generated by the WS model reaches the highest UGR. The x axe represents the number of neighbors each node can have, and y axe in unit of percent (%) shows the probability that the corresponding nn achieves the highest UGR, represented as hp. Each subgraph is an average record of 100-time repeated simulations. 6 different sized systems are showed as examples. Through the observation, it is found that, regardless of the group size, 2 to 18 neighbors can achieve the highest UGR of an economic system; that is, [figure omitted; refer to PDF] Moreover, Figure 3 also reveals the rising tendency of hp when the group size grows.

The probability when nn takes a defined value so that the economic system reaches the highest UGR.

(a) gs = 20 ; rp = 0.02

[figure omitted; refer to PDF]

(b) gs = 50 ; rp = 0.02

[figure omitted; refer to PDF]

(c) gs = 100 ; rp = 0.02

[figure omitted; refer to PDF]

(d) gs = 150 ; rp = 0.02

[figure omitted; refer to PDF]

(e) gs = 180 ; rp = 0.02

[figure omitted; refer to PDF]

(f) gs = 200 ; rp = 0.02

[figure omitted; refer to PDF]

This conclusion is reconfirmed in Figure 4(a), which describes the total sum of hp in the group size from 10 to 200. Lining up the points in Figure 4(a) and getting Figure 4(b), the pattern of the probability approximates the Poisson distribution [34] and the mathematical expectation _{E hp} = 12 .

The total sum of hp in the group size from 10 to 200.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

Since the extent of hp has been found, bonding with gs, the extent of edges can be calculated also. It can be deduced that once the value of nn goes beyond the extent, the WS model would surely generate redundant edges in the economic system. Table 1 compares the number of edges (NE) when each node has the uttermost neighbors, upper end of hp , and _{E hp} neighbors. Under the same group size, uttermost neighbors generate the maximum edges the WS model can; the upper end of hp generates the upper bound number of edges, indexing that beyond this bound the system definitely has redundant edges; _{E hp} generates the mathematical expectation number of edges.

Table 1: A comparison of NE among different group size systems.

Group size	Uttermost neighbors	the upper end of hp	E hp
50	600	450	300
100	2400	900	600
150	5550	1350	900
200	9800	1800	1200

In Table 1, compared to the systems generated under the upper end of hp and _{E hp} , the one under uttermost neighbors has multiple edges and the gap would exaggerate along with the enlargement of group size. Due to the guiding significance of the bound generated by the upper end of hp , any system with NE beyond the bound has costly redundant edges. However, the redundant edges have advantages as shields when the economic system confronts the random or deliberate attacks. Thus the complete removal of redundant edges is unnecessary.

In the random WS model, variable rp cannot bring changes in NE but can reform the network structure. Figure 5 combines a group of graphs describing the correlation between nn ( x axe) and UGR ( y axe) when gs = 80. It reveals that, under the same group size, UGR differs if the network structure and endowment changes are reflected in the pattern of each subgraph varying. However, the pattern of each graph conforms to the range hp ∈ [ 2,18 ] and has similar curvature.

The pattern of UGR when gs = 80 and rp increases linearly.

(a) gs = 80 ; rp = 0.01

[figure omitted; refer to PDF]

(b) gs = 80 ; rp = 0.02

[figure omitted; refer to PDF]

(c) gs = 80 ; rp = 0.03

[figure omitted; refer to PDF]

(d) gs = 80 ; rp = 0.04

[figure omitted; refer to PDF]

(e) gs = 80 ; rp = 0.05

[figure omitted; refer to PDF]

(f) gs = 80 ; rp = 0.06

[figure omitted; refer to PDF]

(g) gs = 80 ; rp = 0.07

[figure omitted; refer to PDF]

(h) gs = 80 ; rp = 0.08

[figure omitted; refer to PDF]

(i) gs = 80 ; rp = 0.09

[figure omitted; refer to PDF]

(j) gs = 80 ; rp = 0.1

[figure omitted; refer to PDF]

Despite the observation on Figure 5, we suppose that the pattern of UGR would decrease gradually when nn is beyond 18, which is the upper end of hp. To verify the conjecture, gs, rp, and nn in the parameter set would increase linearly as defined in Section 3 and after repeated simulations the UGR of systems generated by WS model is collected in Figure 6. It is confirmed that independent of group size and rewiring probability, if nn > 18, the UGR would decrease gradually. Although it may not be a monotonic decreasing, the decreasing tendency would be kept.

The pattern of UGR when gs, rp, and nn increase linearly.

(a) gs = 60 ; rp = 0.01

[figure omitted; refer to PDF]

(b) gs = 120 ; rp = 0.05

[figure omitted; refer to PDF]

(c) gs = 150 ; rp = 0.08

[figure omitted; refer to PDF]

(d) gs = 170 ; rp = 0.1

[figure omitted; refer to PDF]

(e) gs = 200 ; rp = 0.2

[figure omitted; refer to PDF]

When constructing the systems in Figures 5 and 6, we also consider that the possible effect on hp and UGR may be exerted by the endowments to goods _{g 1} and _{g 2} . The fixed group size systems in Figure 5 are endowed with randomly generated _{g 1} and _{g 2} and, in Figure 5, different group size systems are discussed, which means that their endowments cannot keep consistent with each other. The result shows that the UGR varies on account of the endowments and network structure, but the range of hp cannot be influenced.

5. Conclusion

This research combines economic theory, network theory, and computer simulations to examine the parameters set assigned to the WS model relating to an economic system's UGR. We discovered that, regardless of the group size and rewiring probability, (1) 2 to 18 neighbors and the corresponding computable number of edges can help an economic system reach the highest UGR; (2) if the node has more than 18 neighbors, the UGR would decrease gradually and the pattern is not monotonic but would keep the decreasing tendency; (3) different endowments to goods _{g 1} and _{g 2} would not impact the range of neighbors which can help the system achieve the highest UGR. In the practical application, it can be construed that (1) acting as a measurement judges whether a system can reach the highest UGR based on its current structure; (2) when the resource is in the hands of a fraction of people, the resource can derive the highest value for the owners and the rest of people; (3) once keeping the superiority of minority owners, the value of resource would not decrease or increase according to its quantity.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] D. J. Watts, S. H. Strogatz, "Collective dynamics of "small-world" networks," Nature , vol. 393, no. 6684, pp. 440-442, 1998.

[2] W.-K. Chen Graph Theory and Its Engineering Applications , World Scientific, Singapore, 1997.

[3] P. Erdos, A. Rényi, "On random graphs. I," Publicationes Mathematicae , vol. 6, pp. 290-297, 1959.

[4] D. J. Watts, "Networks, dynamics, and the small-world phenomenon," The American Journal of Sociology , vol. 105, no. 2, pp. 493-527, 1999.

[5] A. F. Alexander-Bloch, P. E. Vértes, R. Stidd, F. Lalonde, L. Clasen, J. Rapoport, J. Giedd, E. T. Bullmore, N. Gogtay, "The anatomical distance of functional connections predicts brain network topology in health and schizophrenia," Cerebral Cortex , vol. 23, no. 1, pp. 127-138, 2013.

[6] R. Céline, M. Guy, "A small world perspective on urban systems," Methods for Multilevel Analysis and Visualisation of Geographical Networks , vol. 11, pp. 19-32, 2013.

[7] G. Corso, L. S. Lucena, Z. D. Thomé, "The small-world of economy: a speculative proposal," Physica A: Statistical Mechanics and Its Applications , vol. 324, no. 1-2, pp. 430-436, 2003.

[8] K. Musial, P. Kazienko, "Social networks on the internet," World Wide Web , vol. 16, no. 1, pp. 31-72, 2013.

[9] X. Cheng, J. Liu, C. Dale, "Understanding the characteristics of internet short video sharing: a youtube-based measurement study," IEEE Transactions on Multimedia , vol. 15, no. 5, pp. 1184-1194, 2013.

[10] D. Eppstein, M. T. Goodrich, M. Löffler, D. Strash, L. Trott, "Category-based routing in social networks: membership dimension and the small-world phenomenon," Theoretical Computer Science , vol. 514, pp. 96-104, 2013.

[11] D. César, L. Igor, "Structure and dynamics of transportation networks: models, methods and applications," The SAGE Handbook of Transport Studies , pp. 347-364, 2013.

[12] J. Kleinberg, "The small-world phenomenon: an algorithm perspective," in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pp. 163-170, 2000.

[13] S. Milgram, "The small-world problem," Psychology Today , vol. 2, pp. 60-67, 1967.

[14] A. Kemper Valuation of Network Effects in Software Markets: A Complex Networks Approach , Springer, Heidelberg, Germany, 2010.

[15] R. Albert, A.-L. Barabási, "Statistical mechanics of complex networks," Reviews of Modern Physics , vol. 74, no. 1, pp. 47-97, 2002.

[16] T. John, P. Theodore, L. Terry, "Supply chain management and its relationship to logistics, marketing, production, and operations management," Journal of Business Logistics , vol. 29, no. 1, pp. 31-46, 2008.

[17] B. Ben, G. Mark, "Financial fragility and economic performance," The Quarterly Journal of Economics , vol. 105, no. 1, pp. 87-114, 1990.

[18] G. W. Torrance, "Utility measurement in healthcare: the things I never got to," PharmacoEconomics , vol. 24, no. 11, pp. 1069-1078, 2006.

[19] A. Birati, A. Tziner, "Economic utility of training programs," Journal of Business and Psychology , vol. 14, no. 1, pp. 155-164, 1999.

[20] C. Li, G. Chen, "Stability of a neural network model with small-world connections," Physical Review E--Statistical, Nonlinear, and Soft Matter Physics , vol. 68, no. 5, 2003.

[21] X. Li, X. Wang, "Controlling the spreading in small-world evolving networks: stability, oscillation, and topology," IEEE Transactions on Automatic Control , vol. 51, no. 3, pp. 534-540, 2006.

[22] M. O. Jackson, A. Wolinsky, "A strategic model of social and economic networks," Journal of Economic Theory , vol. 71, no. 1, pp. 44-74, 1996.

[23] Y. A. Ioannides, W. B. Arthur, S. Durlauf, D. Lane, "Evolution of trading structures," The Economy as an Evolving Complex System II , pp. 129-168, 1997.

[24] M. E. J. Newman, D. J. Watts, "Renormalization group analysis of the small-world network model," Physics Letters A: General, Atomic and Solid State Physics , vol. 263, no. 4-6, pp. 341-346, 1999.

[25] http://networkx.github.io/documentation/latest/

[26] A. Hagberg, D. Conway, "Hacking social networks using the Python programming language (module II--why do SNA in NetworkX)," in Proceedings of the International Network for Social Network Analysis Sunbelt Conference, 2010.

[27] "Python 3.4.0 beta 3," Python Software Foundation, 2014

[28] A. Wilhite, "Bilateral trade and "small-world" networks," Computational Economics , vol. 18, no. 1, pp. 49-64, 2001.

[29] A. Marshall Principles of Economics: An Introductory Volume , Macmillan, London, UK, 8th.

[30] J. E. Ingersoll Jr. Theory of Financial Decision Making , Rowman and Littlefield, Totowa, NJ, USA, 1987.

[31] D. W. Caves, L. R. Christensen, "Global properties of flexible functional forms," The American Economic Review , vol. 70, no. 3, pp. 422-432, 1980.

[32] A. Feldman, "Bilateral trading processes, pairwise optimality, and Pareto optimality," Review of Economic Studies , vol. 40, no. 4, pp. 463-473, 1973.

[33] A. Sen, "Markets and freedoms: achievements and limitations of the market mechanism in promoting individual freedoms," Oxford Economic Papers , vol. 45, no. 4, pp. 519-541, 1993.

[34] J. H. Ahrens, U. Dieter, "Computer methods for sampling from gamma, beta, poisson and binomial distributions," Computing , vol. 12, no. 3, pp. 223-246, 1974.