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...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English |
| Published: |
2022
|
| Subjects: | |
| Online Access: | http://psasir.upm.edu.my/id/eprint/104717/1/JESSICA%20LIANG%20YEI%20SHAN%20-%20IR.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| id |
my-upm-ir.104717 |
|---|---|
| record_format |
uketd_dc |
| institution |
Universiti Putra Malaysia |
| collection |
PSAS Institutional Repository |
| language |
English |
| advisor |
Chan, Kar Tim |
| topic |
Laplacian matrices Spectral geometry |
| spellingShingle |
Laplacian matrices Spectral geometry Liang, Jessica Yei Shan Spectral variation of normalized Laplacian for various directed and undirected network models |
| description |
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. |
| format |
Thesis |
| qualification_level |
Master's degree |
| author |
Liang, Jessica Yei Shan |
| author_facet |
Liang, Jessica Yei Shan |
| author_sort |
Liang, Jessica Yei Shan |
| title |
Spectral variation of normalized Laplacian for various directed and undirected network models |
| title_short |
Spectral variation of normalized Laplacian for various directed and undirected network models |
| title_full |
Spectral variation of normalized Laplacian for various directed and undirected network models |
| title_fullStr |
Spectral variation of normalized Laplacian for various directed and undirected network models |
| title_full_unstemmed |
Spectral variation of normalized Laplacian for various directed and undirected network models |
| title_sort |
spectral variation of normalized laplacian for various directed and undirected network models |
| granting_institution |
Universiti Putra Malaysia |
| publishDate |
2022 |
| url |
http://psasir.upm.edu.my/id/eprint/104717/1/JESSICA%20LIANG%20YEI%20SHAN%20-%20IR.pdf |
| _version_ |
1783725835763580928 |
| spelling |
my-upm-ir.1047172023-10-05T06:35:00Z Spectral variation of normalized Laplacian for various directed and undirected network models 2022-09 Liang, Jessica Yei Shan 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. Laplacian matrices Spectral geometry 2022-09 Thesis http://psasir.upm.edu.my/id/eprint/104717/ http://psasir.upm.edu.my/id/eprint/104717/1/JESSICA%20LIANG%20YEI%20SHAN%20-%20IR.pdf text en public masters Universiti Putra Malaysia Laplacian matrices Spectral geometry Chan, Kar Tim |