Power laws in software

ABSTRACT

A single statistical framework, comprising power law distributions and scale-free networks, seems to fit a wide variety of phenomena. There is evidence that power laws appear in software at the class and function level. We show that distributions with long, fat tails in software are much more pervasive than previously established, appearing at various levels of abstraction, in diverse systems and languages. The implications of this phenomenon cover various aspects of software engineering research and practice.

REFERENCES

• 1: Adamic, L. A. 2000. Zipf, power-laws, and Pareto—a ranking tutorial. http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html.
• 2: Adamic, L. A. and Huberman, B. A. 2002. Zipf's law and the internet. Glottometrics 3, 143--150.
• 3: Adams, E. N. 1984. Optimizing preventive service of software products. IBM J. Resear. Devel. 28, 1, 2--14.
• 4: Susanne Albers , Jeffery Westbrook, Self-Organizing Data Structures, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.13-51, January 1998
• 5: Albert, R., Jeong, H., and Barabási, A.-L. 1999. Diameter of the World-Wide Web. Nature 401, 130.
• 6: Albert, R., Jeong, H., and Barabási, A.-L. 2000. Error and attack tolerance of complex networks. Nature 406, 378--382.
• 7: Brian Allen , Ian Munro, Self-Organizing Binary Search Trees, Journal of the ACM (JACM), v.25 n.4, p.526-535, Oct. 1978 [doi>10.1145/322092.322094]
• 8: Barabási, A.-L. 2002. Linked: The New Science of Networks. Perseus Publishing, Cambridge, MA.
• 9: Barabási, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.
• 10: Barabási, A.-L., Albert, R., and Jeong, H. 1999. Mean-field theory for scale-free random networks. Physical A 272, 173--187.
• 11: Barabási, A.-L. and Bonabeau, E. 2003. Scale-free networks. Scientific Amer. 288, 5, 50--59.
• 12: Gareth Baxter , Marcus Frean , James Noble , Mark Rickerby , Hayden Smith , Matt Visser , Hayden Melton , Ewan Tempero, Understanding the shape of Java software, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 13: Jon L. Bentley , Catherine C. McGeoch, Amortized analyses of self-organizing sequential search heuristics, Communications of the ACM, v.28 n.4, p.404-411, April 1985 [doi>10.1145/3341.3349]
• 14: Barry Boehm , Victor R. Basili, Software Defect Reduction Top 10 List, Computer, v.34 n.1, p.135-137, January 2001 [doi>10.1109/2.962984]
• 15: Boehm, B. W. 1987. Industrial software metrics top 10 list. IEEE Softw. 4, 9, 84--85.
• 16: George Candea , Aaron B. Brown , Armando Fox , David Patterson, Recovery-Oriented Computing: Building Multitier Dependability, Computer, v.37 n.11, p.60-67, November 2004 [doi>10.1109/MC.2004.219]
• 17: Andy Chou , Junfeng Yang , Benjamin Chelf , Seth Hallem , Dawson Engler, An empirical study of operating systems errors, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 18: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 19: Peter J. Denning, The locality principle, Communications of the ACM, v.48 n.7, July 2005 [doi>10.1145/1070838.1070856]
• 20: S. N. Dorogovtsev , J. F. F. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Physics), Oxford University Press, Inc., New York, NY, 2003
• 21: Ebert, C. 2001. Metrics for indentifying critical components in software projects. In Handbook of Software Engineering and Knowledge Engineering, S. K. Chang, Ed. Vol. 1, Fundamentals. World Scientific, London, U.K.
• 22: Economides, N. 1996. The economics of networks. Int. J. Indust. Org. 16, 4, 673--699.
• 23: Albert Endres, An analysis of errors and their causes in system programs, ACM SIGPLAN Notices, v.10 n.6, p.327-336, June 1975
• 24: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 25: Feldman, S. I. 1979. Make—a program for maintaining computer programs. Softw. Prac. Exper. 9, 4, 255--265.
• 26: Feller, W. 1971. An Introduction to Probability Theory and Its Applications 2nd ed. Vol. 2. John Wiley & Sons, New York, NY.
• 27: Norman E. Fenton , Niclas Ohlsson, Quantitative Analysis of Faults and Failures in a Complex Software System, IEEE Transactions on Software Engineering, v.26 n.8, p.797-814, August 2000 [doi>10.1109/32.879815]
• 28: Refactoring: improving the design of existing code, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 29: Fox Keller, E. 2005. Revisiting “scale-free” networks. BioEssays 27, 10, 1060--1068.
• 30: Robert L. Glass, Reuse: What's Wrong with This Picture?, IEEE Software, v.15 n.2, p.57-59, March 1998 [doi>10.1109/52.663785]
• 31: Heising, W. P. 1963. Note on random addressing techniques. IBM Syst. J. 2, 2, 112--116.
• 32: S. Henry , D. Kafura, Software Structure Metrics Based on Information Flow, IEEE Transactions on Software Engineering, v.7 n.5, p.510-518, September 1981 [doi>10.1109/TSE.1981.231113]
• 33: Huberman, B. A. and Adamic, L. A. 1999. Growth dynamics of the World-Wide Web. Nature 401, 131.
• 34: Donald E. Knuth, The TeXbook, Addison-Wesley Professional, 1986
• 35: Donald E. Knuth, Literate programming, The Computer Journal, v.27 n.2, p.97-111, May 1984 [doi>10.1093/comjnl/27.2.97]
• 36: Knuth, D. E. 1986a. T_eX: The Program. Computers & Typesetting, vol. B. Addison Wesley Publishing Company, Reading, MA.
• 37: Donald Ervin Knuth, The METAFONTbook, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 38: Donald Ervin Knuth, Metafont: The Program, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 39: D. E. Knuth, The errors of TEX, Software—Practice & Experience, v.19 n.7, p.607-685, July 1989 [doi>10.1002/spe.4380190702]
• 40: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 41: Laherrère, J. and Sornette, D. 1998. Stretched exponential distributions in nature and economy: “fat tails with characteristic scales.” Europ. Phys. J. B 2, 525--539.
• 42: John Lakos, Large-scale C++ software design, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 43: Grant Larsen, Component-based enterprise frameworks, Communications of the ACM, v.43 n.10, p.24-26, Oct. 2000 [doi>10.1145/352183.352196]
• 44: Li, W. 1992. Random texts exhibit zipf's-law-like word frequency distribution. IEEE Trans. Inform. Theory 38, 6, 1841--1845.
• 45: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 46: Mandelbrot, B. 1953. An informational theory of the statistical structure of language. In Proceedings of the 2nd London Symposiumon Communication Theory, W. Jackson, Ed. Butterworth, London, 486--504.
• 47: Mandelbrot, B. M. 1951a. Adaptation du message á la ligne de transmission: I. Quanta d' information. Comptes Rendus des séances de l' Academie des Sciences 232, 1636--1740.
• 48: Mandelbrot, B. M. 1951b. Adaptation du message á la ligne de transmission: II. Interprétation physiques. Comptes Rendus des séances de l' Academie des Sciences 232, 2003--2005.
• 49: Mandelbrot, B. M. 1983. The Fractal Geometry of Nature. W. H. Freeman and Company, New York, NY.
• 50: Marchesi, M., Pinna, S., Serra, N., and Tuveri, S. 2004. Power laws in Smalltalk. In Proceedings of the 12th European Smalltalk User Group Joint Event. Köthen, Germany.
• 51: Robert Cecil Martin, Agile Software Development: Principles, Patterns, and Practices, Prentice Hall PTR, Upper Saddle River, NJ, 2003
• 52: Mitzenmacher, M. 2004. A brief history of generative models for power law and lognormal distributions. Internet Mathematics 1, 2, 226--251.
• 53: Möller, K.-H. 1993. An empirical investigation of software fault distribution. In Proceedings of the 1st International Metrics Symposium. IEEE Computer Society Press, Los Alamitos, CA, 82--90.
• 54: Myers, C. R. 2003. Software systems as complex networks: structure, function, and evolvability of software collaboration graphs. Phys. Rev. E 68, 046116.
• 55: Newman, M. E. J. 2005. Power laws, pareto distributions and zipf's law. Contem. Phys. 46, 5, 232--351.
• 56: Niclas Ohlsson , Hans Alberg, Predicting Fault-Prone Software Modules in Telephone Switches, IEEE Transactions on Software Engineering, v.22 n.12, p.886-894, December 1996 [doi>10.1109/32.553637]
• 57: Thomas J. Ostrand , Elaine J. Weyuker, The distribution of faults in a large industrial software system, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 58: Pareto, V. 1897. Cours d' Économie Politique. Rouge, Lausanne.
• 59: Alex Potanin , James Noble , Marcus Frean , Robert Biddle, Scale-free geometry in OO programs, Communications of the ACM, v.48 n.5, p.99-103, May 2005 [doi>10.1145/1060710.1060716]
• 60: Eugene S. Schwartz, A Dictionary for Minimum Redundancy Encoding, Journal of the ACM (JACM), v.10 n.4, p.413-439, Oct. 1963 [doi>10.1145/321186.321187]
• 61: Shiode, N. and Batty, M. 2000. Power law distributions in real and virtual worlds. In Proceedings of the 10th Annual Internet Society Conference (INET'00). Yokohama.
• 62: Forrest Shull , Vic Basili , Barry Boehm , ,A. Winsor Brown , Patricia Costa , Mikael Lindvall , Dan Port , Ioana Rus , Roseanne Tesoriero , Marvin Zelkowitz, What We Have Learned About Fighting Defects, Proceedings of the 8th International Symposium on Software Metrics, p.249, June 04-07, 2002
• 63: Simon, H. A. 1955. On a class of skew distribution functions. Biometrika 42, 3/4, 425--440.
• 64: Diomidis Spinellis , Clemens Szyperski, Guest Editors' Introduction: How Is Open Source Affecting Software Development?, IEEE Software, v.21 n.1, p.28-33, January 2004 [doi>10.1109/MS.2004.1259204]
• 65: Clemens Szyperski, Component Software: Beyond Object-Oriented Programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 66: TIS Committee. 1995. Tool Interface Standard (TIS) Executable and Linking Format (ELF) Specification. Version 1.2.
• 67: Valverde, S., Cancho, R. F., and Solé, R. V. 2002. Scale-free networks from optimal design. Europhysics Lett. 60, 4, 512--517.
• 68: Valverde, S. and Solé, R. V. 2003. Hierarchical small worlds in software architecture. Working Paper 03-07-044, Santa Fe Institute, Santa Fe, NM.
• 69: Venkatasubramanian, V., Katare, S., Patkar, P. R., and Mu, F.-P. 2004. Spontaneous emergence of complex optimal networks through evolutionary adaptation. Comput. Chem. Engin. 28, 9, 1789--1798.
• 70: Steven Weber, The Success of Open Source, Harvard University Press, Cambridge, MA, 2004
• 71: Leonard H. Weiner, The roots of structured programming, ACM SIGCSE Bulletin, v.10 n.1, February 1978
• 72: Wheeldon, R. and Counsell, S. 2003. Power law distributions in class relationships. In Proceedings of the 3rd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM'03). IEEE Computer Society Press, Los Alamitos, CA, 45--54.
• 73: Yule, G. U. 1925. A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, F.R.S. Philoso. Transa. Royal Soc. London: Series B 213, 21--87.
• 74: Zipf, G. K. 1935. The Psycho-Biology of Language: An Introduction to Dynamic Philology. Houghton Mifflin, Boston, MA.
• 75: Zipf, G. K. 1949. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley, Reading, MA.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
        D.2.13 Reusable Software
            Subjects: Reuse models; Reusable libraries
      D.2.8 Metrics
          Subjects: Product metrics
      D.2.9 Management
          Subjects: Software quality assurance (SQA)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Languages, Measurement

Keywords:
Scale-free networks, power laws