Generating Mechanisms for Evolving Software Mirror Graph

Ling-Zan Zhu, Bei-Bei Yin, Kai-Yuan Cai

Department of Automatic Control, Beijing University of Aeronautics and Astronautics, Beijing 100191, China.
Institute of Chemical Defense, PLA, Beijing 102205, China.

DOI: 10.4236/jmp.2012.39139                

Abstract

Following the growing research interests in complex networks, in recent years many researchers treated static structures of software as complex networks and revealed that most of these networks demonstrate small-world effect and follow scale-free degree distribution. Different from the perspectives adopted in these works, our previous work proposed software mirror graph to model the dynamic execution processes of software and revealed software mirror graph may also be small world and scale-free. To explain how the software mirror graph evolves into a small world and scale free structure, in this paper we further proposed a mathematical model based on the mechanisms of growth, preferential attachment, and walking. This model captures some of the features of the software mirror graph, and the simulation results show that it can generate a network having similar properties to the software mirror graph. The implications are also discussed in this paper.

Keywords

Software Mirror Graph; Complex Network; Scale-Free; Small World

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. de Moura, Y.-C. Lai and A. Motter, “Signatures of Small-World and Scale-Free Properties in Large Computer Programs,” Physical Reviews E, Vol. 68, 2003.
[2]	S. Valverde, R. Ferrer-Cancho and R. Sole, “Hierarchical Small Worlds in Software Architecture,” Santa Fe Institute Working Papers, SFI/03-07-044, 2003.
[3]	A. Gorshenev and Y. Pis’mak, “Punctuated Equilibrium in Software Evolution,” Physical Reviews E, Vol. 70, 2004.
[4]	A. Potanin, J. Noble, M. Frean and R. Biddle, “Scale-Free Geometry in Object-Oriented Programs,” Communication of the ACM, Vol. 48, No. 5, 2005, pp. 99-103. doi:10.1145/1060710.1060716
[5]	S. Jenkins and S. R. Kirk, “Software Architecture Graphs as Complex Networks: A Novel Partitioning Scheme to Measure Stability and Evolution,” Information Sciences, Vol. 177, No. 5, 2007, pp. 2587-2601. doi:10.1016/j.ins.2007.01.021
[6]	G. Concas, M. Marchesi, S. Pinna and N. Serra, “Power-Laws in a Large Object-Oriented Software System,” IEEE Transactions on Software Engineering, Vol. 33, No. 10, 2007, pp. 687-707. doi:10.1109/TSE.2007.1019
[7]	P. Louridas, D. Spinellis and V. Vlachos, “Power Laws in Software”, ACM Transactions on Software Engineering and Methodology, Vol. 18, No. 1, 2008, pp. 1-26. doi:10.1145/1391984.1391986
[8]	L. Hatton, “Power-law Distributions of Component Size in General Software Systems”, IEEE Transactions on Software Engineering, Vol. 35, No. 4, 2009, pp. 566-572. doi:10.1109/TSE.2008.105
[9]	M. E. J. Newman, “The Structure and Function of Complex Networks,” SIAM Review, Vol. 45, No. 2, 2003, pp. 167-256. doi:10.1137/S003614450342480
[10]	K. Y. Cai and B. B. Yin, “Software Execution Processes as an Evolving Complex Network”, Information Sciences, Vol. 179, No. 12, 2009, pp. 1903-1928. doi:10.1016/j.ins.2009.01.011
[11]	D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, Vol. 393, 1998, pp. 440-442. doi:10.1038/30918
[12]	A.-L. Barabási and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, No. 5439, 1999, pp. 509-512. doi:10.1126/science.286.5439.509
[13]	S. Valverde, R. Ferror Cancho and R. V. Sole, “Scale-Free Networks from Optimal Design,” cond-mat/0204344, April 2002.
[14]	C. Myers, “Software Systems as Complex Networks: Structure, Function, and Evolvability of Software Collaboration Graphs,” Physical Reviews E, Vol. 68, 2003.
[15]	S. Valverde and R. Sole, “Network Motifs in Computational Graphs: A Case Study in Software Architecture,” Physical Review E, Vol. 72, No. 2, 2005, p. 026107.
[16]	K. He, R. Peng, J. Liu, F. He, et al., “Design Methodology of Networked Software Evolution Growth Based on Software Patterns,” Journal of System Science and Complexity, Vol. 19, No. 2, 2006, pp. 157-181. doi:10.1007/s11424-006-0157-6