Applying Complex Network Theory to Software Structure Analysis

Authors: Weifeng Pan

Abstract:

Complex networks have been intensively studied across many fields, especially in Internet technology, biological engineering, and nonlinear science. Software is built up out of many interacting components at various levels of granularity, such as functions, classes, and packages, representing another important class of complex networks. It can also be studied using complex network theory. Over the last decade, many papers on the interdisciplinary research between software engineering and complex networks have been published. It provides a different dimension to our understanding of software and also is very useful for the design and development of software systems. This paper will explore how to use the complex network theory to analyze software structure, and briefly review the main advances in corresponding aspects.

Keywords: Metrics, measurement, complex networks, software.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332884

References:

[1] W. Pan, Software Networks-Based Analysis of Software Static Structure and Its Applications. Wuhan: Wuhan University, 2011.
[2] W. Pan, B. Li, Y. Ma, Y. Qin, and X. Zhou, "Measuring Structural Quality of Object-Oriented Softwares via Bug Propagation Analysis on Weighted Software Networks", Journal of Computer Science and Technology, vol. 25, no. 6, pp. 1202-1213, 2010.
[3] L. Costa, O. Oliveria, and G. Travieso, "Analyzing and Modeling Real- World Phenomena with Complex Networks: a Survey of Applications", arXiv:0711.3199v2, 2008.
[4] J. L¨u and G. Chen, "Analysis, Control and Application of Complex Networks: a Brief Overview", Pro. of the 2009 IEEE International Symposium on Circuits and Systems, pp. 1601-1604, 2009.
[5] J. L¨u and D. Liu, "A Brief Overview of the Complex Biological and Engineering Networks", Pro. of the 2007 IEEE International Symposium on Circuits and Systems, pp. 2634-2637, 2007.
[6] W. Pan, B. Li, Y. Ma, and Jing Liu, "Multi-Granularity Evolution Analysis of Software using Complex Network Theory", Journal of Systems Science and Complexity, vol. 24, pp. 1-15, 2011.
[7] W. Pan, B. Li, Y. Ma, J. Liu, and Y. Qin, "Class Structure Refactoring of Object-Oriented Softwares using Coommunity Detection in Dependency Networks", Frontiers of Computer Science in China, vol. 3, no. 3, pp. 396-404, 2009,
[8] R. W. Wolverton, "The Cost of Developing Large-Scale Software", IEEE Transactions on Computers, vol. C-23, no. 6, pp. 615-636.
[9] T. J. McCabe, "A Complexity Measure", IEEE Transactions on Software Engineering, vol. SE-2, no. 4, pp. 308-320, 1976.
[10] M. H. Halstead, "Elements of Software Science", Operating, and Programming Systems, vol. 7, pp. 128, 1977.
[11] B. H. Yin and J. W. Winchester, "The Establishment and Use of Measures to Evaluate the Quality of Software Designs", Software quality assurance workshop on Functional and performance, pp. 45-52, 1978.
[12] C. L. McClure, "A Model for Program Complexity Analysis", Proc. of the 3rd International Conference on Software Engineering, pp. 149-157, 1978.
[13] N. Woodfield, "Enhanced Effort Estimation by Extending Basic Programming Models to Include Modularity Factors", West-Lafayette, USA, 1980.
[14] S. Henry and D. Kafura, "Software Structure Metrics Based on Information Flow", IEEE Transactions on Software Engineering, pp. 510-518, 1981.
[15] K. C. Tai, "A Program Complexity metric based on Data Flow Information in Control Graphs", Proc. of the 7th International Conference on Software Engineering, pp. 239-248, 1984.
[16] B. F. Abreu and R. Carapuca, "Candidate Metrics for Object-Oriented Software within a Taxonomy Framework", Journal of systems software, vol. 26, no. 1, pp. 87-96, 1994.
[17] S. R. Chidamber and C. F. Kemerer, "A Metrics Suite for Object- Oriented Design", IEEE Transactions on Software Engineering, vol. 20, no. 6, pp. 476-493, 1994.
[18] W. Li and S. Henry, "Object-Oriented Metrics that Predict Maintainability", Journal Of Systems And Software, vol. 23, no. 2, pp. 111-122, 1993.
[19] F. B. Abreu, "The MOOD Metrics Set", Proc. of the ECOOP95 Workshop on Metrics, 1995.
[20] F. B. Abreu, "Design Metrics for OO Software System", Proc. of the ECOOP95 Quantitative Methods Workshop, 1995.
[21] M. Lorenz and J. Kidd, Object-Oriented Software Metrics: a Practical Guide. NJ: Prentice Hall PTR, 1994.
[22] R. Subramanyan and M. S. Krishnan, "Empirical Analysis of CK Metrics for Object-Oriented Design Complexity: Implications for Software Defects", IEEE Transactions on Software Engineering, vol. 29, no. 10, pp. 297-310, 2003.
[23] V. R. Basili, L. C. Briand, and W. L. Melo, "A Validation of Object- Oriented Design Metrics as Quality Indicators", IEEE Transactions on Software Engineering, vol. 22, no. 10, pp. 751-761, 1996.
[24] K. EI Emam, S. Benlarbi, N. Goel, "The Confounding Effect of Class Size on the Validity of Object-Oriented Metrics", IEEE Transactions on Software Engineering, vol. 27, no. 6, pp. 630-650, 2001.
[25] T. Gyim'othy, R. Ferenc, and I. Siket, "Empirical Validation of Object- Oriented Metrics on Open Source Software for Fault Prediction", IEEE Transactions on Software Engineering, vol. 31, no. 10, pp. 897-910, 2003.
[26] B. Zhang, "Network and Complex Systems", Scientific Chinese, vol. 10, pp. 37-37, 2004.
[27] G. Chen, "Introduction to Complex Networks and Their Recent Advances", Advances in Mechanics, vol. 38, no. 6, pp. 653-662, 2008.
[28] D. J. Watts and S. H. Strogatz, "Collective Dynamics of Small World Networks", Nature, vol. 393, pp. 440-442, 1998.
[29] A. L. Barab'asi and R. Albert, "Emergence of Scaling in Random Networks", Science, vol. 286, pp. 509-512, 1999.
[30] Committee on Network Science for Future Army Application, Network Science, Washington DC: National Academies Press, 2006.
[31] A. L. Barab'asi, Linked: the New Science of Networks, Cambridge MA: Perseus Publishing, 2002.
[32] D. J. Watts, "The "new" Science of Networks", Annual Review of Sociology, vol, 30, pp. 243-270, 2004.
[33] M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law Relationships of The Internet Topology", Computer Communication Review, vol. 29, no. 4, pp. 251- 262, 1999.
[34] G. Siganos, M. Faloutsos, P. Faloutsos, et al., "Power Laws and The AS-Level Internet Topology", IEEE/ACM Transactions on Networking, vol. 11, no. 4, pp. 514-524, 2003.
[35] L. A. Adamic and B. A. Huberman, "Power-Law Distribution of The World Wide Web", Science, vol. 287, pp. 2115a, 2000.
[36] R. Guimer`a, S. Mossa, A. Turtschi, et al., "The Worldwide Air Transportation Network: Anomalous Centrality, Community Structure, and Cities- Global Roles", Proceedings of the National Academy of Science USA, vol. 102, pp. 3394-7799, 2005.
[37] W. Li and X. Cai, "Statistical Analysis of Airport Network of China", Physical Review E, vol. 68, no. 4: 46106, 2004, .
[38] O. Sporns, "Network Analysis, Complexity, and Brain Function", Complexity, vol. 8, no. 1, pp. 56-60, 2002.
[39] H. Jeong, B. Tombor, R. Albert, et al., "The Large-Scale Organizationn of Metabolic Networks", Nature, vol. 407, pp. 651-654, 2000.
[40] M. E. J. Newman, "Scientific Collaboration Networks. I. Network Construction and Fundamental Results", Physical Review E, vol. 64, no. 1, pp. 16131, 2001.
[41] M. A. Serrano and M. Bogu˜n'a, "Topology of The World Trade Web", Physical Review E, vol. 68, pp. 015101, 2003.
[42] A. E. Motter, A. P. S. Moura, Y. C. Lai, et al., "Topology of The Conceptual Network of Language", Physical Review E, vol. 65, pp. 065102, 2002.
[43] G. Corso, "Families and Clustering in a Natural Numbers Network", Physical Review E, vol. 60, no. 3, pp. 036106-036110, 2004.
[44] X. Liu, C. K. Tse, and M. Small, "Complex Network Structure of Musical Compositions: Algorithmic Generation of Appealing Music", Physica A, vol. 389, no. 1, pp. 126-132, 2010.
[45] S. Abe and N. Suzuki, "Scale-Free Network of Earthquakes", Europhysics Letters, vol. 65, no. 4, pp. 581-586, 2004.
[46] S. Valverde, R. F. i Cancho, and R. Sole, "Scale Free Networks from Optimal Design", Europhysics Letters, vo. 60, pp. 512-517, 2002.
[47] C. R. Myers, "Software Systems as Complex Networks: Structure, Function, and Evolvability of Software Collaboration Graphs, Physical Review E, vol. 68, 2003.
[48] S. Valverde and R. Sol'e, "Hierarchical Small Worlds in Software Architecture", Working Paper of Santa Fe Institue, SFI/03-07-44, 2003.
[49] A. P. S. Moura, Y. C. Lai, and A. E. Motter, "Signatures of Small-World and Scale-Free Properties in Large Computer Programs", Physical Review E, vol. 68, pp. 017102, 2003.
[50] N. LaBelle and E. Wallingford, "Inter-Package Dependency Networks in Open-Source Software", ArXiv: Cs.SE/0411096, 2004.
[51] S. Valverde and R. V. Sole, "Universal Properties of Bipartite Software Graphs", Proc. of the 9th IEEE International Conference on Engineering of Complex Computer Systems, 2004.
[52] M. Han, D. Li, C. Liu, et al. "Networked Characteristics in Software and its Contribution to Software Quality", Computer Engineering and Application, vol. 42, no. 20, pp. 29-31, 2006. (in Chinese)
[53] J. Liu, K. He, Y. Ma, et al., "Scale Free in Software Metrics", Proc. of the 30th Annual International Computer Software and Application Conference, pp. 229-235, 2004.
[54] J. Liu, K. He, R. Peng, et al., "A Study on the Weight and Topology Correlation of Object-Oriented Software Coupling Network", Proc. of the 1st International Conference on Complex Systems and Applications, PP. 955-959, 2006.
[55] D. Yan, G. QI, "The Scale-free Feature and Evolving Model of Large- Scale Software systems", Acta Phisica Sinica, vol. 55, no. 8, pp. 3799- 3084, 2006.
[56] H. Zhang, H. Zhao, W. Cai, et al., "Using the k-core Decomposition to Analyze the Static Structure of Large-Scale Software Systems", The Journal of Supercomputing, vol. 53, no. 2, pp. 352-369, 2010.
[57] S. Jenkins and S. R. Kirk, "Software Architecture Graphs as Complex Networks: a Novel Parttion Scheme to Measure Stability and Evolution", Information Sciences, vol. 177, no. 12, pp. 2587-2601, 2007.
[58] M. Shi, X. Li, and X. Wang, "Evolving Topology of Java Networks", Proc. of the 6th World Congress on Control and Automation, PP. 21-23, 2006.
[59] L. Wang, Z. Wang, C. Yang, et al., "Linux Kernels as Complex Networks: a Novel Method to Study Evolution", Proc. of the 25th International Conference on Software Maintenance, PP. 41-50, 2009.
[60] H. Li, B. Huang, and J. Lu, "Dynamical Evolution Analysis of the Object-Oriented Software Systems", Proc. of the 2008 IEEE World Congress on Computational Intelligence, PP. 3035-3040, 2008.
[61] R. V. Sole and S. Valverde, "Information Theory of Complex Networks: on Evolution and Architectural Constraints", Proc. of the International Conference on Complex Networks, pp. 189-207, 2004.
[62] S. Valverde and R. V. Sole, "Network Motifs in Computational Graphs: a Case Study in Software Architecture", Physical Review E, vol. 72, pp. 026107, 2005.
[63] K. He, R. Peng, J. Liu, et al., "Network Motifs in Computational Graphs: a Case Study in Software Architecture", Journal of Systems Science and Complexity, vol. 19, no. 2, pp. 157-181, 2006.
[64] B. Li, H. Wang, Z. Li, et al., "Software Complexity Metrics Based on Complex Networks", Acta Electronica Sinica, vol. 34, no. 12A, pp. 2371- 2375, 2006. (in Chinese).
[65] H. Li, "Scale-Free Network Models with Accelerating Growth", Frontier of Computer Science in China, vol. 3, no. 3, pp. 373-380, 2009.
[66] W. Pan, B. Li, Y. Ma, and J. Liu, "A Novel Software Evolution Model Based on Software Networks", Complex (2), 1281-1291, 2009.
[67] R. Vasa, J. G. Schneider, C. Woodward, et al., Detecting Structural Changes in Object Oriented Software Systems, Proc. of the International Symposium on Empirical Software Engineering, PP. 479-486, 2005.
[68] Y. Ma, K. He, and D. Du, "A Qualitative Method for Measuring the Structural Complexity of Software Systems based on Complex Networks", Proc. of the 12th Asia-Pacific Software Engineering Conference, PP. 257-263, 2005.
[69] A. Girolamo, L. I. Newman, and R. Rao, "The Structure and Behavior of Class Networks in Object-Oriented Software Design", www.eecs.umich.edu/ leenewm/ documents/classnetworks.pdf, 2005.
[70] Y. Ma, K. He, D. Du, et al., "A Complexity Metrics Set for Large- Scale Object-Oriented Software Systems", Proc. of the 6th International Conference on Computer and Information Technology, PP. 257-263, 2006.
[71] R. Vasa, J. G. Schneider, and O. Nierstrasz, "The Inevitable Stability of Software Change", Proc. of the 23nd IEEE International Conference on Software Maintenance, Paris France, PP. 4-13, 2007.
[72] H. Melton and E. Tempero, "Static Members and Cycles in Java Software", Proc. of the 1st International Symposium on Empirical Software Engineering and Measurement, PP. 136-145, 2007.
[73] Y. Ma, K. He, and J. Liu, "Network Motifs in Object-Oriented Software Systems", Dynamics of Continuous, Discrete and Impulsive System (Series B: Applications and Algorithms) Special Issue on Software Engineering and Complex Networks, vol. 16, no. S6, pp. 166-172, 2007.