Karıştırma desenleri - Mixing patterns

Karıştırma desenleri bir ağdaki bir tür düğümün başka bir türe bağlanma eğilimlerine atıfta bulunur. Örneğin, düğümler çok benzer veya çok farklı olan diğerlerine bağlanma eğiliminde olabilir. Bu özellik birçok ülkede yaygındır sosyal ağlar Bazen sosyal olmayan ağlarda da görünse de. Karışım kalıpları ile yakından ilgilidir çeşitlilik; ancak, bu makalenin amaçları doğrultusunda bu terim, topolojik veya sosyolojik gerçek dünya faktörlerine dayalı olarak çeşitli veya dezavantajlı karıştırmaya atıfta bulunmak için kullanılır.

Karışım Modeli Türleri

Karıştırma modelleri, düğümlerin diğer benzer veya farklı düğümlere bağlanma derecesine atıfta bulunarak, tüm ağın bir özelliğidir. Bu nedenle karıştırma, genel olarak tasnif edici veya dezavantajlı olarak sınıflandırılabilir. Karışık karıştırma düğümlerin benzer düğümlere bağlanma eğilimidir. üzücü karıştırma çok farklı düğümlerin bağlı olduğu zıt durumu yakalar.

Açıktır ki, bir çift arasında bir bağlantı oluşturma sürecinde yer alan belirli düğüm özellikleri, bir ağın karıştırma modellerini şekillendirecektir. Örneğin, bir cinsel ilişki ağında, erkek-kadın bağlantılarında bir üstünlük bulunurken, bir arkadaşlık ağında erkek-erkek ve kadın-kadın ağları hakim olabilir. Bu nedenle, farklı düğüm özelliklerinin incelenmesi, ilginç toplulukları veya ağın diğer yapısal özelliklerini ortaya çıkarabilir. Prensipte, bu mülklerden yararlanmak için kullanılan iki tür yöntem vardır. Bunlardan biri, işlev oluşturma teknikleri kullanılarak analitik hesaplamalara dayanmaktadır. Diğeri sayısaldır ve grafik oluşturma için Monte Carlo simülasyonlarına dayanmaktadır.^[1]

Ağlarda örüntüleri karıştırma üzerine yapılan bir çalışmada, M.E.J. Newman, düğüm özelliklerini iki kategoriye ayırarak başlar. Gerçek dünyadaki düğüm özelliklerinin sayısı neredeyse sınırsız olsa da, iki başlık altında olma eğilimindedirler: ayrık ve skaler / topolojik. Aşağıdaki bölümler, kategoriler arasındaki farkları tanımlar ve her birine örnekler sunar. Her kategori için, Newman tarafından sunulan çeşitli karma ağların modelleri kısaca tartışılmıştır.

Ayrık Özelliklere Göre Karıştırma

Bir düğümün ayrık özellikleri kategorik, nominal veya numaralandırıcıdır ve genellikle nitelikseldir. Örneğin, ırk, cinsiyet ve cinsel yönelim genel olarak ayrı özellikler incelenir.

Bir ağın ayrık karakteristikler üzerindeki karışımını ölçmek için, Newman^[1] bir miktar tanımlar ${displaystyle e_ {ij}}$ türdeki düğümleri birbirine bağlayan bir ağdaki kenarların kesri olması ben yazmak j (bkz. Şekil 1). Yönlendirilmemiş bir ağda bu miktar, endekslerinde simetriktir. ${displaystyle e_ {ij} = e_ {ji}}$yönlendirilmiş olanlarda ise asimetrik olabilir. Toplam kurallarını karşılar

${displaystyle toplamı _ {ij} {e_ {ij} = 1}, dörtlü toplam _ {j} {e_ {ij} = a_ {i}}, dörtlü toplam _ {i} {e_ {ij} = b_ {j} }}$,

nerede ${displaystyle a_ {i}}$ ve ${displaystyle b_ {i}}$ türdeki düğümlere eklenen bir kenarın ucunun her türünün kesirleri ${displaystyle i}$. Bir bağlantının uçları arasında fiziksel bir ayrımın olmadığı yönsüz grafiklerde, yani kenarların uçlarının tümü aynı tiptedir, ${displaystyle a_ {i} = b_ {i}}$.

Sonra bir çeşitlilik katsayısı, bir dizi ayrı özellikteki iki düğüm arasındaki benzerliğin veya farklılığın gücünün bir ölçüsü şu şekilde tanımlanabilir:

${displaystyle r = {frac {toplam _ {i} {e_ {ii}} - toplam _ {i} {a_ {i} b_ {i}}} {1-toplam _ {i} {a_ {i} b_ { ben}}}}}$

ile

${displaystyle r_ {min} = - {frac {sum _ {i} {a_ {i} b_ {i}}} {1-sum _ {i} {a_ {i} b_ {i}}}}}$

Bu formül verir ${displaystyle r = 0}$ çeşitlendirici karıştırma olmadığında, çünkü ${displaystyle e_ {ij} = a_ {i} b_ {j}}$ bu durumda ve ${displaystyle r = 1}$ ağ mükemmel bir çeşitlilik arz ettiğinde. Ağ mükemmel bir şekilde olumsuz etkileniyorsa, yani her bağlantı farklı türdeki iki düğümü birbirine bağlıyorsa, o zaman ${displaystyle r = r_ {min}}$genel olarak aralıkta yatan ${displaystyle -1leq r <0}$. Bu aralık ${displaystyle r_ {min}}$ Tamamen olumsuz bir ağın normalde rastgele karıştırılmış bir ağa, mükemmel bir çeşitlilikten daha yakın olduğunu ima eder. Birkaç farklı düğüm türü olduğunda, rastgele karıştırma çoğu zaman düğümlerin aksine eşleşir, böylece ağ çoğunlukla dezavantajlı görünür. Bu nedenle değerin ${displaystyle r = 0}$ rastgele bir ağ için, mükemmel bir şekilde tasnif edici ağ için olduğundan daha yakın olmalıdır.

Fonksiyon üretme yöntemi, ilgilendiğimiz dağılımlar için uygun üretim fonksiyonunu her seferinde bulma ve ağ yapısıyla ilgili verileri farklılaştırarak çıkarma fikrine dayanmaktadır. Derece dağılımının ${displaystyle p_ {k} ^ {(i)}}$ tip düğümler için ${displaystyle i}$ ve matrisin değeri ${displaystyle e_ {ij}}$ (ve dolayısıyla değerleri ${displaystyle a_ {i}}$ ve ${displaystyle b_ {i}}$) biliniyorsa, belirtilen tüm grafiklerin topluluğunu dikkate alabiliriz ${displaystyle p_ {k} ^ {(i)}}$ ve ${displaystyle e_ {ij}}$ kolektif (makroskopik) ağ karakteristikleri elde etmek için. Prensip olarak, oluşturma işlevi ${displaystyle p_ {k} ^ {(i)}}$ ve ilk anı tarafından verilir${displaystyle G_ {0} ^ {(i)} (x_ {1}, ..., x_ {n}) = toplam _ {k} p_ {k} ^ {(i)} x ^ {k}}$, ve${displaystyle G_ {1} ^ {(i)} = {frac {1} {z_ {i}}} {frac {dG_ {0} ^ {(i)}} {dx}} {Bigg |} _ {x = 1}}$,nerede ${displaystyle x_ {i} = {frac {toplam _ {j} e_ {ij} x_ {j}} {toplam _ {j} e_ {ij}}}}$ tip düğüm ${displaystyle i}$ (${displaystyle r_ {i}}$ numarada) ve ${displaystyle z_ {i}}$ bu tür düğümler için ortalama derece. Şimdi ilgilendiğimiz dağıtımlara odaklanıyoruz.

Bir tür düğüme gelen bir ucu takip ederek ulaşılabilen toplam düğüm sayısının dağılımı ${displaystyle i}$ üreten bir işlevi vardır${displaystyle H_ {1} ^ {(i)} (x) = xG_ {1} ^ {(i)} [H_ {1} ^ {(1)} (x), ..., H_ {1} ^ {(n)} (x)]}$. Benzer şekilde, bir noktadan ulaşılabilen düğüm sayısının dağılımı rastgele seçilen düğüm türü ${displaystyle i}$ tarafından üretilir${displaystyle H_ {0} ^ {(i)} (x) = xG_ {0} ^ {(i)} [H_ {1} ^ {(1)} (x), ..., H_ {1} ^ {(n)} (x)]}$. Şimdi ağın bazı özelliklerini verebilecek konumdayız. Ortalama sayı ${displaystyle s_ {i}}$ tipteki bir düğümden ulaşılabilen düğüm sayısı ${displaystyle i}$ dır-dir

${displaystyle s_ {i} = {frac {dH_ {0} ^ {(i)}} {dx}} {Bigg |} _ {x = 1} = 1 + G_ {0} ^ {(i) '} ( 1) {frac {toplam _ {j} e_ {ij} H_ {1} ^ {(i) '} (1)} {toplam _ {j} e_ {ij}}}}$

Ayrıca, eğer ${displaystyle u_ {i}}$ türdeki bir düğümün olasılığıdır ${displaystyle i}$ (grafikte rastgele seçilen bir bağlantıyı takip ederek ulaşılır) dev kümeye ait değil, ardından genel fraksiyon ${displaystyle S}$ Bu kümeyi oluşturan düğümlerin yüzdesi tarafından verilir

${displaystyle S = 1-sum _ {i} {frac {a_ {i}} {z_ {i}}} G_ {0} ^ {(i)} (u_ {1}, ..., u_ {n} )}$

Monte Carlo tekniklerine dayanan sayısal simülasyonlar, yukarıda açıklanan formüllerin sağladığı analitik sonuçlarla uyumlu görünmektedir.

Skaler veya Topolojik Özelliklere Göre Karıştırma

Bir düğümün skaler özellikleri, niceliksel olanlardır. Sayımlar gibi sürekli veya ayrı sıralı değişkenler olabilirler. Yaş, belki de en basit örnektir, ancak zeka ve ham gelir diğer bariz olasılıklardır. Ağın bazı topolojik özellikleri, skaler özelliklerle karıştırmayı incelemek için de kullanılabilir. Spesifik olarak, bir düğümün derecesi, ağların karıştırma modellerinde genellikle oldukça önemli bir özelliktir.^[2] Topolojik skaler özellikler çok kullanışlıdır, çünkü diğer ölçümlerden farklı olarak her zaman kullanılabilirler. Bazen gerçek dünyadaki "sosyallik" için bir vekil olarak kullanılırlar.^[1]

Skaler değişkenlerin çeşitliliğini ölçmek için, ayrı duruma benzer (yukarıya bakınız) bir çeşitlilik katsayısı tanımlanabilir. Standart kullanılarak ölçülebilir Pearson Korelasyonu Newman'ın gösterdiği gibi.^[1] Şekil 2'de, örneğin, Pearson Korelasyon Katsayısının hesaplanması r = 0,574 verir. Bu, evlilik sırasındaki karı-kocanın yaşı arasında oldukça güçlü bir ilişki olduğunu gösterir.

Düğümlerin derecesine göre karışımı ölçmek için alternatif bir katsayı hesaplanabilir. Yeni adam ^[1] olduğu bulunan ifadeyi türetir

${displaystyle r = {frac {toplam _ {jk} jk (e_ {jk} -q_ {j} q_ {k})} {sigma _ {q} ^ {2}}}}$ yönlendirilmemiş bir ağ için. Bu formülde eğer ${displaystyle p_ {k}}$ grafiğin derece dağılımını ifade eder (yani, bir düğümün dereceye sahip olma olasılığı k) sonra ${displaystyle q_ {k} = {frac {(k + 1) p_ {k + 1}} {z}}}$. Bu, aşırı derece bir düğümün veya şu anda incelenenin dışında diğer kenarların sayısı. z ağdaki ortalama dereceyi ifade eder ve ${displaystyle sigma _ {q}}$ dağılımın standart sapmasıdır ${displaystyle q_ {k}}$. Yönlendirilmiş bir ağ için eşdeğer ifade şöyledir:${displaystyle r = {frac {sum _ {jk} jk (e_ {jk} -q_ {j} ^ {in} q_ {k} ^ {out})} {sigma _ {in} sigma _ {out}}} }$.

Bu korelasyon, düğümler dereceye göre çeşitlendiğinde pozitif, ağ olumsuz olduğunda negatiftir. Bu nedenle, ölçü bir ağın karıştırma modellerinin genel bir anlamını yakalar. Bu konunun daha derinlemesine bir analizi için şu makaleye bakın: çeşitlilik.

İşlev oluşturma yöntemi bu durum için de geçerlidir, ancak hesaplanacak işlevler nadiren kapalı biçimde hesaplanabilir. Bu nedenle, sayısal simülasyonlar ilgi çekici sonuçlar vermenin tek yolu gibi görünüyor. Kullanılan teknik bir kez daha Monte Carlo'dur. Ağlar için Güç yasası derece dağılımı ${displaystyle p_ {k} sim k ^ {- au}}$, ${displaystyle q_ {k}}$ farklı bir ortalamaya sahiptir. ${displaystyle au> 3}$, ki bu nadiren olur.^[3] Bunun yerine, katlanarak kesilmiş güç yasası dağılımı${displaystyle p_ {k} = {frac {k ^ {- au} mathrm {e} ^ {- k / kappa}} {mathrm {Li} _ {au} (mathrm {e} ^ {- 1 / kappa}) }} mathrm {for} kgeq 1}$ tipin fazla derecesi için bir dağılım verir ${displaystyle q_ {k} sim (k + 1) ^ {1- au} mathrm {e} ^ {- (k + 1) / kappa}}$. Bu vakanın sonuçları aşağıda özetlenmiştir.

1) Dev bir kümenin göründüğü faz geçişinin konumu, daha yüksek değerlere hareket eder. ${displaystyle kappa}$ değeri olarak ${displaystyle r}$ azalır. Yani, bir ağ ne kadar çeşitli olursa, dev kümenin görünümü için kenar yoğunluğu eşiği o kadar düşük olacaktır.

2) Büyük sınırdaki dev kümenin boyutu ${displaystyle kappa}$ çeşitlilik açısından karışık grafik için nötr ve dezavantajlı olanlardan daha küçüktür.

3) Ağdaki çeşitlilik karışımı, ağın sağlamlığı düğüm kaldırma altında. Asortatif ağlar için, dev kümeyi yok etmek için normalden yaklaşık on kat daha fazla yüksek dereceli düğümleri kaldırmak gerekir (normal olarak nötr bir ağ anlamına gelir), bunun tersi, olumsuzluk yaratan ağlar için doğrudur, yani bunlar, altında nötr olanlardan daha hassastırlar. yüksek dereceli düğümlerin kaldırılması.

Ağın sağlamlığının düğüm karışımına bağımlı olmasının büyüleyici sonucu şu şekilde açıklanabilir. Tanımlarına göre, çeşitli ağlardaki yüksek dereceli düğümler, aralarında bir çekirdek grup oluşturma eğilimindedir. Böyle bir çekirdek grup, tüm açık hedef düğümleri grafiğin bir bölümünde bir araya toplayarak ağa sağlamlık sağlar. Bu yüksek dereceli düğümleri kaldırmak hala ağ bağlantısını yok etmenin en etkili yollarından biridir, ancak daha az etkilidir (nötr ağlara kıyasla) çünkü hepsini grafiğin aynı bölümünden kaldırarak diğer bölümlere saldırmayı başaramayız. Bu diğer kısımların kendileri süzülüyorsa, en yüksek dereceli düğümler yok olsalar bile dev bir küme varlığını sürdürecektir. Öte yandan, rahatsız edici bir şekilde karma ağ, özellikle yüksek dereceli düğümlerin kaldırılmasına karşı hassastır çünkü bu düğümler ağın her tarafına dağılmış durumdadır, böylece onlara saldırmak, ağın tüm bölümlerine aynı anda saldırmak gibidir.

Örnekler ve Uygulamalar

Karıştırma modellerinin yaygın bir uygulaması, hastalık geçişinin incelenmesidir. Örneğin, birçok çalışma HIV / AIDS ve diğer bulaşıcı hastalıkların yayılmasını incelemek için karıştırmayı kullandı.^[4][5][6] Bu makaleler, Karıştırma modelleri ile hastalığın yayılma hızı arasında güçlü bir bağlantı bulmaktadır. Bulgular, gerçek dünyadaki ağ büyümesini modellemek için de kullanılabilir.^[7] veya ağlar içindeki toplulukları bulun.

Referanslar