Research On MapReduce-based Algorithm For Motifs Discovery In Software Network

Network Motifs are important foundation and basic building blocks of complex network on revealing the architecture design principles and evolutionary mechanism, which has been become a research hotspot of complex network and complex systems. As an artificial complex network, Software Network shows the "Small World" and "Scale-free" phenomenon, but the research on the motifs of software network is insufficient. Currently, the research of motifs discovery algorithm is almost the serial algorithm based on single platform, while the lower efficiency of the serial algorithm is difficult to meet the needs of motifs discovery in large-scale networks, which limiting the research and analysis on motifs in software network.First, this thesis analyzes the execution principles and processes of the traditional serial motifs discovery algorithm, and explore the parallelism of motifs discovery process according to the characteristics of motifs discovery and the data processing sequence, and introduce the parallel algorithm and parallel programming models to clarify the reasons for choosing MapReduce programming model in this thesis. Then, according to a detailed analysis of ESU motifs discovery algorithm based on node expansion, we sum up the treelike search structure and the potential parallelism, and develop a MapReduce-based algorithm for motifs discovery named MRESU based on the decomposition of motifs discovery task according to data partitioning. Next, we implement the MRESU algorithm on Hadoop cluster, and the efficiency, speedup and scalability of the algorithm are analyzed and proved out according to using different scale software network. Finally, the MRESU algorithm proposed in this thesis is applied in the research of object-oriented software complexity, and used to find motifs in specific software network, and we analyze the structural feature and evolution laws of specific software systems from the perspective of the motifs. Through analyzing the motifs in multiple software systems and multiple versions of the same software system, we find the relationship between the structural stability and the frequency of occurrence of motifs, as well as the occurrence laws of stable motifs in software evolution process, and reveal the relationship between the macrostructure stability and the microstructure stability of object-oriented software systems.The MRESU algorithm proposed in this thesis enhances the efficiency of motifs discovery significantly, and provides an effective means for finding motifs in large-scale software network. In addition, through applying the MRESU algorithm to the research of object-oriented software complexity, we do an analysis of the structural feature and evolution laws of object-oriented software systems, which helps software developers in-depth understanding of the architecture and evolution process of software systems, and has an improtant guiding significance to the iterative development of software systems.