Graph Signal Processing On Complex Network

The research of complex network has achieved great success in many fields, such as network modeling, cluster analysis and so on.Most researches focus on network structure or emphasis on the nature of network nodes. Recently,a framework called graph signal processing (GSP) has been proposed which breaks the research dilemma.We introduce basic principle of GSP firstly. GSP algorithm maps property of nodes into a graph signals and transforms the graph signals to another dimension by graph Fourier transform. However,GSP algorithm is suitable for homogeneous network only.Homogeneous network is the network that contains only one type of node. For the scene of heterogeneous network, we propose an algorithm called signal processing on tensor (TSP), which extends GSP algorithm to heterogeneous network. Firstly, TSP algorithm uses adjacent tensor to model the heterogeneous network. Secondly, it propagates graph signals on heterogeneous network. Finally, a graph filter, which is suitable for heterogeneous networks, is designed by defining graph Fourier transform based on tensor decomposition.Because TSP algorithm is applied on heterogeneous network, it not only analyze the graph filter of homogeneous network, but also takes topological structure between different types of nodes into account,which makes the best use of known information. TSP algorithm extends the scope of application of GSP algorithm and analyzes the filtering rule of graph signals more accurately.In the aspect of algorithm simulation, we present a semi-supervised classification algorithm based on TSP algorithm.The accuracy of classification is used to prove the validity of TSP algorithm. In this thesis, TSP algorithm is applied to DBLP database,Sina microblogging database and a constructed heterogeneous network respectively. Compared with GSP algorithm, which is for homogeneous networks only, TSP algorithm achieves higher accuracy of classification. The advantage of the TSP algorithm is more obvious when the proportion of known nodes is small.