Research On Software Model And Community Detection In Complex Networks

In recent years,complex networks have been rapidly developed as interdisciplinary subjects in many fields,especially in the field of computers,which have been paid attention and research by scholars.In the real world,the Internet,neural networks,protein networks,social networks,etc.can be regarded as a complex network in which the constituent units are abstracted as nodes,and the relationships between the constituent units are abstracted as edges.The "small world effect","scale-free characteristics" and "community structure" of complex networks have become research hotspots in complex networks.With the deepening of complex network research and the continuous expansion of application fields,such as metabolic pathway prediction,Web community mining,search engine,open source software,etc.,network problems in new fields becomes a new research direction,Mainly includes: 1)Network characteristics in the software field;2)Network model evolution in the software field;3)Large-scale complex networks require high community detection accuracy and low complexity problems;4)The overlapping degree of overlapping community structures and the quality of results.This dissertation focuses on the network characteristics,network evolution models in the field of open-source software and complex network community detection problems,solves the characteristics of open-source software networks and issues related to the evolution model of open-source software networks,and proposes new complex network community detection algorithms.The main contributions of this dissertation are in the following:1)Complex network theory is used to study the complexity of the software system in this paper.The selected object-oriented open-source software framework both Web Work and Spring as the research object,undirected(directed)graph nodes representing classes,relationships between classes edges representing dependency,association,etc.,the system is abstracted to the network graph and its topology is analyzed.Studies show that undirected(directed)network has a large clustering coefficient and a smaller average path length,which are characteristic of a small world.The results show that the statistical properties of the degree distribution still have scale-free characteristics.2)An evolution model of software networks based on local events is proposed.The model uses object-oriented software systems as research object and improves the BA scale-free network model,local events such as changes in node and edges are added,and the model is used to simulate the evolution of software networks.Simulation results show that the degree distribution of the network generated by this model follows power law distribution.and the degree distribution is in agreement with that of real software network,which can simulate the evolution process of real software.Thus,the proposed model can simulate and evaluate the evolution of object-oriented software network.3)An algorithm for community detection named Marko Random Walks Ants is proposed The algorithm is inspired by Markov random walks model theory,the probability of ants being located in any node within a cluster will be greater than the probability of ants being located outside the cluster.Through the random walks,the network structure is revealed.The algorithm is a stochastic method which uses the information collected during the traverses of the ants in the network.The algorithm is validated on different datasets including computer-generated networks and real-world networks.The outcome shows the algorithm performs moderately quickly with providing an acceptable time complexity and its result appears good in practice.4)A Genetic Algorithm based on K-clique for complex networks is proposed.K-clique-based population initialization,(? + ?)selection strategy and Q function are adopted to select the next generation of population,then the formed communities are clustered to realize community division.It is validated on benchmark networks and real-world networks,which can improve the accuracy and efficiency of population initialization,the superior traits formed by parents during the process of evolution cannot be destroyed and can also be effectively inherited by offspring individuals.The algorithm can reduce the search space of community partition and improve the search efficiency of the algorithm.5)An overlapping community detection algorithm COPRAPC(Community Overlap Propagation Algorithm based on Page Rank and Clustering Coefficient)is proposed.The algorithm used Page Rank algorithm to rank the influence of nodes,which can stabilize the community finding results.The parameter of node clustering coefficient is a node-related parameter,which can be used to modify the parameters of the algorithm and limit the maximum number of labels each node,so as to improve the quality of community mining.Experiments on artificial networks and real-world networks show that the algorithm can effectively detect overlapping communities,and the algorithm has acceptable time efficiency and algorithm complexity.6)A novel Local Information Cliques for detecting overlapping communities is proposed.The algorithm draws on the assumption that cliques are the core of communities,the proposed algorithm adopts the single node with the highest density as the initial community,the local optimization search strategy based on fitness function is used,and k-cliques is added when the natural community expands,so as to realize the detection of overlapping communities.The search efficiency of the algorithm is improved.Experiments on artificial networks and real-world networks show that the algorithm achieves better accuracy in overlapping community detection.