Augmented Graph Models for Small-World Analysis with Geographical Factors

Small-world properties, such as small-diameter and clustering, and the power-law property are widely recognized as common features of large-scale real-world networks. Recent studies also notice two important geographical factors which play a significant role, particularly in Internet related setting. These two are the distance-bias tendency (links tend to connect to closer nodes) and the property of bounded growth in localities. However, existing formal models for real-world complex networks usually don't fully consider these geographical factors. We describe a flexible approach using a standard augmented graph model (e.g. Watt and Strogatz's [33], and Kleinberg's [20] models) and present important initial results on a refined model where we focus on the small-diameter characteristic and the above two geographical factors. We start with a general model where an arbitrary initial node-weighted graph H is augmented with additional random links specified by a generic 'distribution rule' tau and the weights of nodes in H. We consider a reined setting where the initial graph H is associated with a growth-bounded metric, and tau has a distance-bias characteristic, specified by parameters as follows. The base graph H has neighborhood growth bounded from both below and above, specified by parameters beta(1) , beta(2) > 0. (These parameters can be thought of as the dimension of the graph, e.g. beta(1) = 2 and beta(2) = 3 for a graph modeling a setting with nodes in both 2D and 3D settings.) That 2(beta 1) <= N-u(2r)/N-u(r) <= 2(beta 2) where N-u (r) is the number of nodes v within metric distance r from u: d(u, v) <= r. When we add random links using distribution T, this distribution is specified by parameter a > 0 such that the probability that a link from u goes to v not equal u is alpha 1/d(alpha)(u,v) . We show which parameters produce a small-diameter graph and how the diameter changes depending on the relationship between the distance-bias parameter a and the two bounded growth parameters beta(1), beta(2) > 0. In particular, for most connected base graphs, the diameter of our augmented graph is logarithmic if alpha < beta(1), and poly-log if beta(2) < alpha < 2 beta(1), but polynomial if alpha > 2 beta(2). These results also suggest promising implications for applications in designing routing algorithms.