Abstract:
The small-world phenomenon has been already the subject of a huge variety of papers, showing its appeareance in a variety of systems. However, some big holes still remain to be filled, as the commonly adopted mathematical formulation suffers from a variety of limitations, that make it unsuitable to provide a general tool of analysis for real networks, and not just for mathematical (topological) abstractions. In this paper we show where the major problems arise, and how there is therefore the need for a new reformulation of the small-world concept. Together with an analysis of the variables involved, we then propose a new theory of small-world networks based on two leading concepts: efficiency and cost. Efficiency measures how well information propagates over the network, and cost measures how expensive it is to build a network. The combination of these factors leads us to introduce the concept of {\em economic small worlds}, that formalizes the idea of networks that are "cheap" to build, and nevertheless efficient in propagating information, both at global and local scale. This new concept is shown to overcome all the limitations proper of the so-far commonly adopted formulation, and to provide an adequate tool to quantitatively analyze the behaviour of complex networks in the real world. Various complex systems are analyzed, ranging from the realm of neural networks, to social sciences, to communication and transportation networks. In each case, economic small worlds are found. Moreover, using the economic small-world framework, the construction principles of these networks can be quantitatively analyzed and compared, giving good insights on how efficiency and economy principles combine up to shape all these systems.

Abstract:
Small-world networks are the focus of recent interest because they appear to circumvent many of the limitations of either random networks or regular lattices as frameworks for the study of interaction networks of complex systems. Here, we report an empirical study of the statistical properties of a variety of diverse real-world networks. We present evidence of the occurrence of three classes of small-world networks: (a) scale-free networks, characterized by a vertex connectivity distribution that decays as a power law; (b) broad-scale networks, characterized by a connectivity distribution that has a power-law regime followed by a sharp cut-off; (c) single-scale networks, characterized by a connectivity distribution with a fast decaying tail. Moreover, we note for the classes of broad-scale and single-scale networks that there are constraints limiting the addition of new links. Our results suggest that the nature of such constraints may be the controlling factor for the emergence of different classes of networks.

Abstract:
We report numerical evidence that an epidemic-like model, which can be interpreted as the propagation of a rumor, exhibits critical behavior at a finite randomness of the underlying small-world network. The transition occurs between a regime where the rumor "dies" in a small neighborhood of its origin, and a regime where it spreads over a finite fraction of the whole population. Critical exponents are evaluated, and the dependence of the critical randomness with the network connectivity is studied. The behavior of this system as a function of the small-network randomness bears noticeable similarities with an epidemiological model reported recently [M. Kuperman and G. Abramson, Phys. Rev. Lett. 86, 2909 (2001)], in spite of substantial differences in the respective dynamical rules.

Abstract:
We investigate the role of clustering on the critical behavior of the contact process (CP) on small-world networks using the Watts-Strogatz (WS) network model with an edge rewiring probability p. The critical point is well predicted by a homogeneous cluster-approximation for the limit of vanishing clustering (p close to 1). The critical exponents and dimensionless moment ratios of the CP are in agreement with those predicted by the mean-field theory for any p > 0. This independence on the network clustering shows that the small-world property is a sufficient condition for the mean-field theory to correctly predict the universality of the model. Moreover, we compare the CP dynamics on WS networks with rewiring probability p = 1 and random regular networks and show that the weak heterogeneity of the WS network slightly changes the critical point but does not alter other critical quantities of the model.

Abstract:
In the context of growing networks, we introduce a simple dynamical model that unifies the generic features of real networks: scale-free distribution of degree and the small world effect. While the average shortest path length increases logartihmically as in random networks, the clustering coefficient assumes a large value independent of system size. We derive expressions for the clustering coefficient in two limiting cases: random (C ~ (ln N)^2 / N) and highly clustered (C = 5/6) scale-free networks.

Abstract:
The critical behavior of the XY model on small-world network is investigated by means of dynamic Monte Carlo simulations. We use the short-time relaxation scheme, i.e., the critical behavior is studied from the nonequilibrium relaxation to equilibrium. Static and dynamic critical exponents are extracted through the use of the dynamic finite-size scaling analysis. It is concluded that the dynamic universality class at the transition is of the mean-field nature. We also confirm numerically that the value of dynamic critical exponent is independent of the rewiring probability P for P > 0.03.

Abstract:
We evolve topology of a network of N fully-coupled nodes that interact according to repulsion-attractiondynamics within a confining wall. The dynamics portrays each node’s tendency to keep distance from itscompetitors while maintaining a lighter tendency to resist relative isolation. Each node is characterizedby two parameters: an intrinsic mobility μ and a preferred neighboring distance ρ. Onset of clustering isfound 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 ofnode population.

Abstract:
We analyze critical phenomena on networks generated as the union of hidden variables models (networks with any desired degree sequence) with arbitrary graphs. The resulting networks are general small-worlds similar to those a` la Watts and Strogatz but with a heterogeneous degree distribution. We prove that the critical behavior (thermal or percolative) remains completely unchanged by the presence of finite loops (or finite clustering). Then, we show that, in large but finite networks, correlations of two given spins may be strong, i.e., approximately power law like, at any temperature. Quite interestingly, if $\gamma$ is the exponent for the power law distribution of the vertex degree, for $\gamma\leq 3$ and with or without short-range couplings, such strong correlations persist even in the thermodynamic limit, contradicting the common opinion that in mean-field models correlations always disappear in this limit. Finally, we provide the optimal choice of rewiring under which percolation phenomena in the rewired network are best performed; a natural criterion to reach best communication features, at least in non congested regimes.

Abstract:
Query processing is one of the most important technologies in sensor networks. To reduce energy consumption of query, a small world based query strategy named Contact-Assisted poweR-efficient Direction-sense-achieved query strategy for Sensor Networks (CardSN) was presented. In CardSN, Contacts act as shortcuts to bring down the average path length of the network; a distributed relative localization algorithm was introduced to achieve a sense of direction. Experimental results show that CardSN has good scal...

Abstract:
Small-world networks by Watts and Strogatz are a class of networks that are highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. These characteristics result in networks with unique properties of regional specialization with efficient information transfer. Social networks are intuitive examples of this organization with cliques or clusters of friends being interconnected, but each person is really only 5-6 people away from anyone else. While this qualitative definition has prevailed in network science theory, in application, the standard quantitative application is to compare path length (a surrogate measure of distributed processing) and clustering (a surrogate measure of regional specialization) to an equivalent random network. It is demonstrated here that comparing network clustering to that of a random network can result in aberrant findings and networks once thought to exhibit small-world properties may not. We propose a new small-world metric, {\omega} (omega), which compares network clustering to an equivalent lattice network and path length to a random network, as Watts and Strogatz originally described. Example networks are presented that would be interpreted as small-world when clustering is compared to a random network but are not small-world according to {\omega}. These findings have significant implications in network science as small-world networks have unique topological properties, and it is critical to accurately distinguish them from networks without simultaneous high clustering and low path length.