Ağları incelemeye devam ediyoruz. PageRank ve ArticleRank'den sonraki algoritmamız Eigenvector Centrality ya da Özvektör Merkezliliği olacak. Tıpkı ArticleRank'de olduğu gibi temel mantık PageRank ile oldukça benzer olacak. Tabii öncesinde kısaca özvektörleri ve öz değerleri hatırlamak gerekebilir. Doğrusal cebir'in bu eğlenceli konusu bir çok problemin çözümünde de anahtar rol oynamaktadır. Ana konudan çıkmamak adına öz vektör ve değerleri detaya inmeden hızlıca hatırlatacağım.
A * v = \lambda * vBurada A herhangi bir kare matris, v özvektörlerimizden birisi, lambda ise ise özdeğerlerimizden birisini oluşturuyor. Dikkat ederseniz her ikisi için de çoğul bir ifade kullandım zira A yerine koyacağımız bir kare matris için birden fazla değer/vektör elde edebiliriz. Böyle bir problemi çözmek için denklemi 0'a eşitleyerek başlayabiliriz.
A*v - \lambda * v = 0 \\
(A-\lambda) * v = 0Bir matrisden sabit bir sayı çıkmayacağı için lambda değerini A ile aynı boyuttaki birim matris ile çarpıyoruz.
(A * \lambda I) * v = 0Lambda değerini bulmak içinde v yi kaldırıp sol tarafın determinantını almak yetiyor.
|A * \lambda I|= 0Her şeyi yerine koyduğumuzda bir çok değer ve vektör bulacağız ama bizi ilgilendiren bunların en büyüğü (öz değer) olacak.
Bu vektörü MathNet kütüphanesi kullanarak hızlı bir şekilde bulabilirsiniz. Fakat, ben hazırını göstermeyi sevmediğim için bu değerleri kod yardımıyla bulacağım. Kod yardımıyla en büyük özdeğere karşılık gelen özvektörü bulmak için Power Iteration algoritmasını kullanacağınız. Bu algoritmanın özelliği en büyük öz değer için geçerli olan öz vektörlerden birisine doğru giderek yaklaşmasıdır. Aşağıdaki versiyonunda çıkan sonuç en büyük öz değere karşı oluşan öz vektörün normalize edilmiş halini bulmak için yeterlidir.
private static double[] PowerIteration(double[,] matrix, int maxIterations = 33)
{
var n = matrix.GetLength(0);
var vector = Enumerable.Range(0, n).Select(static _ => Random.Shared.NextDouble()).ToArray();
for (var iteration = 0; iteration < maxIterations; iteration++){
var newVector = MultiplyMatrixByVector(matrix, vector);
newVector = NormalizeVector(newVector);
vector = newVector;
}
return vector;
}Bu kodu açıklayalım:
- Rastgele bir vektör oluşturarak başlıyoruz. İsterseniz tümü 1olan veya istediğiniz bir vektör ile başlayabilirsiniz.
- Belirlediğimiz iterasyon sayısı kadar ilerliyoruz. Arttırdıkça gerçek değere daha fazla yaklaşırken bir o kadar yavaşlayacağından ihtiyaca yönelik tatlı bir nokta seçebilirsiniz.
- Vektörümüzü matrisimiz ile çarpıyoruz
- Çarpma işleminden sonra çıkan vektör iterasyonlar boyunca büyüyebileceğinden vektörü normalize ediyoruz (uzunluğunu 1 e getiriyoruz)
Tüm işlem bu kadar, fakat performans için bir kaç oyun yapabiliriz. Yapacağımız cinlik, şayet yaklaşma miktarı çok ama çok küçükse boşu boşuna deneme yapmasını engellemek olacak.
Bunu uygularsak döngü kısmımız şu hale gelecektir,
for (var iteration = 0; iteration < maxIterations; iteration++){
var newVector = MultiplyMatrixByVector(matrix, vector);
newVector = NormalizeVector(newVector);
if (newVector.Zip(vector).Sum(v => Math.Abs(v.First - v.Second)) < 0.0000001){
vector = newVector;
break;
}
vector = newVector;
}Sonuca ulaşmanın Inverse Vector Iteration (Gauss Eliminasyonu) gibi yöntemleri de bulunuyor, bunlar donanımsal hızlandırmalar ile daha iyi hale de getirilebilir. Fakat bizim tüm amacımız merkezi bulmak. Yukarıdaki fonksiyonun kullandığı diğer fonksiyonları da şuraya ekleyeyim:
private static double[] MultiplyMatrixByVector(double[,] matrix, double[] vector)
{
var rows = matrix.GetLength(0);
var cols = matrix.GetLength(1);
var result = new double[rows];
for (var i = 0; i < rows; i++){
for (var j = 0; j < cols; j++){
result[i] += matrix[i, j] * vector[j];
}
}
return result;
}
private static double VectorNorm(double[] vector)
{
return Math.Sqrt(vector.Sum(static t => t * t));
}
private static double[] NormalizeVector(double[] vector)
{
var norm = VectorNorm(vector);
return vector.Select(c => c / norm).ToArray();
}Buradan sonra yapacaklarımız için önce örnek teşkil etmesi açısından PageRank'da kullandığımız değerleri alalım.
public record Person(int Id, string Name, HashSet<int> Followers, HashSet<int> Following);
Person[] people =
{
new(0, "Ali", new() { 2 }, new() { 1 }),
new(1, "Berk", new() { 0, 2 }, new() { 4 }),
new(2, "Cem", new() { 3 }, new() { 0, 1, 3 }),
new(3, "Doruk", new() { 2, 4 }, new() { 2, 4 }),
new(4, "Erkan", new() { 1, 3 }, new() { 3 })
};Şimdi bu veriyi bir kare matris haline çevirecek bir fonksiyon yazalım.
private static double[,] GetAdjacencyMatrix(Person[] people)
{
var n = people.Length;
var matrix = new double[n, n];
for (var i = 0; i < n; i++){
for (var j = 0; j < n; j++){
matrix[i, j] = people[i].Following.Contains(people[j].Id) ? 1 : 0;
}
}
return matrix;
}Matrisimiz şöyle görünecek:
\begin{matrix}
- & A & B & C& D& E \\
A & 0 & 1 & 0 & 0 & 0 \\
B & 0 & 0 & 0 & 0 & 1 \\
C & 1 & 1 & 0 & 1 & 0 \\
D & 0 & 0 & 1 & 0 & 1 \\
E & 0 & 0 & 0 & 1 & 0
\end{matrix}Daha sonra tek yapmamız gereken bu matrisin öz vektörünü bulmak olacak.
var matrix = GetAdjacencyMatrix(people);
var eigenVector = PowerIteration(matrix);
for (var index = 0; index < eigenVector.Length; index++){
var person = people[index];
var t = eigenVector[index];
Console.WriteLine($"{person.Name} : {t}");
}Bunu ekrana bastığımızdaki sonuç ise:
Ali : 0,14686729300051407
Berk : 0,23763628496766961
Cem : 0,6221398443185082
Doruk : 0,6221398680880599
Erkan : 0,3845035669017643Sıralama olarak PageRank ve ArticleRank'e benzer sonuçlar elde ettiğimizi göreceksiniz. PageRank'de benzer şekilde matrisler ve öz vektörler ile hesaplanabilmektedir.
Bir iki okumalık bırakıyorum.
https://www.ahmeddemir.net/wp-content/uploads/2016/02/Gaussian.pdf
https://people.inf.ethz.ch/arbenz/ewp/Lnotes/chapter7.pdf
