ArticleRank algoritmasına C# ile bakalım

ArticleRank hem adıyla hem de çalışma mantığı ile daha önce baktığımız PageRank algoritmasına oldukça benzemektedir. Özünde dergi makalelerinin önemini tayin etmek için geliştirilmiştir. Düşük dereceli düğümlerin etkilerini azaltmak için paydaya ağa göre hesaplanan (dış bağlantı adetlerinin ortalaması) sabit bir değer ekler. Haliyle, formülümüz de oldukça benzer olacaktır.

\operatorname{ArticleRank}_i(v)=(1-d)+d \sum_{w \in N_{\text {in }}(v)} \frac{\operatorname{ArticleRank}_{i-1}(w)}{\left|N_{\text {out }}(w)\right|+\overline{N_{\text {out }}}}

Bahsettiğim gibi bu formülün PageRank'dan tek farkı, bölme ,işlemi sırasında paydada toplanan $$ \overline{N_{\text {out }}} $$ değeri. Bu da ortalama dış bağlantı sayısı anlamına geliyor.

Kullanacağımız veri PageRank ile aynı olsun:

        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 })
        };

Kodumuzu da küçük değişiklikler ile uyarlarsak.

public static Dictionary<Person, double> ArticleRank(Person[] people, double dampingFactor = 0.8, int maxIterations = 1)
    {
        const double exitThreshold = 0.001;
        var meanOut = people.Average(x => x.Following.Count);
        var result = people.ToDictionary(x => x, _ => 1.0);
        var damping = (1.0 - dampingFactor);
        var peopleDictionary = people.ToDictionary(x => x.Id, x => x);

        for (var iteration = 0; iteration < maxIterations; iteration++){
            double currentSum = 0;
            foreach (var person in people){
                var sum = person
                    .Followers
                    .Select(x => peopleDictionary[x])
                    .Sum(x => result[x] / (x.Following.Count + meanOut));
                result[person] = damping + dampingFactor * sum;
                currentSum += result[person];
            }
            if (Math.Abs(currentSum - 1) < exitThreshold){
                Console.WriteLine($"Converged after {iteration} iterations");
                break;
            }
        }
        return result;
    }

İşlemler PageRank ile aynı,

1. Bir yaklaşma eşiği berlirtiyorum. Şayet sonuç kümesinin toplamı 1'den 0.001 uzaklıktan daha yakın olursa benim için yeterlidir.
2. Sonuç sözlüğünü (kümesini) hazırlıyorum. Her kişi için başlangıç PageRank değerini 1 veriyorum.
3. Tekrar tekrar yapılacak sönümle işleminin bir parçasını önceden hesaplayıp bir kenara koyuyorum. Bölme işlemi yapmadığıma dikkat edin!
4. Takip edilen ve takipçi bilgilerini Id üzerinden referanslamıştım, her iterasyonda tekrar tekrar kişileri bulmamak adına Id->Person şeklinde bir index oluşturuyorum.
5. Sonuca yaklaşmasa bile belirli bir maksimum deneme sayına kadar deneme yapılması için basit bir for döngüsü kuruyorum
6. Mevcut iterasyonun toplam değeri
7. Herkesi sırayla dön
8. Takip edenler için AR değerini hesapla ve bunu takip edenin takip ettiği kişi sayısı ile ortalama dış bağlantı adedinin toplamına böl
9. Sönümleme ve normalizasyon işlemleri
10. Toplamı güncelle
11. Toplamın 1 e ne kadar uzak olduğına bak, yeterince yakınsa yeni bir iterasyonu gerek yok.
12. Sonucu dön

Sonucumuz:

Ali : 0,3739130434782608
Berk : 0,4889632107023411
Cem : 0,42222222222222217
Doruk : 0,5811222593831289
Erkan : 0,4795884985405609