Hiperbolik geometrik grafik - Hyperbolic geometric graph

Ağ bilimi
Teori
Grafik Karmaşık ağ Bulaşma Küçük dünya Ölçeksiz Topluluk yapısı Süzülme Evrim Kontrol edilebilirlik Grafik çizimi Sosyal sermaye Bağlantı analizi Optimizasyon Mütekabiliyet Kapanış Homofilik Geçişlilik Tercihli ek Denge teorisi Ağ etkisi Sosyal etki
Ağ türleri
Bilgilendirici (bilgi işlem) Telekomünikasyon Ulaşım Sosyal Bilimsel işbirliği Biyolojik Yapay sinir Birbirine bağımlı Anlamsal Mekansal Bağımlılık Akış Çip üzerinde
Grafikler
Özellikleri Clique Bileşen Kesmek Döngü Veri yapısı Kenar Döngü Semt Yol Köşe Bitişiklik listesi  / matris Sıklık listesi  / matris Türler Bipartit Tamamlayınız Yönetmen Aşırı Çok Rastgele Ağırlıklı
Metrikler Algoritmalar
Merkeziyet Derece Motif Kümeleme Derece dağılımı Çeşitlilik Mesafe Modülerlik Verimlilik
Modeller
Topoloji Rastgele grafik Erdős – Rényi Barabási-Albert Spor modeli Watt-Strogatz Üstel rastgele (ERGM) Rastgele geometrik (RGG) Hiperbolik (HGN) Hiyerarşik Stokastik blok Maksimum entropi Yumuşak konfigürasyon LFR Benchmark Dinamikler Boole ağı ajan tabanlı Salgın / SIR
Listeler Kategoriler
Konular Yazılım Ağ bilimcileri Kategori: Ağ teorisi Kategori: Grafik teorisi
v t e

Bir hiperbolik geometrik grafik (HGG) ya da hiperbolik geometrik ağ (HGN) özel bir türü olan uzamsal ağ düğümlerinin (1) birtakım latent koordinatlar göre serpiştirilir olasılık yoğunluk fonksiyonunun bir içine hiperbolik alan bir sürekli negatif eğrilik ve (2) bir İki düğüm arasındaki kenar , metriğin bir fonksiyonuna göre yakınsa mevcuttur (tipik olarak ya belirli bir eşik mesafesinden daha yakın köşeler arasında deterministik bağlantılarla sonuçlanan bir Heaviside adım fonksiyonu veya bağlantı olasılığını veren hiperbolik mesafenin zayıflama fonksiyonu). Bir HGG , gömme alanı Öklid olan rastgele bir geometrik grafiği (RGG) genelleştirir .

Matematiksel formülasyon

Matematiksel olarak, bir HGG a, grafik bir köşe ile ayar V ( önem düzeyi ) ve bir kenar seti E 2-boyutlu hiperbolik alanı üzerine yerleştirilir noktaları olarak düğümler ile inşa sürekli negatif Gauss eğriliği , ve bu yarıçap kesme , örneğin yarıçap arasında Poincare diskin bir kullanılarak görüntülenebilir hiperboloit modeli . Her noktanın ve ile hiperbolik kutupsal koordinatları vardır . ${\ displaystyle G (V, E)}$ ${\ displaystyle N = | V |}$${\ displaystyle \ mathbb {H} _ {\ zeta} ^ {2}}$${\ displaystyle - \ zeta ^ {2}}$${\ displaystyle R}$${\ displaystyle i}$${\ displaystyle (r_ {i}, \ theta _ {i})}$${\ displaystyle 0 \ leq r_ {i} \ leq R}$${\ displaystyle 0 \ leq \ theta _ {i} <2 \ pi}$

Hiperbolik kosinüs yasası mesafeyi ölçmek sağlar iki nokta arasındaki ve , ${\ displaystyle d_ {ij}}$${\ displaystyle i}$${\ displaystyle j}$

${\ displaystyle \ cosh (\ zeta d_ {ij}) = \ cosh (\ zeta r_ {i}) \ cosh (\ zeta r_ {j})}$${\ displaystyle - \ sinh (\ zeta r_ {i}) \ sinh (\ zeta r_ {j}) \ cos {\ bigg (} \ underbrace {\ pi \! - \! {\ bigg |} \ pi - | \ theta _ {i} \! - \! \ theta _ {j} | {\ bigg |}} _ {\ Delta} {\ bigg)}.}$

Açı  , iki konum vektörü arasındaki (en küçük) açıdır . ${\ displaystyle \ Delta}$

En basit durumda, bir kenar (ancak ve ancak) iki düğüm, belirli bir mesafede olan IFF kurulur mahalle yarıçapı , bir etkisi eşiğine, bu karşılık gelir. ${\ displaystyle (i, j)}$ ${\ displaystyle r}$${\ displaystyle d_ {ij} \ leq r}$

Bağlantı zayıflama işlevi

Genelde mesafeye bağlı bir olasılıkla bağlantı kurulacaktır  . Bir bağlantı bozunma fonksiyonu mesafede düğüm bir çift bir kenar atama olasılığını temsil eder . Bu çerçevede, rastgele geometrik grafiklerde olduğu gibi basit bir sabit kod komşuluğu durumu, kesme zayıflama işlevi olarak adlandırılır . ${\ displaystyle d_ {ij}}$ ${\ displaystyle \ gamma (s): \ mathbb {R} ^ {+} \ ila [0,1]}$${\ displaystyle s}$

Hiperbolik geometrik grafikler oluşturma

Krioukov vd. yarıçaplı bir disk üzerinde eşit olarak rasgele düğüm dağılımına sahip hiperbolik geometrik grafikler (aynı zamanda genel versiyonları) oluşturmak üzere açıklanmıştır olarak . Bu grafikler , düğüm dereceleri için bir güç yasası dağılımı verir. Her noktanın / düğümün açısal koordinatı , rastgele rastgele seçilirken, radyal koordinat r için yoğunluk fonksiyonu, olasılık dağılımına göre seçilir : ${\ displaystyle R}$${\ displaystyle \ mathbb {H} _ {\ zeta} ^ {2}}$${\ displaystyle \ theta}$${\ displaystyle [0,2 \ pi]}$ ${\ displaystyle \ rho}$

${\ displaystyle \ rho (r) = \ alpha {\ frac {\ sinh (\ alpha r)} {\ cosh (\ alpha R) -1}}}$

Büyüme parametresi dağılımı kontrol eder: Çünkü dağılım tek tiptir , daha küçük değerler için düğümler diskin merkezine doğru ve daha büyük değerler için daha sınıra doğru dağıtılır. Bu modelde, düğümler arasında kenarları ve IFF mevcut ya da olasılıkla daha genel bir bağlantı bozunma fonksiyonu kullanılırsa. Ortalama derece, hiperbolik diskin yarıçapı tarafından kontrol edilir . Düğüm dereceleri için üslü bir güç yasası dağılımını izlediği gösterilebilir . ${\ displaystyle \ alpha> 0}$${\ displaystyle \ alpha = \ zeta}$${\ displaystyle \ mathbb {H} _ {\ zeta} ^ {2}}$${\ displaystyle u}$${\ displaystyle v}$${\ displaystyle d_ {uv} <R}$${\ displaystyle \ gama (d_ {uv})}$${\ displaystyle R}$${\ displaystyle \ alpha / \ zeta> 1/2}$${\ displaystyle \ gamma = 1 + 2 \ alpha / \ zeta}$

Görüntü rastgele farklı değerleri için grafikleri oluşturulur tasvir ederken ve de . Düğümlerin dağılımı ve grafiğin bağlanabilirliği üzerinde nasıl bir etkiye sahip olduğu görülebilir . Uzaklık değişkenlerinin gerçek hiperbolik değerlerine sahip olduğu yerel temsil, grafiğin görselleştirilmesi için kullanılır, bu nedenle kenarlar düz çizgilerdir. ${\ displaystyle \ alpha}$${\ displaystyle R}$${\ displaystyle \ mathbb {H} _ {1} ^ {2}}$${\ displaystyle \ alpha}$${\ displaystyle R}$

Her biri farklı alfa ve R değerleri için N = 100 düğümlü rastgele hiperbolik geometrik grafikler

İkinci dereceden karmaşıklık üreteci

Hiperbolik geometrik grafiklerin oluşturulması için naif algoritma, her noktanın açısal ve radyal koordinatlarını seçerek hiperbolik disk üzerindeki düğümleri dağıtır ve rastgele örneklenir. Her düğüm çifti için, ilgili mesafelerinin bağlantı zayıflama fonksiyonunun değerinin olasılığı ile birlikte bir kenar eklenir. Sözde kod aşağıdaki gibi görünür:

${\displaystyle V=\{\},E=\{\}}$
for ${\displaystyle i\gets 0}$ to ${\displaystyle N-1}$ do
    ${\displaystyle \theta \gets U[0,2\pi ]}$
    ${\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}$
    ${\displaystyle V=V\cup \{(r,\theta )\}}$
for every pair  ${\displaystyle (u,v)\in V\times V,u\neq v}$ do
    if ${\displaystyle U[0,1]\leq \gamma (d_{uv})}$ then
        ${\displaystyle E=E\cup \{(u,v)\}}$
return ${\displaystyle V,E}$

${\ displaystyle N}$ Üretilecek düğüm sayısıdır, olasılık yoğunluk fonksiyonu ile radyal koordinatın dağılımı ters dönüşüm örneklemesi kullanılarak elde edilir . verilen aralıktaki bir değerin tek tip örneklemesini gösterir. Algoritma tüm düğüm çiftleri için kenarları kontrol ettiğinden, çalışma zamanı ikinci dereceden yapılır. Büyük olduğu uygulamalar için bu artık geçerli değildir ve alt kuadratik çalışma süresine sahip algoritmalara ihtiyaç vardır. ${\ displaystyle \ rho}$${\ displaystyle U}$${\ displaystyle N}$

Alt karesel nesil

Düğümlerin her çifti arasındaki kenarlar için kontrol önlemek için, modern bir jeneratör ek kullanmak veri yapıları bu bölüme bantlar halinde grafik. Bunun görselleştirilmesi, bantların sınırlarının turuncu ile çizildiği hiperbolik bir grafiği göstermektedir. Bu durumda, bölümleme radyal eksen boyunca yapılır. Noktalar, kendi bantlarında açısal koordinatlarına göre sıralanarak saklanır. Her nokta için , hiperbolik yarıçap çemberinin sınırları (fazla) tahmin edilebilir ve yalnızca çemberle kesişen bir bantta bulunan noktaların kenar kontrolünü gerçekleştirmek için kullanılabilir. Ek olarak, her bir bant içindeki sıralama, yalnızca açısal koordinatları aşağıdakilerden biri etrafında belirli bir aralıkta bulunan noktaları dikkate alarak bakılacak noktaların sayısını daha da azaltmak için kullanılabilir (bu aralık, etrafındaki hiperbolik çemberin fazla tahmin edilmesiyle de hesaplanır. ). ${\ displaystyle u}$${\ displaystyle R}$${\ displaystyle u}$${\ displaystyle u}$

Bu ve algoritmanın diğer uzantılarını kullanarak, zaman karmaşıklıkları ( düğüm sayısı ve kenar sayısı nerede ) yüksek olasılıkla mümkündür. ${\ displaystyle {\ mathcal {O}} (n \ log \ log n + m)}$${\ displaystyle n}$${\ displaystyle m}$

Hiperbolik grafik, her biri yaklaşık olarak aynı sayıda noktayı tutacak şekilde bantlara bölünmüştür.

Bulgular

İçin (Gauss eğriliği ), HGGs bir formu ensemble ifade etmek mümkün olduğu için ağlar derecesi dağılımını kapalı form olarak analitik için sınırlayıcı durumda düğüm çok sayıda. Bu, birçok grafik topluluğu için geçerli olmadığından bahsetmeye değer. ${\ displaystyle \ zeta = 1}$${\ displaystyle K = -1}$

Başvurular

HGG'ler , hiperbolikliğin bir bireyin benzerliği ve popülerliği arasındaki rekabet yoluyla ortaya çıktığı sosyal ağlar için umut verici bir model olarak önerilmiştir .

Referanslar