Düğüm benzerliğine dayalı, yönlendirilmiş bir ağ topluluğu algılama algoritması
Wang Lin, Zhang Yifan
(Otomasyon ve Bilgi Mühendisliği Okulu, Xi'an Teknoloji Üniversitesi, Xi'an, Shaanxi 710048)
: Mevcut topluluk algılama algoritmalarının düşük doğruluğu ve yönlendirilmiş ağların yön özelliklerinin yetersiz değerlendirilmesi sorunlarına yönelik olarak, yönlendirilmiş ağlar için uygun geliştirilmiş bir CNM (Newman açgözlü algoritma) topluluk algılama algoritması önerilmiştir. Algoritma tasarımında, topolojik yapı bilgisine dayanan yönlendirilmiş bir ağ düğümü benzerliği algoritması tanıtılmış ve modülerlik artış fonksiyonu Qs yeniden tanımlanmıştır. Algoritma, bilgisayar tarafından oluşturulan bir ağ ve iki gerçek ağ kullanılarak test edildi ve mevcut algoritmalarla karşılaştırıldı. Deneysel sonuçlar, makalede önerilen algoritmanın yönlendirilen ağdaki topluluk yapısını etkili bir şekilde tespit edebildiğini göstermektedir.
: Topluluk algılama; yönlendirilmiş ağ; CNM algoritması; düğüm benzerliği
: TP301.6 Belge tanımlama kodu: ADII: 10.19358 / j.issn.1674-7720.2017.03.006
Alıntı biçimi Wang Lin, Zhang Yifan. Düğüm benzerliğine dayalı yönlendirilmiş bir ağ topluluğu algılama algoritması J. Mikrobilgisayar ve Uygulama, 2017, 36 (3): 19-22.
0 Önsöz
Topluluk algılama, karmaşık ağların yapısını ve işlevsel özelliklerini incelemek için en temel görevdir. Bir topluluk, ağda benzer özniteliklere veya benzer rollere sahip düğümlerin bir koleksiyonu olarak kabul edilebilir. Bu topluluklar içindeki düğümler genellikle yakından bağlantılıdır, topluluklar arasındaki düğüm bağlantıları ise nispeten seyrektir. Ağdaki gizli topluluk yapısını keşfetmek için, geleneksel topluluk algılama algoritması temel olarak topluluk algılama problemini bir optimizasyon problemine dönüştüren ve ardından klasik GN algoritması [1] ve Newman gibi en iyi hedef işlevine sahip topluluk yapısını arayan modülerlik indeksine dayanır. Hızlı algoritma [2]. Bununla birlikte, bu tür algoritmanın kendisinin sınırlamaları vardır [3] ve yukarıdaki algoritma, karmaşık ağların yön özelliklerini ve düğümlerin benzerlik özelliklerini hesaba katmaz. Bir yandan, gerçek dünyadaki karmaşık ağlarda, sosyal ağlardaki takip ilişkileri gibi bağlantı ilişkileri her zaman yönlendirilmezken, diğer yandan karmaşık ağlardaki farklı düğümlerin farklı benzerlikleri ve benzerlikleri vardır. Düğümler arasındaki ilişkinin yakınlığını yansıtır.
Modülerlik optimizasyonuna [1,2,4] dayanan geleneksel yönteme ek olarak, mevcut topluluk algılama algoritmaları ayrıca düğümlerin benzerliğini ve ağın yön özelliklerini dikkate alan algoritmaları da içerir. Literatür [5], modülerlik indeksine dayalı bir Benzerlik-CNM algoritması önerdi ve düğüm benzerliğini dikkate aldı ve CNM algoritmasındaki modülerlik artış değerinin artan yönünün büyük ölçekli topluluklar olma eğiliminde olduğuna ve küçük ölçekli olanları göz ardı ettiğine işaret etti. Topluluk, ancak, bu algoritma yalnızca yönlendirilmemiş ağ topluluklarını algılar ve yönlendirilmiş ağları işleyemez. Yönlendirilmiş ağın daha gerçekçi ağını göz önünde bulundurarak, literatür [6], yönlendirilmiş ağı yönlendirilmemiş bir ağa simetrik hale getirmek için yerel bilgiye dayalı benzerlik hesaplama yöntemini kullanır ve ardından bölmek için geleneksel yönlendirilmemiş ağ topluluğu algılama algoritmasını kullanır. Topluluk, ancak bu yönlendirilmemiş yöntem, yönlendirilen ağın topolojisini yok eder. Gerçek bir yönlendirilmiş ağ-Weibo sosyal ağına dayanan literatür [7], ortak ilgiye ve ortak hayranlara dayalı bir Weibo kullanıcı benzerliği önerdi, bu temelde, Newman hızlı algoritmasını kullanarak yeni bir modülerlik işlevi tanımladı Topluluk testi yapma fikri. Literatür [8], k-Path topluluk topluluğunun mahalle benzerliği kavramını ve hesaplama yöntemini önermiş ve yönlendirilmiş ağın topluluk algılama sorununu, yönlendirilmemiş ağırlıklı ağın topluluk algılama sorununa dönüştürmüştür.
Özetle, topluluk algılamanın temel fikri, modülerliğe dayalı optimizasyon algoritmasının sınırlamaları ve ağın yönlü etkileşimi göz önünde bulundurularak, benzer özelliklere veya rollere sahip düğümleri aynı sete bölmek olduğundan, bu makale CNM algoritmasına dayalı bir yöntem önermektedir. Yönlendirilmiş ağlar için bir topluluk algılama algoritması. Yönlendirilmiş ağ topolojisine dayalı benzerlik algoritması, düğüm benzerliğini hesaplamak için kullanılır ve daha sonra benzerlik, CNM algoritmasının açgözlü fikrinin ve modülerlik algoritmasının sınırlamalarının neden olduğu topluluk bölünmesinin eksikliğinin etkin bir şekilde üstesinden gelen modülerlik artış işlevini geliştirmek için kullanılır. Doğru dezavantajlar.
1 İlgili teoriler ve algoritmalar
1.1 SimRank algoritması
SimRank [9], herhangi iki nesne arasındaki benzerlik derecesini ölçmek için grafik topolojisi bilgisine dayalı yönlendirilmiş bir grafiktir. Modelin ana fikri şudur: iki nesneye benzer nesneler tarafından referans veriliyorsa, o zaman bu İki nesne de benzerdir. SimRank'in temel formülü:
Bunlar arasında, | I (v) | v düğümünün derecesini, Ii (v) v'nin i-inci gelen komşu düğümünü, c zayıflatma faktörü ve c (0,1) 'i temsil eder.
SimRank için yinelemeli denklem (1) sonunda sabit bir değere yinelenebilir. SimRank'i hesaplamak için aşağıdaki yinelemeli yöntem kullanılır:
1.2CNM algoritması
Topluluk algılamanın verimliliğini artırmak ve hesaplama karmaşıklığını azaltmak için Clauset ve diğerleri, ağın modülerliğini hesaplamak ve güncellemek için yığının veri yapısını kullandılar ve yeni bir açgözlü algoritma olan CNM algoritmasını önerdiler [4]. Algoritmanın karmaşıklığı Derecesi yalnızca doğrusal karmaşıklığa yakın olan O (nlog2n) 'dir.
CNM algoritması önce modülerlik artış matrisi Qi, j oluşturur ve ardından modülerlik maksimum olduğunda bir topluluk yapısı elde etmek için öğelerini günceller. Algoritma akışı şu şekildedir: (1) Bir topluluk olarak ağdaki her düğümü başlatın; (2) Ağ birleşimindeki herhangi iki topluluktan sonra modülerlik artışını hesaplayın Qi, j; (3) açgözlülükle en büyük Qi, j'yi seçin İki topluluk aynı anda birleştirilir, yeni topluluğa bağlı tüm toplulukların veri yapısı güncellenir ve önceki adım tekrarlanır; (4) Qi, j < 0'da algoritma sona erer.
1.3 Yönlendirilmiş ağın modülerliği
Topluluk tespitinin kalitesini ölçmek için Newman ve Girvan, ağdaki toplulukları nicel olarak tanımlamak ve ağ topluluk yapısının bölünmesini ölçmek için bir modülerlik işlevi tanımladı. Yönlendirilmiş ağların yön özelliklerini hesaba katan Leicht ve Newman [10], aşağıdaki şekilde tanımlanan yönlendirilmiş ağlar için uygun bir modülerlik fonksiyonu Qd önermiştir:
Yönlendirilmiş ağın modülerliğinden farklı olarak, Aij yönlendirilmiş ağın bitişik matrisini temsil eder ve kini ve koutj sırasıyla düğümün derece ve dış derecesini temsil eder.
2 Benzerliğe dayalı yönlendirilmiş ağ topluluğu algılama algoritması
Bu yazıda algoritmanın temel fikri, modülerlik artışını değiştirmek için düğümler arasındaki benzerlik değişikliğini kullanmaktır Birleştirme kuralı hala CNM algoritmasının birleştirme kuralını benimser ve son olarak benzerliğe dayalı birkaç topluluk elde edilir.
Eij ve ai değişkenlerini şu şekilde yeniden tanımlayın:
Aşağıdaki gibi tanımlanan modülerlik artışından sonra artış matrisini değiştirmek için SimRank benzerliğini kullanın:
Bunlar arasında, n, ağdaki toplam düğüm sayısıdır, s (i, j), i ve j düğümleri arasındaki SimRank benzerlik değeridir, Ds (i), i düğümü ve diğer düğümler arasındaki benzerliğin toplamıdır ve M tümüdür Düğüm benzerliğinin toplamı.
Algoritma adımları aşağıdaki gibidir:
Giriş: yönlendirilmiş ağ G (V, E);
Çıktı: topluluğun bölünme sonucu.
(1) Yönlendirilmiş ağ veri setinin benzerliğini hesaplamak için SimRank algoritmasını kullanın ve düğümler arasındaki benzerlik matrisi S'yi elde edin.
(2) Geliştirilmiş modülerlik artış matrisi rixQ'larını başlatın.
(3) Algoritmada maksimum yığın yapısı H'yi başlatın Yığın yapısı her satırın maksimum değerini Q'larda saklar.
(4) En büyük yığın yapısı H'deki en üst öğeyi seçin, CNM algoritmasının modülerlik artışlı güncelleme kuralına göre artımlı matrise karşılık gelen satırları ve sütunları birleştirin ve artımlı matrisi ve en büyük yığın yapısını güncelleyin.
(5) Tüm düğümler bir topluluğa aittir, algoritma sona erer, aksi takdirde adım (4) 'e ilerleyin.
3 Deneysel sonuçlar ve analiz
Algoritmanın etkinliğini test etmek için, bu makale doğrulama için bilgisayar tarafından oluşturulan bir ağ ve iki gerçek ağ kullanır. Bunların arasında, bilgisayar tarafından üretilen ağ, yönlendirilmiş ağ dirnetini oluşturmak için LFR (Lancichinetti-Fortunato-Radicchi) kıyaslama ağını [11-12] kullanır ve gerçek ağ, poblogları [13] siyasi blog çemberi ağı ve wiki-oy [14] Wikipedia oylama ağını kullanır.
LFR referans ağı, son yıllarda topluluk tespitinde yaygın olarak kullanılan, bilgisayar tarafından üretilen bir simülasyon ağıdır.Farklı ağ parametreleri ve topluluk parametreleri ayarlanarak, bölüm standartlarına sahip karmaşık bir ağ oluşturulur. Algoritma tarafından sağlanan topluluk bölümü standardı, aynı zamanda orijinal topluluğu oluşturur ve bu da algoritmanın doğruluğunu doğrulama sorununu çözer. Ağı oluşturmak için LFR bilgisayarı kullanırken ayarlanması gereken ana parametreler Tablo 1'de gösterilmektedir.
3.1 Ağ üzerinde bilgisayar tarafından oluşturulan deneysel sonuçlar
Deneyde, LFR bilgisayar tarafından üretilen ağdaki belirli parametreler şu şekilde ayarlanmıştır: düğüm sayısı N = 62, ortalama derece cinsinden k = 10, maksimum derece cinsinden kmax = 16, karma parametre mu = 0.2, minimum topluluk düğümü sayısı cmin = 9, maksimum Topluluk düğümlerinin sayısı cmax = 27.
LFR bilgisayarı tarafından oluşturulan ilk yönlendirilmiş ağ Şekil 1'de gösterilmektedir ve standart bölüm topluluk yapısı Şekil 2'de gösterilmektedir.
LFR bilgisayar tarafından oluşturulan ağ topluluğunu tespit etmek için bu makalede önerilen algoritmayı kullanarak, topluluk bölümü sonuçları Tablo 2'de gösterilmektedir.
Bu makaledeki algoritmanın topluluk algılama sonucunun, Şekil 2'deki standart topluluk bölümü sonucuyla tutarlı olduğu görülebilir. Formül (3) kullanılarak, mevcut topluluk algılama sonucunun modülerlik değeri, bu makaledeki algoritmanın iyi doğruluğa sahip olduğunu gösteren modülerlik değer aralığı ile tutarlı olan 0.433 olarak hesaplanır.
3.2 Algoritmadaki parametrelerin seçimi
Bu makaledeki algoritmada, benzerlik hesaplaması nihai topluluk algılama sonucunu belirlemektedir.SimRank algoritması için zayıflama faktörü literatürdeki c = 0.8 değerini ifade etmektedir [9]. SimRank'ın doğruluğu, k yineleme sayısı arttıkça artar Teoride, k sonsuza meyilli olduğunda doğruluk en yüksektir. Çoğu gerçek ağın seyrek olduğu [15] ve sınırlı sayıda yineleme içinde zaman içinde birleşebildiği gerçeği ışığında, en iyi k değeri deneyler yoluyla seçilebilir.
Test ağı olarak poblogları ve wiki-oyu seçin, algoritmayı farklı k değerleri için 10 kez çalıştırın ve k yineleme sayısı farklı değerler aldığında karşılık gelen modülerlik ortalamasını hesaplayın.
Şekil 3'te gösterildiği gibi, modülerlik yinelemelerin sayısı ile artar ve bu yinelemenin topluluk yapısını daha belirgin hale getirdiğini gösterir. Pobloglar için, k = 5 olduğunda, modülerliğin maksimum değeri Q = 0.427'dir ve iki bariz topluluk yapısını gösterir; wiki-oy için, k = 7 olduğunda, maksimum modülerlik Q = 0.416'dır.
3.3 Karşılaştırmalı deney
Literatürde [4] Newman, 400.000'e kadar düğüm ve 2 milyondan fazla uç içeren Amazon.com çevrimiçi kitabevindeki sayfaların bağlantı ilişkileri ağını analiz etmek için CNM algoritmasını kullandı ve sonunda 10 topluluğu böldü. Bunların arasında en büyük topluluk 114538 düğüm içerir, ikinci en büyük topluluk da küçük değildir, 92276 düğüm bulunurken, en küçük topluluk yalnızca 947 düğüme sahiptir. Böyle çok büyük veya çok küçük bir dernek, birliğin gelişmesine yardımcı olmayabilir.
Üç veri kümesi üzerinde karşılaştırmalı deneyler yapmak için bu makaledeki algoritmayı ve [10] 'da önerilen yönlendirilmiş ağ topluluğu algılama algoritmasını kullanma.
Tablo 3'teki verilerden, LFR modeli tarafından oluşturulan dirnet ağında, hesaplamada yönlendirilen ağın topolojik yapısının tam olarak dikkate alınması nedeniyle, bu makaledeki algoritmanın literatürdeki [10] ve literatürdeki [10] algoritma topluluğu tespitinden daha iyi sonuçlara sahip olduğu görülebilir. Algoritması, yönsel modülerliğin maksimum değerini spektrum analizi ile çözmektir.Kendi başına bir modülerlik optimizasyon algoritmasıdır ve ağ yapısını tam olarak dikkate alamaz. Benzer şekilde, ploblogs veri setinde, bu algoritmanın topluluk algılama sonuçları da 15 düğümün doğru şekilde bölünmediği, ancak optimal modülerlik değerinin 0.427 olduğu ve topluluk algılama sonuçlarının hala iyi bir topluluk olduğunu gösteren iki topluluk olduğunu göstermektedir. yapı. Viki oylama veri seti üzerindeki deneylerde, bu makaledeki algoritma literatürdeki algoritma kadar modüler olmasa da [10], tespit edilen topluluk boyutu daha da iyidir. Büyük ölçekli ağlarda, bazen topluluk boyutu Daha eşitçe.
4. Sonuç
Bu makale, CNM algoritmasına dayalı benzerliğe dayalı yönlendirilmiş bir ağ topluluğu algılama algoritması önermektedir.Lebiyatta [10] önerilen yönlendirilmiş ağ topluluğu algılama algoritması ile karşılaştırıldığında, yalnızca yönlendirilmiş ağı işlemekle kalmaz, aynı zamanda algılanan topluluk boyutu da daha makuldür. Deneysel sonuçlar, bu makalede önerilen algoritmanın sadece yönlendirilen ağın topolojik yapı bilgisini tam olarak dikkate almakla kalmayıp, aynı zamanda modülerliğin kendisinin sınırlandırılmasını önleyerek bölünmüş toplulukların ölçeğini daha tekdüze hale getirdiğini göstermektedir.
Referanslar
1 GIRVAN M, NEWMAN M E J. Sosyal ve biyolojik ağlarda topluluk yapısı J. Amerika Birleşik Devletleri Ulusal Bilimler Akademisi Bildirileri, 2002, 99 (12): 7821-7826.
2 NEWMAN M E J. Ağlarda topluluk yapısını tespit etmek için hızlı algoritma J. Physica Review E, 2004, 69 (6): 066133.
3 FORTUNATO S, BARTHLEMY M. Topluluk tespitinde çözünürlük sınırı J. Amerika Birleşik Devletleri Ulusal Bilimler Akademisi Bildirileri, 2007, 104 (1): 36-41.
4 CLAUSET A, NEWMAN M E, MOORE C. Çok büyük ağlarda topluluk yapısını bulmak. J. Physical Review E, 2010, 70 (6): 264-277.
5 ALFALAHI K, ATIF Y, HAROUS S. Benzerlik sanal ağları aracılığıyla sosyal ağlarda topluluk tespiti C. IEEE / ACM Uluslararası Sosyal Ağ Analizi ve Madencilik Gelişmeleri Konferansı, 2013: 1116-1123.
6 ZHANG F, WU B, WANG B, ve diğerleri. Düğüm benzerlik hesaplaması yoluyla yönlendirilmiş grafiklerde topluluk algılama C. IET Uluslararası Kablosuz, Mobil ve Multimedya Ağları Konferansı, 2013: 258-261.
7 Sun Yifan, Li Sai Benzerliğe Dayalı Weibo Sosyal Ağının Topluluk Keşif Yöntemi J. Bilgisayar Araştırma ve Geliştirme, 2014, 51 (12): 2797-2807.
[8] Zhang Haiyan, Liang Xun, Zhou Xiaoping. Yönlendirilmiş grafiğin yerel olarak genişletilmesi için örtüşen topluluk keşif algoritması J. Veri Toplama ve İşleme, 2015,30 (3): 683-693.
[9] JEH G, WIDOM J. SimRank: yapısal bağlam benzerliğinin bir ölçüsü C Sekizinci ACM SIGKDD Uluslararası Bilgi Keşfi ve Veri Madenciliği Konferansı Bildirileri, ACM, 2002: 538-543.
10 LEICHT E A, NEWMAN M E. Yönlendirilmiş ağlarda topluluk yapısı. J. Physical Review Letters, 2007, 100 (11): 2339-2340.
11 LANCICHINETTI A, FORTUNATO S, RADICCHI F. Topluluk algılama algoritmalarını test etmek için kıyaslama grafikleri J. Fiziksel İnceleme E İstatistiksel Doğrusal Olmayan ve Yumuşak Madde Fiziği, 2008, 78 (2): 561-570.
12 LANCICHINETTI A, FORTUNATO S. Örtüşen topluluklarla yönlendirilmiş ve ağırlıklı grafiklerde topluluk algılama algoritmalarını test etmek için kıyaslamalar J. Fiziksel İnceleme E İstatistiksel Doğrusal Olmayan ve Yumuşak Madde Fiziği, 2009, 80 (2): 145-148.
13 ADAMIC LA, GLANCE N. Siyasi blogosfer ve 2004 ABD seçimleri: bölünmüş bloglar C. Uluslararası Link Keşfi Çalıştayı, ACM, 2005: 36-43.
14 LESKOVEC J, HUTTENLOCHER D, KLEIBERG J. Çevrimiçi sosyal ağlarda olumlu ve olumsuz bağların tahmin edilmesi J Computer. Bilgisayar Bilimi, 2010, 36 (7): 641-650.
15 Chen Jie, SAAD Y. Topluluk algılamaya uygulama ile yoğun alt grafik çıkarma J .IEEE Bilgi ve Veri Mühendisliği İşlemleri, 2012, 24 (7): 1216-1230.
