Computation and analysis of spectra of large undirected networks

Abstract

Biyoloji, fizik, teknoloji ve sosyal sistemler gibi alanlarda yer alan kompleks sistemler büyükağlar şeklinde gösterilebilinirler. Bu ağlar, daha sonra matematiksel olarak çizgeler şeklindeifade edilirler. Çizgeler, Adjacency ve Laplace matrisleriyle gösterilebilinecekleri bulunmuştur.Böylece sistemlerin yapılarının ve dinamiklerinin önemli özellikleri matrislerin spektrumanalizlerinden çıkarılır. Büyük ağların birimleştirilmiş Laplace matrislerinin analizi son yıllardapopüler hale gelmiştir. Bu matrisler genellikle 0 ların çoğunlukta olduğu ve düzensiz biryapıya sahiptirler. Bu tezin amacı farklı özdeğer çözücülerin yönsüz ağların simetrik matrislerşeklinde gösterimlerinden doğan büyük ve sparse yapıdaki matrisler üzerindeki performanslarınıkarşılaştırmaktır. Birimleştirilmis¸ Laplace matrisinin özdeğerleri [0,2] aralığındadırve 1 özdeğerlerinin çokluğu (multiplicity) ağların analizinde önemli rol oynamaktadır. Ayrıcaprotein etkileşim ağları üzerinde yapılan çalışmalar sonucunda bu ağların mevcut olarak bilinenmodel ağlara göre daha farklı bir spektral dağılıma sahip olduğu bulunmuştur. Buc¸erc¸evede, dolaylı olarak yeniden bas¸layan Arnoldi(IRA), blok Lanczos, Krylov?Schur veJacobi?Davidson metotlarına dayanan özdeğer cözücüler araştırılmıştır. Bu çözücüler MATLABrutini olarak ve ücretsiz yazılımlar halinde bulunmaktadır. MATLAB da yazılmıs¸ özdeğerçözücülerinden, SPEIG, AHBEIGS, IRBLEIGS, EIGIFP, LANEIG, JDQR, JDCG, ve C++ da yazılmıs¸ olan SLEPc paketinin performansları büyüklükleri 100 ile 13000 arasında değişenmatrisler üzerinde kesinlik ve süreleri açısından karşılaştırıldı. Bu bazda özdeğerleri bilinenPaley çizgeleri ile ampirik ağlardan doğan çizgelerin birimleştirilmiş Laplace matrisleri kullanıldı.Paley çizgelerinin özdeğerleri için hata figürleri, ampirik ağların özdeğerleri için iseresidual figürleri ile spektral dağılımlarının gösteren figürler oluşturuldu.

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 representedby 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 theanalysis of the spectrum of the graphs. Spectral analysis of the so called normalized Laplacianof large networks became popular in the recent years. The Laplacian matrices of the empiricalnetworks are in form of unstructured large sparse matrices. The aim of this thesis is the comparisonof dierent eigenvalue solvers for large sparse symmetric matrices which arise fromthe graph theoretical representation of undirected networks. The spectrum of the normalizedLaplacian is in the interval [0; 2] and the multiplicity of the eigenvalue 1 plays a particularlyimportant role for the network analysis. Moreover, the spectral analysis of protein-proteininteraction networks has revealed that these networks have a dierent distribution type thanother model networks such as scale free networks. In this respect, the eigenvalue solversimplementing 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 dierent eigenvaluesolvers SPEIG, AHBEIGS, IRBLEIGS, EIGIFP, LANEIG, JDQR, JDCG in MATLAB andthe library SLEPc in C++ were tested for matrices of size between 100-13000 and are comparedin terms of accuracy and computing time. The accuracy of the eigenvalue solvers arevalidated for the Paley graphs with known eigenvalues and are compared for large empiricalnetworks using the residual plots and spectral density plots are computed.