The Spectral Distance Based On The Normalized Laplacian And Its Applications On Complex Networks

Graph theory is an important method to analysis our real world. Normally, a complex system can be described as a complex network. In one complex network, ver-tices represent some typical objects in one complex system and edges express relations among these objects. In order to explain and comprehend characterized phenomena in one complex system, different models and parameters have been proposed to explore the graph structure and model the dynamical behaviors. Identifying the unique and typical features of one complex system and capturing universal properties existing in common complex systems are two important issues in graph theory and network the-ory. For example, three generic network models depict the notable characteristics in common complex systems, hence support one rough classification of real networks. Meantime, some remarkable structures related to some particular functions are well-discussed in some classes of graphs. For instance, motif, discovered in the gene reg-ulation networks and a lot of natural networks, is one of the common and important local properties existing in biological networks. Besides of the rough classification and looking for the general features on networks, there are two questions, how to measure the difference between two graphs in the sense of structure, especially for graphs shar-ing the same class; is there more visual method to understand the graphs structures or dynamics on networks?In recent years, the spectral graph theory brings us crucial insights and useful ideas for considering these problems. Many developments in spectral graph theory often have a geometric flavor, particularly are related to Riemannian geometry. One can discriminate different classes of graphs and find clues of some evolutionary processes from the spectral plots of the normalized Laplacian. Moreover, The information about different topological properties of a graph has been proved to be carried by its complete spectrum. There is no question that the spectra of the graph Laplacian play a vital role in our fundamental understanding of graphs structures. Based on this, we propose the spectral distance to measure the difference between graphs in the sense of their structures.For two graphs G(V, E) and G’(V, E’) containing N and N’vertices respectively, their eigenvalues of the normalized Laplacian matrices can be written as: Formally, We define the spectral distance D(G, G’) in the following way: where ρG(x)= is the eigenvalues density for graph G and σhere is the bandwidth. Obviously, this distance is bounded in [0,2] and is a pseudometric on the space of graphs due to the existence of nonisomorphic but cospectral graphs.We investigate the behavior of the spectral distance for large graphs, particularly in graphs whose size tends to infinity. We prove the distance between two graphs be-longing to the same spectral class becomes zero, whose sizes tend to infinity. Generally speaking, it is difficult to break or change the structure of one large graph by finite edit steps. Moreover, we prove that the distance between two large graphs belonging to the same spectral class and only differing in finite edit operations is equal to σ(1/N), and σ(1/N2) in particular cases. Additionally, the time complexity to calculate the spec-tral distance can be around σ(N2). All these results show that the spectral distance can be used to measure structural differences between two graphs efficiently and quickly.Furthermore, we define another spectral distances dp on the set of all graphs based on the spectrum of the normalized Laplacian, by assigning a probability mea-sure to each graph and taking Lp Wasserstein distances between probability measures. Through equipped with d1, we prove that the diameter of the set of graphs, as a pseudo-metric space, is one.Based on the relationship between the spectral distance and the evolutionary dis-tance, the spectral distance is used to construct the phylogenetic tree on species via real biological networks. By calculating the quartet distance, the spectral distance can predict more accurate phylogenetic trees, with respect to expert classifications, than the ones obtained by the edit distance (in the case of attributed graphs).In summary, we propose a novel method in this thesis, based on the spectral dis-tance, as an efficiency and reliable tool to identify the relationship among networks.