Spectral variation of normalized Laplacian for various directed and undirected network models

In recent years, complex network research which is multidisciplinary by nature is very popular as it is a valuable tool for analysing complex real-world systems. These systems are usually studied in a large-scale data structure where they show different kinds of non-trivial topological structural properties. Since realworld systems are sometimes too large to describe explicitly, various network models have been developed to mimic their construction processes. While most of the tools used to study their structural properties are coming from graph theory, spectral analysis is another method that can be used to reveal the structural inheritance properties of a network. In this dissertation, we focus on the studies for normalised Laplacian spectrum on six different undirected and directed network models namely, Erdos-Rényi (ER), Watts-Strogatz (WS), Barabási-Albert (BA), square grid ((Sgrid, triangular grid (Tgrid) and growing geometrical network (GGN) network models. These network models are manipulated and constructed using Mathematica software. Spectral graph theory is used to study the network properties by utilising eigenvalues associated with the normalised Laplacian matrix computed via eigendecomposition method. Spectral measures such as spectral density plot, Cheeger constant, discrepancy and energy have been performed to analyse the directed and undirected network models. The spectral plot for the undirected and directed networks showed very different patterns. Most of the directed network models showed a very sharp peak at eigenvalue 1 while for the undirected networks only ER, BA and Sgrid show this feature. Undirected Tgrid plots have two peaks, one is at 1 and another is in between {1, 1.5} while GGN has a sharp peak at 1.5 and followed by a smaller peak between {1, 1.5}. These patterns are usually unique and depend on the network itself. Network motifs have been utilized to analyse the topological structure of these networks. It is found that ER network is mainly formed by tree motif and bipartite motif, WS network model consists of motifs with cliques, BA network model has bow-tie motifs, Sgrid network model has square motif and finally, Tgrid and GGN network model has triangle motif. For directed networks, the eigenvalues depend on whether the motif is cyclic or noncyclic and whether they are open or closed loops. A high number of eigenvalue 1 are produced if the motif is open or noncyclic closed loop. From Cheeger constant (hG) measurement, it is found that ER models has the highest hG follow by BA and WS. This implies that ER models is difficult to be separated due the high volume of edges and random distribution of its edges. For BA and WS, hG do not change much while Tgrid and GGN recorded a decrease in hG. As for Sgrid, the hG decreased then increased. For the directed network, the results are similar because the calculation does not take into consideration of the direction of the edges. Discrepancy of the graph for the undirected networks is also calculated using results from the Cheeger constant measurement. Results show that edges in ER models are distributed randomly while edges in Sgrid, Tgrid and GGN models are distributed in a controlled fashion. In the energy measurement, adjacency matrix (A(G)) and normalised Lapalcian matrix (NL(G)) are used in both undirected and directed network models. The adjacency energy ratio (RAM) of ER model is more than one implying that it is a highly random strongly regular graph with edges multiple time higher than the number of nodes. As for other networks, their RAM and normalised Laplacian energy ratio (RNL) values do not change much as the network size increase mainly because the edges increase linearly with the numbers of nodes. In the directed network energy measurement, energy is much smaller as compared to the undirected part because it depends on close-loop network. Open-loop and acyclic networks give zero energy value to the system.

Text JESSICA LIANG YEI SHAN - IR.pdf Download (973kB)

Actions (login required)

View Item