Büyük grafikler için merkezilik ölçümleri: kesin, yaklaşık ve dağıtılmış algoritmalar

TSAI

İnsanlar arasındaki dostluklar ve nesneler arasındaki benzerlikler gibi varlıklar arasındaki ilişkiler, nesnelerin grafiğin düğümleri (veya köşeleri) olduğu ve kenarların ilgili düğümleri birbirine bağladığı grafikler (veya ağlar) olarak doğal olarak temsil edilebilir. Hem çevrimiçi hem de çevrimdışı sosyal ağlar, Web (birbirine bağlanan web sayfaları ile) ve İnternet (makineler ve yönlendiriciler koleksiyonu olarak) gibi grafiklere iyi bir örnektir.

Bir grafikteki "önemli" düğümleri veya kenarları belirlemek, ekonomi, biyoloji, güvenlik ve sosyoloji gibi alanlarda birçok farklı uygulama ile ağ analizinde temel bir görevdir. Yıllar boyunca, merkezilik endeksleri adı verilen ve önem kavramını farklı şekillerde resmileştiren çeşitli önem ölçüleri önerilmiştir.

Merkeziliği ölçmek

Merkezilik ölçüleri, önemi ölçmek için grafik özelliklerine güvenir. Örneğin, en yaygın kullanılan merkezilik endekslerinden biri olan "aradalık merkeziliği", bir düğümden geçen en kısa yolun kesrini hesaplarken, bir düğümün "yakınlık merkeziliği" diğer düğümlere olan mesafelerinin terslerinin toplamının ortalamasıdır. Google'ın web sayfalarını sıralamak için kullandığı orijinal algoritma olan PageRank bile bir merkezilik ölçüsüdür.

Milyonlarca düğüm ve milyarlarca kenar içeren büyük ağların yaygınlaşmasıyla, merkezilik endekslerini hesaplamak için ölçeklenebilir algoritmalara sahip olmanın önemi giderek artmaktadır. Son zamanlarda, pratikte çok iyi performans gösteren sezgisel yöntemlerden, güçlü olasılıksal garantiler sağlayan yaklaşık algoritmalara ve MapReduce platformları için ölçeklenebilir algoritmalara kadar birçok katkı önerilmiştir.

TSAI Labs, işbirlikçisi ISI Foundation ile birlikte, büyük grafikler için merkezilik ölçüleri oluşturur: kesin, yaklaşık ve dağıtılmış algoritmalar.