Structure Feature Representation For Dynamic Network And Pattern Mining On Multi-layer Network

Complex networks,as an effective tool for analyzing the relationship between individuals and the characteristics of functional structures in complex systems,have been widely used in various fields.At present,with the continuous development of science and technology,a large number of multi-dimensional,dynamic and multi-level data are generated,which requires researchers to analyze and mine useful information.However,traditional static and single-layer network model is not enough to describe deep-seated characteristics from the informative data.Therefore,as an upgrade and extension of traditional complex network model,multi-layer network model is proposed and used to characterize and detect more realistic features of complex systems.Multi-layer network is a kind of coupling network which combines multiple connection relationships.For example,social networks at different levels consist of many kinds of interpersonal relationships,such as friends,family members and colleagues.Multi-layer networks can be divided into various forms according to the different coupling relationships among layers,such as dynamic networks with time-series relationships,interconnected networks that layers are related by individuals,and interdependent networks that each layer is strongly dependent by nodes,etc.Characterizing important structural features of multi-layer networks and mining patterns,such as dynamic evolution and conserved structure,are of great significance for understanding and analyzing complex systems.Recently,the topological feature analysis,dynamic evolution analysis,structural feature characterization and defining and mining of functional structure patterns in multi-layer networks have become research hotspots.This dissertation mainly focuses on two aspects,that are,structure feature characterization of multi-layer network and pattern mining.Specifically,this dissertation includes dynamic network similarity measurement and dynamic community detection,dynamic network representation learning and finding conserved module structures in multi-layer network.The main research contents and contributions of this dissertation are as follows: 1.It has been demonstrated that the structural perturbation in static network is excellent in characterizing the topology recently.In order to investigate the perturbation structural theory in dynamic networks,this paper extends the theory by considering the dynamic variation information between networks of consecutive time as a perturbation set.Thus,a structural perturbation similarity is proposed for measuring the similarity between nodes in dynamic networks.Furthermore,by combining local topological similarity measures,the structural characteristics of dynamic networks are characterized from different aspects.With the proposed similarity,we come up with a dynamic community detection algorithm based on evolutionary clustering and density clustering to detect the community structure on the networks changing over time.The advantages of this study are as follows: 1)The structural perturbation similarity on dynamic networks fully combines dynamic information,and it is based on matrix eigenvalue decomposition.The eigenvalues and eigenvectors reflect the topological characteristics of the network at the macro level,which is helpful to characterize the dynamic community structure.2)The evolutionary clustering method considers the community evolution information,and the density clustering method does not need to set the potential community number in advance.On the synthetic network and several real dynamic networks,it is shown that the method presented in this dissertation can effectively detect the dynamic community structure,and thus reflect the superiority of the proposed similarity measure.2.Research on most current network representation learning lacks consideration for time evolving.This dissertation provides a method for dynamic network representation learning,so as to represent nodes in dynamic networks with a low-dimensional vector containing time information.By fully combining the local neighbor structure,community structure and dynamic evolution information,this paper proposes a two-layer non-negative matrix factorization model,and use the idea of evolutionary clustering to consider the dynamic evolution information to the local neighbor structure and community structure.The advantages of this research are as follows.1)The two-layer non-negative matrix factorization model can simultaneously obtain the community structure and the lowdimensional representation vectors of nodes.And the community structure is integrated into the vector representation.2)The dynamic information are considered in the local topology structure and community structure in two forms,taking full account of the impact of dynamic changes on different levels of topology.In this paper,on different synthetic and real datasets,the node classification task and dynamic community detection task are mainly used to evaluate the performance of the node vector representation obtained by the proposed method.The results show the effectiveness of the proposed method and indicate that combining different levels of topology and dynamic information for dynamic network representation learning is useful.3.The conserved structure in a multi-layer network is very important,since it reflects the common traits in multiple networks.This dissertation proposes two feature metrics—connection strength and participation coefficient,which are used to respectively measure the tightness of each pair of nodes on the overall level of the multi-layer network and the uniformity of the connection weights over all networks.According to the two proposed feature metrics,the multi-layer network can be compressed into two related feature matrices.Then,the conserved module is detected only on these two feature matrices based on the multi-view non-negative matrix factorization.The algorithm itself has nothing to do with the number of networks,which greatly reduces the computational space and time complexity.The method is applied to multi-layer biological networks and an in-depth analysis is made.On the 33 cancer-associated gene co-expression networks,conserved gene modules such as ribosome synthesis and immune response were identified,which reflected the common traits of cancer occurrence and development.On the 15 protein interaction networks in different regions of human brain tissues,the proposed method identifies conserved functional modules related to nervous system development.