Computation and analysis of spectra of large undirected networks

Download
index.pdf
2010
Erdem, Özge
Show full item record
271
views
94
downloads
Many interacting complex systems in biology, in physics, in technology and social systems, can be represented in a form of large networks. These large networks are mathematically represented by graphs. A graph is represented usually by the adjacency or the Laplacian matrix. Important features of the underlying structure and dynamics of them can be extracted from the analysis of the spectrum of the graphs. Spectral analysis of the so called normalized Laplacian of large networks became popular in the recent years. The Laplacian matrices of the empirical networks are in form of unstructured large sparse matrices. The aim of this thesis is the comparison of different eigenvalue solvers for large sparse symmetric matrices which arise from the graph theoretical epresentation of undirected networks. The spectrum of the normalized Laplacian is in the interval [0 2] and the multiplicity of the eigenvalue 1 plays a particularly important role for the network analysis. Moreover, the spectral analysis of protein-protein interaction networks has revealed that these networks have a different distribution type than other model networks such as scale free networks. In this respect, the eigenvalue solvers implementing the well-known implicitly restarted Arnoldi method, Lanczos method, Krylov-Schur and Jacobi Davidson methods are investigated. They exist as MATLAB routines and are included in some freely available packages. The performances of different eigenvalue solvers PEIG, AHBEIGS, IRBLEIGS, EIGIFP, LANEIG, JDQR, JDCG in MATLAB and the library SLEPc in C++ were tested for matrices of size between 100-13000 and are compared in terms of accuracy and computing time. The accuracy of the eigenvalue solvers are validated for the Paley graphs with known eigenvalues and are compared for large empirical networks using the residual plots and spectral density plots are computed.
Numerical analysis.
http://etd.lib.metu.edu.tr/upload/12612233/index.pdf
https://hdl.handle.net/11511/19804
Graduate School of Applied Mathematics, Thesis

Suggestions

Computation and analysis of spectra of large networks with directed graphs
Sarıaydın, Ayşe; Karasözen, Bülent; Jost, Jürgen; Department of Scientific Computing (2010)
Analysis of large networks in biology, science, technology and social systems have become very popular recently. These networks are mathematically represented as graphs. The task is then to extract relevant qualitative information about the empirical networks from the analysis of these graphs. It was found that a graph can be conveniently represented by the spectrum of a suitable difference operator, the normalized graph Laplacian, which underlies diffusions and random walks on graphs. When applied to large...
Computation of Spectra of Large Networks
Erdem, Özge; Karasözen, Bülent (2010-11-27)
Many interacting complex systems in biology, physics, technology and social systems can be represented in a form of large networks. The networks are mathematically represented by graphs. A graph is usually represented by adjacency or Laplacian matrix. Many important features of the underlying structure and dynamics of them can be extracted from the analysis of the spectrum of graphs. Spectral analysis of the so called normalized Laplacian matrix of large networks has become popular in recent years. The Lapl...
Computation of Graph Spectra of Protein-Protein Interaction Networks
Karasözen, Bülent (2011-05-05)
Complex systems from many areas such as biology, sociology, technology appear in form of large networks. These networks are represented usually in form of graphs and their structural properties are analyzed using the methods of graph theory. The so called Laplacian matrix became an important tool of spectral graph theory for the investigation of structural properties of large biological networks. Many important features of the underlying structure and dynamics of systems can be extracted from the analysis o...
Error analysis for the numerical evaluation of the diagonal forms of the scalar spherical addition theorem
Koc, S; Song, JM; Chew, WC (Society for Industrial & Applied Mathematics (SIAM), 1999-04-29)
The numerical solution of wave scattering from large objects or from a large cluster of scatterers requires excessive computational resources and it becomes necessary to use approximate-but fast-methods such as the fast multipole method; however, since these methods are only approximate, it is important to have an estimate for the error introduced in such calculations. An analysis of the error for the fast multipole method is presented and estimates for truncation and numerical integration errors are obtain...
Two dimensional finite volume weighted essentially non-oscillatory euler schemes with uniform and non-uniform grid coefficients
Elfarra, Monier Ali; Akmandor, İbrahim Sinan; Department of Aerospace Engineering (2005)
In this thesis, Finite Volume Weighted Essentially Non-Oscillatory (FV-WENO) codes for one and two-dimensional discretised Euler equations are developed. The construction and application of the FV-WENO scheme and codes will be described. Also the effects of the grid coefficients as well as the effect of the Gaussian Quadrature on the solution have been tested and discussed. WENO schemes are high order accurate schemes designed for problems with piecewise smooth solutions containing discontinuities. The key ...
Citation Formats
Ö. Erdem, “Computation and analysis of spectra of large undirected networks,” M.S. - Master of Science, Middle East Technical University, 2010.
METU IIS - Integrated Information Service open@metu.edu.tr