Spectral Graph Partitioning Using QR Algorithm

Yıl 2022, Cilt: 34 Sayı: 2, 207 - 218, 30.09.2022

Mücahit Sülü Resul Daş

Öz

In this study, spectral graph segmentation algorithm, which is one of the graph analysis methods calculated using numerical methods, has been implemented. In practice, data from the BBC's Doctor Who television series, which continued for 39 seasons from 1963 to the present, were used. In the Doctor Who simple diagram from this television series, the nodes represent the characters' names in the series. The weight $w$ between nodes $i,j$ is created to represent an undirected edge where the characters play together $w$ times in the same section. In this data set, the question of what kind of separation would be if the movie actors who played together in the same episode were to be divided into two groups according to the intensity of playing together was started. The weighted relations in these data were modeled with the graph, and the Laplace matrix of the graph was calculated. Eigenvalues and eigenvectors belonging to this calculated Laplace matrix were obtained with the help of QR algorithm and the graph was divided into two parts so that the negative and positive values in the eigenvector line corresponding to the second smallest eigenvalue (Fiedler vector) form different groups.

Anahtar Kelimeler

Graph partitioning, Graph theory, Graph visualization.

QR Algoritması Kullanarak Spektral Çizge Bölümleme

Öz

Bumakaleçalışmasında,sayısalmetotlarkullanılarakhesaplananveçizgeanalizyöntemlerindenolanspek- tral çizge bölümleme algoritmasının uygulaması gerçekleştirilmiştir. Uygulamada, 1963 yılından günümüze kadar 39 sezondur devam eden BBC yapımı Doctor Who televizyon dizisi verileri kullanılmıştır. Bu televizyon dizisinden elde edilen Doctor Who basit çizgesinde, düğümler karakterlerin dizideki isimlerini göstermektedir. 𝑖, 𝑗 düğümleri arasındaki 𝑤 ağırlığı ise karakterlerin aynı bölümde 𝑤 kez beraber oynadığı yönsüz bir ayrıtı temsil edecek şekilde oluşturulmuştur. Bu veri setinde aynı bölümde beraber oynayan film oyuncuları, birlikte oynama yoğunluğuna göre iki gruba ayrılmak istense nasıl bir ayrışma olurdu sorusundan yola çıkılmıştır. Bu verilerdeki ağırlıklı ilişk- iler, çizge ile modellenerek, çizgenin Laplace matrisi hesaplanmıştır. Bu Laplace matrisine ait olan özdeğer ve özvektörler, QR algoritması yardımı ile elde edilmiş ve ikinci en küçük özdeğere karşılık gelen özvektör (Fiedler vektörü) satırındaki negatif ve pozitif değerler farklı gruplar oluşturacak şekilde çizge iki parçaya bölümlenmiştir.

Anahtar Kelimeler

Çizge bölümleme, Çizge teorisi, Çizge görselleştirme.

Kaynakça

• [1] N. Deo, Graph theory with applications to engineering and computer science. Courier Dover Publications,2017.
• [2] A. Kaveh, Structural mechanics: graph and matrix methods. Macmillan International Higher Education,1992, vol. 6.
• [3] J. G. F. Francis, “The QR Transformation A Unitary Analogue to the LR Transformation—Part 1,” The Computer Journal, vol. 4, no. 3, pp. 265–271, Jan. 1961, ISSN: 0010-4620. DOI: 10.1093/comjnl/4.3.265. eprint: https://academic.oup.com/comjnl/article-pdf/4/3/265/1080833/040265.pdf.[Online]. Available: https://doi.org/10.1093/comjnl/4.3.265.
• [4] A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, “Recent advances in graph partitioning,” in Algorithm Engineering: Selected Results and Surveys, L. Kliemann and P. Sanders, Eds. Cham: Springer International Publishing, 2016, pp. 117–158, ISBN: 978-3-319-49487-6. DOI: 10 . 1007 / 978 - 3 - 319 - 49487-6_4. [Online]. Available: https://doi.org/10.1007/978-3-319-49487-6_4.
• [5] B. Hendrickson and R. Leland, “An improved spectral graph partitioning algorithm for mapping parallel computations,” SIAM Journal on Scientific Computing, vol. 16, no. 2, pp. 452–469, 1995. DOI: 10.1137/0916028. eprint: https://doi.org/10.1137/0916028. [Online]. Available: https://doi.org/10.1137/0916028.
• [6] T. Uçkan, C. Hark, E. Seyyarer, and A. Karcı, “Ağırlıklandırılmış çizgelerde tf-idf ve eigen ayrışımı kullanarak metin sınıflandırma,” Bitlis Eren Üniversitesi Fen Bilimleri Dergisi, vol. 8, no. 4, pp. 1349–1362,2019, ISSN: 2147-3129. DOI: 10.17798/bitlisfen.531221.
• [7] R. Merris, “Laplacian matrices of graphs: A survey,” Linear Algebra and its Applications, vol. 197-198, pp. 143–176, 1994, ISSN: 0024-3795. DOI: https : / / doi . org / 10 . 1016 / 0024 - 3795(94 ) 90486 - 3. [Online]. Available: https : / / www . sciencedirect . com / science / article / pii / 0024379594904863.
• [8] A. Gusrialdi and Z. Qu, “Distributed estimation of all the eigenvalues and eigenvectors of matrices associated with strongly connected digraphs,” IEEE Control Systems Letters, vol. 1, no. 2, pp. 328–333, 2017. DOI: 10.1109/LCSYS.2017.2717799.
• [9] R. T. Kobayashi and T. Abrão, “Stability analysis in gram-schmidt qr decomposition,” IET Signal Processing, vol. 10, no. 8, pp. 912–917, 2016. DOI: https://doi.org/10.1049/iet-spr.2016.0123. eprint:https://ietresearch.onlinelibrary.wiley.com/doi/pdf/10.1049/iet- spr.2016.0123.[Online]. Available: https://ietresearch.onlinelibrary.wiley.com/doi/abs/10.1049/iet- spr.2016.0123.
• [10] D. Watkins, “Understanding the qr algorithm, part ii,” SIAM Review, vol. 24, Oct. 1982. DOI: 10.1137/1024100.
• [11] M. Dileo. “Doctor Who dataset.” (), [Online]. Available: https://www.kaggle.com/manueldileo/doctor-who-dataset. (accessed: 06.06.2022).
• [12] M. Bastian, S. Heymann, and M. Jacomy, “Gephi: An open source software for exploring and manipulating networks,” 2009. [Online]. Available: http://www.aaai.org/ocs/index.php/ICWSM/09/paper/view/154.