Scale-free networks from optimal design

By Sergi Valverde, Ramon Ferrer Cancho, R. Solé. 2002

356 citations recorded by the source corpus.

A large number of complex networks, both natural and artificial, share the presence of highly heterogeneous, scale-free degree distributions. A few mechanisms for the emergence of such patterns have been suggested, optimization not being one of them. In this letter we present the first evidence for the emergence of scaling (and the presence of small-world behavior) in software architecture graphs from a well-defined local optimization process. Although the rules that define the strategies involved in software engineering should lead to a tree-like structure, the final net is scale-free, perhaps reflecting the presence of conflicting constraints unavoidable in a multidimensional optimization process. The consequences for other complex networks are outlined.

Subfields: Computer Networks and Communications, Condensed Matter Physics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/e4fff8352cdf8ba9f552e24250c8989f9c5bebef

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Condensed Matter Physics

In Statistical and Nonlinear Physics

Citations in the corpus

Trees, networks, and hydrology (2006, methodology): “Loops complicate the general picture, but the suggestion that an optimal balance of directedness (i.e., network diameter) and connectivity may, indeed, yield to optimal scale-free constructions is rather revealing [Valverde et al., 2002].”
Link Prediction in Complex Networks: A Survey (2010, background): “Taking the power-law degree distribution as an instance, the well-known mechanisms include rich gets richer [45], good gets richer [140], optimal design [141], Hamiltonian dynamics [142], merging and regeneration [143], stability constraints [144], and so on.”
Network ‘Small-World-Ness’: A Quantitative Method for Determining Canonical Network Equivalence (2008, neutral): “73 n/a [1,55]”
Selection, Tinkering, and Emergence in Complex Networks - Crossing the Land of Tinkering (2002, background): “The scale-free distributions observed in both natural and artiﬂcial graphs suggests that the homeostasis won by the second might well be a result of exploiting the SF topology resulting from optimization (Valverde et al. , 2002).”
Information Theory of Complex Networks: On Evolution and Architectural Constraints (2004, methodology): “This might be a signature of frustrated optimization in software design processes [10].”
Spatial Networks (2010, background): “It has been shown, for example, that optimization of both the average shortest path and the total length can lead to small-world networks [226], and more generally, degree correlations [48] or scale-free features [302] can emerge from an optimization process.”
The Structure and Function of Complex Networks (2003, neutral): “See, for instance, [29, 156, 166, 394, 416, 417].”
Analyzing and modeling real-world phenomena with complex networks: a survey of applications (2007, methodology): “The sub-area of software engineering is aimed at prov iding methodologies and tools for designing and building software efficiently, which can be ac hieved by decomposing a problem into many small, distinct but interlocking pieces, named softwa re components [187, 188].”
Complex networks: small-world, scale-free and beyond (2003, neutral): “E-mail [15] 56969 0.03 4.95 1.81 Software [ 16 ] 1376 0.06 6.39 2.5”