08_juanico 37 Topologically Evolving Networks Science Diliman (January-June 2003) 15:1, 37-40 Onset of Small-World Behavior in Topologically Evolving Networks D.E. Juanico*, C.P. Monterola, and C.A. Saloma National Institute of Physics, College of Science University of the Philippines Diliman 1101 Quezon City, Philippines E-mail: earl@nip.upd.edu.ph ABSTRACT We evolve topology of a network of N fully-coupled nodes that interact according to repulsion-attraction dynamics within a confining wall. The dynamics portrays each node’s tendency to keep distance from its competitors while maintaining a lighter tendency to resist relative isolation. Each node is characterized by two parameters: an intrinsic mobility µ and a preferred neighboring distance ρ. Onset of clustering is found to occur at a critical variance in mobility, σµ 2 = 1, and in preferred neighboring distance, σµ 2 = 10. This result implies that small-world behavior manifested in clustering can be triggered by the diversity of node population. INTRODUCTION The current interest in networks is part of a broader movement towards research on complex systems. A network of interacting individuals is considered to be a complex system because the collective behavior of the entire network is not deducible from the properties of the individual. This is called “emergent behavior”. Many of the systems in the real world, such as neural networks, social networks, and even the world-wide web, that are yet to be completely understood can be considered to be complex networks (Strogatz, 2001). Interactions between nodes that constitute a network is difficult to determine exactly. However, there are subtle manifestations of this interaction that can be used to motivate a simple dynamical model of the network. Nodes are always located at some finite, nonzero distance from each other. Nodes do not overlap because each node should minimize competition among its neighbors for resources, and the maximum distance is bounded because it needs to interact considerably such that it prevents itself from becoming isolated. In the frame of one node, all other nodes are viewed both as competitors and allies. These qualities can be modelled in terms of short- distance repulsion and long-distance attraction adopted from the interaction between molecular species defined by the Lennard-Jones potential in the field of molecular dynamics. Furthermore, the population of nodes is inherently diverse, such that any two nodes take on different states. In recent studies of complex networks (Amaral et al., 2000), the nodes are characterized by some preferential attachment, which result in sparse connections. As a new perspective, we set aside this property and instead consider a fully-connected network wherein all the nodes interact with one another. The reason is that we believe that the diversity of the nodes has something to do with the emergence of self-organized behavior even if the connections are static.* Corresponding author 38 Juanico, Monterola, and Saloma MODEL We consider a system composed of N agents represented by nodes in a network. The entire network evolves within a bounded region in space, considering limited resources. The state of agent k is represented by φ k = {µ k , ρ k , ϑ k }, wherein k is a measure of the node’s mobility, ρ k is the node’s preferred neighboring distance, and ϑ k determines its sensitivity. The response of the node (k) is defined by its displacement velocity υ k , a function of its separation distance r = r kj = r jk from another node at state φ j . It is defined to be (1) The value for µ k and ρ k is normally different for each particle. The distribution of the value is Gaussian centered at 〈µ〉 = 0.125 and 〈ρ〉 = 10, with variance denoted by σµ 2 and σµ 2 , respectively. The value of ϑ k is set to unity for all particles. Eq. (1) is positive if r < ρ k , such that node k recedes from node j, and negative if r > ρ k , such that node k approaches toward node j. The network evolves topologically in the following way: at each time step t i (1) a connection is randomly selected for update, and (2) node k is displaced by ∆r k = υ kj ∆t due to its interaction with node j according to Eq. (1), wherein ∆t is a fixed time step. The total displacement of a node due to all other nodes is given as (2) wherein ∆r kj is the contribution of one particle to the total displacement. The goal of the evolution is to minimize an energy function E. This energy is defined to be (3) which follows from the assumption that a stable configuration of the network is attained if the nodes settle down at their respective positions. RESULTS Initially, the network is distributed uniformly within a confining wall (Fig. 1). The side of the wall is set to have a length L = 5 〈ρ〉. The network is allowed, not forced, to evolve until a stability criterion has been reached, as given by (4) Let us denote the variance in the states to be (5) In Fig. 1b, the cumulative distribution is expected to be smooth, corresponding to a random distribution of the k kj j k r r ≠ ∆ = ∆∑ 2 2 N N k kj k j j k E r r ≠ ⎛ ⎞ = ∆ = ∆⎜ ⎟ ⎝ ⎠ ∑ ∑ ∑ 610 E E −∆ ≤ { }2 2 2, ,µ ρ ϑδφ σ σ σ= ( ) ( )( )tanh .= − −k k k kr rυ µ ϑ ρ Fig. 1. (a) Initial distribution of the nodes. The length of one side of the confining wall is L = 50; (b) Cumulative distribution of internode separation. (a) (b) 39 Topologically Evolving Networks nodes within the bounded region. If all the nodes have the same mobility and preference, the resulting topology does not exhibit clustering as in Fig.2. Instead, the cumulative distribution (Fig. 2b) has a linear region, which implies that there is approximately a uniform distribution of internode distances. Consequently, the stable configuration appears as a nearly perfect circle (Fig. 2a). If the nodes have different preferences but of similar mobility, the stable configuration has only one cluster at the center of the distribution, as shown in Fig. 3. The cluster consists of nodes that settle with more neighbors. The nodes at the periphery tend to prefer isolation. Clustering is seen to produce three “plateaus” in the cumulative distribution, as shown in Fig. 4b. The first plateau corresponds to the distribution of nodes, with a mean separation 〈r〉 ≈ 2 in each of the six clusters formed (5 arms, 1 center). The second plateau corresponds to 〈r〉 ≈ 9 between adjacent clusters. The third plateau corresponds to 〈r〉 ≈ 16.5 between opposite clusters. DISCUSSION Small-world behavior was first suggested by Watts and Strogatz (Watts & Strogatz, 1998) to explain the collective dynamics of complex networks Fig. 2. Parameters: δφ = {0,0,0}. (a) Stable configuration with final energy, E = 7.03 x 10-7; (b) Cumulative distribution of internode separation of the final configuration. (a) (b) Fig. 3. Parameters: δφ = {0, 10, 0}. (a) Stable configuration with final energy, E = 8.13 x 10-7; (b) Cumulative distribution of internode separation of the final configuration. (a) (b) characterized by fluid connectivity between nodes. Small-world networks are so called because of the surprisingly small average path lengths between nodes in the presence of a large degree of clustering. It has been shown that real complex systems such as the network of movie-actor collaborations, the neuronal network of the worm C. elegans, the world-wide web, and the network of citations of scientific papers behave as small-world networks (Amaral et al., 2000). In this paper, we show that diversity in the node population can trigger the onset of small-world clustering 40 Juanico, Monterola, and Saloma behavior. Adding dynamics in the connectivity between nodes (i.e., taking the possibility of growth of new links and death of old ones) has been shown (Strogatz, 2001; Amaral et al., 2000; Watts & Strogatz, 1998; Bornholdt & Rohlf, 2000; Eguiluz & Zimmerman, 2000) to bring about the emergence of clustering or herding behavior in communication and information networks. However, we have shown that this is not necessarily the only reason that can explain the small-world behavior because a network with static connections may exhibit small-world behavior. To summarize, we have shown that variance in node- specific properties allows us to construct a topology consistent with small-world distributions. In the future, more subtle properties of real-world complex systems may surface out by considering the interplay between node diversity and link dynamics in evolving topology of complex networks. ACKNOWLEDGMENT This work is partially supported by the Commission on Higher Education (CHED). REFERENCES Amaral et al., 2000. Classes of small-world networks. Proc. Natl. Acad. Sci. USA. 97: 11149-11152. Bornholdt, S. & T. Rohlf, 2000. Topological evolution of dynamical networks: Global criticality from local dynamics. Phys. Rev. Lett. 84: 6114-6117. Eguiluz, V.M. & M.G. Zimmerman, 2000. Transmission of information and Herd behavior: An application to financial markets. Phys. Rev. Lett. 85: 5659-662. Strogatz, S.H., 2001. Exploring complex networks. Nature. 410: 268-276. Watts, D.J. & S.H. Strogatz, 1998. Collective dynamics of small-world networks. Nature. 393: 440-442. Fig. 4. Parameters: δφ = {10, 1, 0}. (a) Stable configuration with final energy, E = 5.22 x 10-3; (b) Cumulative distribution of internode separation of the final configuration. (a) (b)