Generuj sieci bez skali z rozkładami stopni mocy i prawa za pomocą Barabasi-Alberta

Próbuję odtworzyć sieci syntetyczne (wykresy) opisane w niektórych artykułach.

Stwierdzono, że model Barabasi-Albert został wykorzystany do stworzenia „sieci rozkładach stopni mocy, $P_A(k) ∝ k^{-λ}$ ”.

$P_A$ to rozkład prawdopodobieństwa, który zwraca prawdopodobieństwo węzła o stopniu $k$ . Na przykład $P_A(2)$ wskazuje prawdopodobieństwo losowego wyboru węzła z sieci i uzyskania węzła o stopniu 2.

Średni stopień uderzenia $k$ wydaje się wynosić 4 w jednym papierze, przy minimalnym $k$ 2. Brak słowa o maksymalnym $k$ . W drugim artykule nie jest to określone. Zdefiniowanie sieci nie wydaje się takie ważne.

Podane są wartości lambda λ, podobnie jak liczba węzłów $n$ . Kombinacje są

1. n = 50000, λ = 3, 2,7, 2,3, w dokumencie
2. n = 4000 i λ = 2,5 lub n = 6000 i λ = 3 w drugim artykule

Szukałem bibliotek implementujących algorytm Barabasi-Alberta i wydają się one wymagać innych parametrów niż lambda i średni stopień. Jeden to NetworkX , drugi to GraphStream ( tutaj implementacja ). Działają w podobny sposób i proszą o:

• n : int - liczba węzłów
• m : int - liczba krawędzi do dołączenia z nowego węzła do istniejących węzłów; liczba krawędzi do dodania na każdym kroku

Jak obliczyć ustawienia m, aby wygenerować porównywalny wykres?

Oto kilka referencji:

• Katastrofalna kaskada awarii w sieciach współzależnych, Buldyrev i in. 2010, z osobno dostarczonymi informacjami uzupełniającymi
• Small Cluster in Cyber ​​Physical Systems, Huang i in. 2014
• Katastrofalna kaskada awarii w sieciach współzależnych, Havlin i in. 2010, dotyczy to Arxivu i nieco wyjaśnia pierwszy

Zauważ, że w tych artykułach wykorzystano „funkcje generujące” do analitycznego badania niektórych właściwości tych wykresów. Jednak uruchamiają również symulacje na tych modelach, więc musieli jakoś wygenerować te sieci.

Dzięki.

Krótka odpowiedź jest taka, że ​​nie można używać tego oprogramowania bezpośrednio, aby uzyskać to, czego chcesz. Dla ustalonego model Barabasi-Alberta ma zawsze rozkład stopni , niezależnie od . Dokładna formuła stopnia prawdopodobieństwa tego, co implementują te elementy oprogramowania (którym jest model BA)$m$$P_k \sim k^{-3}$$m$

Dokumenty (z ) prawdopodobnie mówią o jakimś uogólnionym modelu BA, jak sądzę. Pomogłoby to podać więcej szczegółów (pełne cytowania) na ich temat.$\lambda \neq 3$

EDYCJA: OK, przejrzę te referencje. W międzyczasie odkryłem, że istnieje pakiet R o nazwie igraph, który może robić, co chcesz. Stosowany tam cytowany dokument teoretyczny:

• „Połączone komponenty na losowych wykresach z podanymi oczekiwanymi sekwencjami stopni” Fan Chung, Linyuan Lu.

Ma około 400 cytowań w Google Scholar, więc prawdopodobnie jest to powszechnie stosowana metoda. Późniejszy artykuł z 2009 r. Cytowany na tej stronie pakietu R. wyraźnie mówi: „Sieci SF zawierają stopnie heterogeniczne, a ich dystrybucja jest zgodna z prawem mocy, . Aby zbudować sztuczne sieci SF, stochastyczny używany jest model Chung and Lu (CL). ”$P_d(k) \sim k^{-\lambda}$

EDYCJA 2: Myślę, że źle odczytałeś Huang i in. „Budujemy syntetyczne sieci losowe, pozbawione skali i małych światów, stosując odpowiednio model Erdos-Renyi, model Barabasi-Albert oraz model Watts i Strogatz [9]”. Nie mówi, że nigdzie mają BA, aby wykonać jakąkolwiek moc inną niż 3. Istnieje podpis liczbowy, który mówi: „Używamy modelu współzależności„ k-n ”do dwóch sieci syntetycznej skali i z wykładnikami prawa mocy 2.5 i 3 odpowiednio." Ale to nie znaczy, że użyli BA dla tych wykresów 2,5 stopnia. Jest jeszcze jedna postać, która mówi tylko: „Model Barabasi-Alberta służy do generowania sieci pozbawionej skali z wykładnikiem prawa mocy 3”.$G_p$$G_c$

EDIT3: Artykuł Buldyrev i in. nigdzie nie mówi, że użyli żadnych wykresów BA. „Wyniki symulacji dla P8 jako funkcji p dla sieci SF z = 3, 2,7, 2,3”. Nie mówią, jak otrzymali te wykresy. Przytaczają artykuły BA, ale tylko na długiej liście 10 artykułów na temat różnych losowych modeli sieci. Drugi artykuł tej grupy autorstwa Havlina i in. rzeczywiście daje na p. 5 model BA ma nieokreślony / nieokreślony , powołując się na dokument BA z 1999 r. Naprawdę nie chcę źle nazwać tego papieru, ale jedyny poprawny odczyt to . Znów nie mówi, jak wygenerowali$\lambda$$\lambda$$\lambda = 3$$\lambda = 2.7$wykresy z ich ryc. 8. Widzę, jak czytając ten artykuł można stwierdzić, że BA może generować takie wykresy ... ale nie może.

EDIT4: Tak, znalazłem to teraz w aktualnej wersji opublikowanej w Nature „Dla dwóch współzależnych sieci ² o rozkładach stopni mocy, , odkrywamy, że kryteria istnienia gigantycznego komponentu są zupełnie inne niż w jednej sieci. ” Cytat rzeczywiście wprowadza w błąd w taki sam sposób jak w Halvin i wsp., Ale nie twierdzą, że użyli procesu BA do wygenerowania wykresów. Fragment ten można interpretować jako cytowaną wzmiankę BA 1999 o tym, co oznacza sieć pozbawiona skali i / lub kto stworzył tę koncepcję. W każdym razie zaufaj matematyce ... pochodną wzoru na stopień licencjata możesz znaleźć w wielu miejscach, w tym w pracy własnej lub bardziej szczegółowo$P_A(k) \sim P_B(k) / k^{-\lambda}$w późniejszej książce [let] . BA oczywiście zrozumiał ogólność tego, co zaobserwowali, więc podali prawo, które jest bardziej ogólne (arbitralne ) niż to, co zapewnia ich konstrukcja, tj. . Jak powiedziałem wcześniej, istnieją inne metody (później opublikowane przez innych, np. Chung i Lu), aby uzyskać inną , ale nie używają konstrukcji BA, mimo że ich wykresy są również poprawnie nazywane bezskalowe.$\lambda$$\lambda = 3$$\lambda$