Distinct Clusterings and Characteristic Path Lengths in Dynamic Small-World Networks with Identical Limit Degree Distrib
- PDF / 537,856 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 86 Downloads / 161 Views
Distinct Clusterings and Characteristic Path Lengths in Dynamic Small-World Networks with Identical Limit Degree Distribution Yilun Shang
Received: 5 April 2012 / Accepted: 21 September 2012 / Published online: 2 October 2012 © Springer Science+Business Media New York 2012
Abstract Many real-world networks belong to a particular class of structures, known as small-world networks, that display short distance between pair of nodes. In this paper, we introduce a simple family of growing small-world networks where both addition and deletion of edges are possible. By tuning the deletion probability qt , the model undergoes a transition from large worlds to small worlds. By making use of analytical or numerical means we determine the degree distribution, clustering coefficient and average path length of our networks. Surprisingly, we find that two similar evolving mechanisms, which provide identical degree distribution under a reciprocal scaling as t goes to infinity, can lead to quite different clustering behaviors and characteristic path lengths. It is also worth noting that Farey graphs constitute the extreme case qt ≡ 0 of our random construction. Keywords Degree distribution · Small world graph · Complex network
1 Introduction Over the past few years, there has been substantial research activity in the science of complex networks. It has been suggested that a host of real-world networks display a high degree of clustering, like grids and regular graphs, but small average path lengths, like random ones [1, 10, 18, 20]. Networks whose diameter grows logarithmically (or more slowly) with the number of nodes are often referred to as small-world networks [35]. In order to mimic complex real-life small-world networks, many models have been presented, among which the most well known successful attempts are the Watts-Strogatz (WS) rewiring model [36] and its variant Newman-Watts (NW) model [21]. Mathematically, a key observation is that structured graphs can have their diameter drastically reduced by the introduction of some random edges between the vertices. The pioneering studies have been followed by many others, and different mechanisms that producing small-world networks Y. Shang () Institute for Cyber Security, University of Texas at San Antonio, San Antonio, TX 78249, USA e-mail: [email protected]
506
Y. Shang
Fig. 1 A depiction of graphs Gt produced at iterations t = 0, 1, 2 and 3 with q1 = 1, q2 = 1/2 and q3 = 1/4. Removed edges are represented by dashed lines
have also been explored, see e.g. [2, 5–7, 11, 12, 16, 17, 30]. Unlike the WS and NW models, many real-world systems are evolving and have growing network structures [4, 20]. Modeling dynamic small-world networks has become a hot topic lately and we will briefly review some of the relevant work at the end of this section. In this paper, we present a dynamically growing small-world network model governed by a tunable probability sequence {qt }t≥1 associated with every (discrete) time step t . By varying qt the model undergoes an interesting phase tra
Data Loading...
