Computation and analysis of spectra of large networks with directed graphs

Abstract

Biyoloji, bilim, teknoloji ve sosyal sistemlerdeki geniş ağların analizi son zamanlarda çok popüler olmuştur. Bu ağlar matematiksel olarak çizgiler şeklinde gösterilebilmektedir. Bu tür deneysel ağların çizge şeklinde gösterimleri, ağ yapısıyla ilgili gerekli niteliksel bilgileri çıkarabilmede büyük önem taşımaktadır.Bir grafik, birimleşirilmiş Laplace gösterimi diye adlandırılan, grafik üzerindeki yayılmalarıve olası gidişleri belirleyen uygun bir fark işleticisinin spektrumu tarafından gösterilebilmektedir.Bu işlem geniş ağlara uygulandığında büyük matrislerin spektrumunun sayısal yöntemlerlebelirlenmesi gerekmektedir. Büyük ağarı temsil eden birimleştirilmiş Laplace matrisi düzenlibir yapıya sahip olmamaktadır ve doğal ölçeklenme özelliği göstermemektedir.Bu tezde, deneysel ağların yönlendirilmiş cizgelerini gösteren simetrik olmayan birimleştirilmişLaplace matrisi için uygun özdeğer yötemleri karşılaştırılacaktır. Bu metodlar MATLAB yada C++ daki kitaplık programı olan SLEPc gibi paket programlar olarak serbestçe bulunabilentam olarak yeniden başlatılmayan Arnoldi metodu, Krylov-Schur metodu ve Jacobi-Davidsonmetodları gibi çeşitli Krylov alt uzay algoritmalarını kapsamaktadır.Uygulanan Laplace grafiği normalize edilmiş olup spektrumu (0, 2) aralığından oluşmaktadır.Özdeğer dağılımı ağ analizinde büyük önem taşımaktadır. Sayısal olarak yapılması gerekentüm özdeğerlerin uygun yöntemlerle hesaplanmasıdır. Bu yüzden mevcut yöntemlerin birkarşılaştırması yönlendirilmiş Paley çizgelerinin bilinen özdeğerleriyle ve 400, 1100 ve 4500büyüklüklerindeki alıntı ağlarıyla kalıntı hesaplanarak yapılacaktır.

Analysis of large networks in biology, science, technology and social systems have becomevery popular recently. These networks are mathematically represented as graphs. The task isthen to extract relevant qualitative information about the empirical networks from the analysisof these graphs.It was found that a graph can be conveniently represented by the spectrum of a suitable differenceoperator, the normalized graph Laplacian, which underlies diffusions and random walkson graphs. When applied to large networks, this requires computation of the spectrum of largematrices. The normalized Laplacian matrices representing large networks are usually sparseand unstructured.The thesis consists in a systematic evaluation of the available eigenvalue solvers for nonsymmetriclarge normalized Laplacian matrices describing directed graphs of empirical networks.The methods include several Krylov subspace algorithms like implicitly restarted Arnoldimethod, Krylov-Schur method and Jacobi-Davidson methods which are freely available asstandard packages written in MATLAB or SLEPc, in the library written C++.The normalized graph Laplacian as employed here is normalized such that its spectrum isconfined to the range [0, 2]. The eigenvalue distribution plays an important role in networkanalysis. The numerical task is then to determine the whole spectrum with appropriate eigenvaluesolvers. A comparison of the existing eigenvalue solvers is done with Paley digraphswith known eigenvalues and for citation networks in sizes 400, 1100 and 4500 by computingthe residuals.