Pattern Mining Algorithms In Complex Networks

With the rapid development of information technology and the continuousimprovement of the theory and technology of various disciplines, complexity andcomplicated science has become one of the most important research areas recently.Complex networks are the most widely used model in complex systems, and the studyof them focuses on exploring the commonness among various networks in differentfields(including biology, society, and information) and the universal methods to dealwith them. It is a big challenge to understand complex networks quantitatively andqualitatively today.Complex network patterns characterize the topological structural property atsubstructure level, and are important hints for understanding the structure and functionof complex systems. These patterns may also tell the evolution laws and help us predictthe evolutionary trends of complex systems. For instance, network motifs and modulesare important function units in complex networks; dynamic patterns and modules arekey dynamic properties, which can be used to predict the future behaviour of complexsystems. As complex networks are graphs in mathematical term, pattern mininginvolves subgraph searching, graph isomorphism determination, graph clustering, andso on, most of which are high computational complexity. Therefore, pattern mining incomplex networks are of great theoretical significance and application value.This thesis studies pattern mining algorithms in real biological networks and socialnetworks. The patterns consist of network motifs and modules in static complexnetworks, dynamic patterns and modules in dynamic complex networks. Of course,these algorithms can also be used in other complex networks. Specifically, weinvestigate the following problems and make the following contributions.1. We propose a probability network motif discovery algorithm based on clusteringanalysis, with respect to the uncertainty and noise in complex networks. Firstly, wesearch non-treelike subgprahs of which the probability of occurrence in randomnetworks is small, by using ESU (Enumerate Subgraphs). Secondly, we calculate graphisomorphism among the subgraphs by using canonical labeling and determine theoccurrence frequency of every subgraph. Thirdly, we cluster these subgraphs byregarding similar subgraphs as a probability motif. Through setting different values forthe parameter, one, more, or exact motifs are obtained for a given size. Experimentresults on the protein-protein interaction networks and the transcriptional regulatorynetworks of E. coli and S. cerevisiae show that the algorithm can not only find known motifs, but also potential motifs.2. We study a module identification algorithm based on network symmetry andspectral clustering for the large size and complex structure in complex networks. Firstly,we compress complex networks by making use of their symmetry property, and thencluster the compressed networks by spectral clustering. As similarity graphs areimportant for spectral clustering, we also analyze three types of similarity definitionbetween nodes, i.e. adjacency similarity, common neighbor similarity, and transmissionsimilarity. Experiment results on the protein-protein networks of S. cerevisiae show thatspectral clustering based on network symmetry compression and other three similaritygraphs obtain good performance, and the former is more efficient. Furthermore, spectralclustering based on network symmetry compression is comparable to several typicalalgorithms for protein-protein interaction network decomposition.3. To characterize the evolution laws of dynamic networks, and predict theirbehavior, we define periodic dynamic pattern and stage dynamic pattern, and propose adynamic pattern mining algorithm based sequence analysis. Periodic dynamic patternsare regular and periodic substructures, and stage dynamic patterns are substructures thatexist among the whole period of dynamic networks or a certain stage. For the method, asummary graph is used to represent the dynamic network, with0/1sequences on itsedges. And pattern mining is executed on this summary graph and these0/1sequences.As there are noises in the dynamic networks, quasi-dynamic patterns are defined whichpermit certain degree of errors. Experiment results on several real dynamic networksshow that our algorithm can find some interesting patterns.4. Module structures are still an important topic in dynamic network analysis, so wepropose a dynamic module analysis framework based on evolutionary clustering. Firstly,we propose a framework for analyzing dynamic modules, in which moduleidentification, variation in quantity between two networks, module adjustment, andmodule evolvement analysis are involved. Then, we give a method for eachcomputation task. Experiment results on dynamic gene-regulatory networks during thefull developmental cycle of D. melanogaster show that our algorithm can obtain somemeaningful results.