Computation and analysis of spectra of large networks with directed graphs

Download

index.pdf

Date

2010

Author

Sarıaydın, Ayşe

Metadata

Show full item record

Item Usage Stats

157
views

74
downloads

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 networks, this requires computation of the spectrum of large matrices. The normalized Laplacian matrices representing large networks are usually sparse and unstructured. The thesis consists in a systematic evaluation of the available eigenvalue solvers for nonsymmetric large normalized Laplacian matrices describing directed graphs of empirical networks. The methods include several Krylov subspace algorithms like implicitly restarted Arnoldi method, Krylov-Schur method and Jacobi-Davidson methods which are freely available as standard packages written in MATLAB or SLEPc, in the library written C++. The normalized graph Laplacian as employed here is normalized such that its spectrum is confined to the range [0, 2]. The eigenvalue distribution plays an important role in network analysis. The numerical task is then to determine the whole spectrum with appropriate eigenvalue solvers. A comparison of the existing eigenvalue solvers is done with Paley digraphs with known eigenvalues and for citation networks in sizes 400, 1100 and 4500 by computing the residuals.

Subject Keywords

Numerical analysis.

URI

http://etd.lib.metu.edu.tr/upload/12612249/index.pdf
https://hdl.handle.net/11511/19806

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

Computation and analysis of spectra of large undirected networks Erdem, Özge; Karasözen, Bülent; Jost, Jürgen; Department of Scientific Computing (2010) 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 ...
Modern tools for the time-discrete dynamics and optimization of gene-environment networks DEFTERLİ, ÖZLEM; Fuegenschuh, Armin; Weber, Gerhard Wilhelm (Elsevier BV, 2011-12-01) In this study, we discuss the models of genetic regulatory systems, so-called gene-environment networks. The dynamics of such kind of systems are described by a class of time-continuous ordinary differential equations having a general form (E) over dot = M(E)E, where E is a vector of gene-expression levels and environmental factors and M(E) is the matrix having functional entries containing unknown parameters to be optimized. Accordingly, time-discrete versions of that model class are studied and improved b...
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...
Development of a pressure-based solver for both incompressible and compressible flows Denk, Kerem; Sert, Cüneyt; Department of Mechanical Engineering (2007) The aim of this study is to develop a two-dimensional pressure-based Navier-Stokes solver for incompressible/compressible flows. Main variables are Cartesian velocity components, pressure and temperature while density is linked to pressure via equation of state. Modified SIMPLE algorithm is used to achieve pressure-velocity coupling. Finite Volume discretisation is performed on non-orthogonal and boundary-fitted grids. Collocated variable arrangement is preferred because of its advantage on staggered arrang...
Implementation of different flux evaluation schemes into a two-dimensional Euler solver Eraslan, Elvan; Aksel, Mehmet Haluk; Department of Mechanical Engineering (2006) This study investigates the accuracy and efficiency of several flux splitting methods for the compressible, two-dimensional Euler equations. Steger-Warming flux vector splitting method, Van Leer flux vector splitting method, The Advection Upstream Splitting Method (AUSM), Artificially Upstream Flux Vector Splitting Scheme (AUFS) and Roe’s flux difference splitting schemes were implemented using the first- and second-order reconstruction methods. Limiter functions were embedded to the second-order reconstruc...

Citation Formats

A. Sarıaydın, “Computation and analysis of spectra of large networks with directed graphs,” M.S. - Master of Science, Middle East Technical University, 2010.