Spectral Graph Partitioning Using QR Algorithm - Sülü, Mücahit; Daş, Resul (Fırat University, 2022)
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.

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.
QR Algoritması Kullanarak Spektral Çizge Bölümleme