Signatures of small-world and scale-free properties in large computer programs

Abstract

A large computer program is typically divided into many hundreds or even thousands of smaller units, whose logical connections define a network in a natural way. This network reflects the internal structure of the program, and defines the ``information flow'' within the program. We show that, (1) due to its growth in time this network displays a scale-free feature in that the probability of the number of links at a node obeys a power-law distribution, and (2) as a result of performance optimization of the program the network has a small-world structure. We believe that these features are generic for large computer programs. Our work extends the previous studies on growing networks, which have mostly been for physical networks, to the domain of computer software.

arXiv comment4 pages, 1 figure, to appear in Phys. Rev. E

References in corpus (18)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Error and attack tolerance of complex networks
• The diameter of the world wide web
• Random graphs with arbitrary degree distributions and their applications
• Who is the best connected scientist? A study of scientific coauthorship networks
• Mean-field theory for scale-free random networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model
• Topology of evolving networks: local events and universality
• Connectivity of Growing Random Networks
• Organization of Growing Random Networks
• Bose-Einstein condensation in complex networks
• Degree Distributions of Growing Networks
• Topology of the conceptual network of language
• Scaling properties of scale-free evolving networks: Continuous approach
• Effect of the accelerating growth of communications networks on their structure
• Dynamics of directed graphs: the world-wide Web

Cited by in corpus (7)

• Analyzing and Modeling Real-World Phenomena with Complex Networks: A Survey of Applications
• Probing the topological properties of complex networks modeling short written texts
• Inter-Package Dependency Networks in Open-Source Software
• Bug propagation and debugging in asymmetric software structures
• Redefining measures of Layered Architecture
• Complex Dependencies in Large Software Systems
• Properties of dense partially random graphs