Modele losowych wykresów dla rzeczywistych sieci komputerowych

Interesują mnie modele losowych wykresów, które są podobne do wykresów rzeczywistych sieci komputerowych. Nie jestem pewien, czy wspólny dobrze zbadany model ( wierzchołków, każda możliwa krawędź jest wybierana z prawdopodobieństwem ) nadaje się do badania rzeczywistych sieci komputerowych (prawda?).n $G(n,p)$$n$$p$

jakie modele losowych wykresów są przydatne do zrozumienia sieci komputerowych powstających w praktyce?

Mówiąc bardziej ogólnie, jakie inne modele skończonych losowych wykresów (inne niż równoważne modelowi ) zostały zbadane w literaturze? (Idealną odpowiedzią byłby wskaźnik do ankiety dla badanych modeli skończonych losowych wykresów.)$G(n,p)$

W ciągu ostatnich kilku lat badania losowych wykresów z „naturalnymi” ograniczeniami strukturalnymi zyskały na popularności. Można na przykład rozważyć płaski wykres narysowany z klasy wszystkich płaskich wykresów z wierzchołkami i zbadać, jak zachowuje się jak n → ∞ . W przeciwieństwie do losowych wykresów Erdősa-Rényi lub innych podobnych modeli, krawędzie na tych wykresach są wysoce zależne, więc jednym z pseudo-motywacji do badania takich rozkładów jest analiza modeli sieciowych z bardzo ograniczoną niezależnością między krawędziami.$n$$n \rightarrow \infty$

Być może jednak obecnie cel ten wydaje się dość odległy, ponieważ ograniczona niezależność znacznie utrudnia analizę właściwości takich wykresów. W rzeczywistości kilka podstawowych pytań, na które bardzo łatwo jest odpowiedzieć dla , takich jak rozkład sekwencji stopni, zostały rozwiązane dopiero niedawno dla losowych wykresów płaskich.$G(n, p)$

Ostateczne odniesienie można znaleźć w artykułach Konstantinosa Panagiotou i zawartych w nich cytatach. Dla wygody oto mała próbka niektórych istotnych dokumentów:

• O rozkładzie stopni losowych wykresów płaskich . Konstantinos Panagiotou i Angelika Steger . Wystąpić w toku 22. dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych (SODA '11).
• O właściwościach przypadkowych przekrojów i triangulacji . Nicla Bernasconi, Konstantinos Panagiotou i Angelika Steger . W materiałach z 19. dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych (SODA '08), str. 132–141. [http://www.mpi-inf.mpg.de/~kpanagio/Dissections.pdf]
• O stopniach losowych wykresów zewnętrznych i szeregowo-równoległych . Nicla Bernasconi, Konstantinos Panagiotou i Angelika Steger . W materiałach z 12. Międzynarodowego warsztatu na temat technik losowych w obliczeniach (RANDOM'08), s. 1. 303–316. [http://www.mpi-inf.mpg.de/~kpanagio/OPSP.pdf]

Badanie to, Struktura i funkcja złożonych sieci Newmana, dokonuje przeglądu technik i modeli dla rzeczywistych złożonych sieci, w tym takich pojęć, jak efekt małego świata, rozkłady stopni i modele wykresów losowych. Również ten sam autor ma niezły artykuł, Losowe wykresy jako modele sieci , o adaptacjach losowych wykresów do modelowania rzeczywistych sieci.

Bibliografia:

1) Losowe wykresy jako modele sieci, MEJ Newman, w Handbook of Graphs and Networks, S. Bornholdt i HG Schuster (red.), Wiley-VCH, Berlin (2003)

2) Struktura i funkcja złożonych sieci, MEJ Newman, SIAM Review 45, 167-256 (2003)

Prawdziwe sieci komputerowe na jakiej warstwie? Internet jest, na poziomie AS (prawdopodobnie najwyższym), siecią małego świata z kilkoma węzłami o bardzo wysokim stopniu zaawansowania. Gdy warstwy zbliżają się do rzeczywistych drutów, wykres staje się bardziej związany z geografią, a mniej związany z warstwą społeczną (społeczność to rodzaj złego słowa - czy to naprawdę sieć społecznościowa, gdy podmioty będące „przyjaciółmi” są korporacjami wielonarodowymi?) . W skrajnym przypadku lokalna sieć Ethernet jest logicznym drzewem, które jest (prawdopodobnie) podgrafem fizycznego wzorca połączeń przewodów, a ten wzór połączeń przewodów prawdopodobnie nie jest zbyt wiele przewodów więcej niż drzewa.

„Prawdziwe sieci komputerowe” mają wiele smaków i warstw. Niektóre z nich wyglądają jak sieci społecznościowe, niektóre nie. Aby uzyskać więcej informacji na ten temat, nieskromnie odsyłam do rozdziału 2 mojej rozprawy - http://home.manhattan.edu/~peter.boothe/thesis.pdf

$n$$u$$v$$\beta e^{-d/(L\alpha)}$$d$$L$

Waxman, Routing połączeń wielopunktowych , IEEE J. Select. Obszary Commun. 6 (9), 1617-1622, 1988. Zegura, Calvert, Bhattacharjee, Jak modelować sieć , Proc. IEEE INFOCOM '96, 1996.

Walter Willinger zbudował swoją karierę dzięki wykorzystaniu grafów bez skali do modelowania sieci. Jest za dużo do cytowania, więc wskażę ci jego wpis DBLP . Kluczową kwestią w tych modelach jest to, że mają właściwości podobne do „rzeczywistych” sieci, które nie są przechwytywane przez G (n, p).

Możesz zajrzeć do książki Durretta . Wierzę, że masz dużo do zrobienia.

Zamiast żmudnego wyszukiwania, uzasadniania i analizowania konkretnego modelu, możesz chcieć wykorzystać posiadane dane z prawdziwego życia (jeśli takie posiadasz). Oznacza to zdefiniowanie ogólnego modelu probabilistycznego i szkolenie jego parametrów na podstawie danych (np. Poprzez oszacowanie maksymalnego prawdopodobieństwa).

$S \rightarrow p_1 : (S)S \mid p_2 : \varepsilon$$p_1, p_2$

Oczywiście, konkretna gramatyka może (i powinna!) Wykorzystywać wiedzę domenową. Rozważ np. Różne gramatyki wykorzystywane do przewidywania struktury drugorzędowej RNA w Dowell, Eddy (2004) dla smaku.

Znajdź szczegółowe informacje na temat tej techniki w Weinberg, Nebel (2010) . Nie wiem jednak, jak (dobrze) można go zastosować do ogólnych wykresów.

Jeśli potrzebujesz więcej mocy, możesz przejść do wielowymiarowych (S) CFG (np. Seki, Kato (2008) ) lub SCFG zależnych od długości / pozycji ( Weinberg, Nebel (2010) ).

$G(n,p)$$G(n,m)$

Jak zapewne wiesz, wydaje się, że istnieje różnica między wykresem połączeń dla sieci WWW a sprzeciwianiem się wykreśleniu wykresu połączeń dla infrastruktury internetowej. Z pewnością nie twierdzę, że jestem ekspertem, ale widziałem artykuł Li, Aldersona, Tanaki, Doyle'a i Willingera „W kierunku teorii wykresów bez skali: definicja, właściwości i implikacje”, który wprowadza „metrykę” „do zmierzenia„ płynności skali ”wykresu (z definicją wykresów bezskalowych będących nadal przedmiotem dyskusji, o ile mi wiadomo), które twierdzą, że mają model wykresu, który tworzy wykresy podobne do połączenia internetowego na routerze poziom.

Oto kilka bardziej generatywnych modeli, które mogą być interesujące:

Artykuł Bergera, Borgsa, Chayesa, D'Souzy i Kleinberga „Preferencyjne przywiązanie do konkurencji”

Wysoce zoptymalizowana tolerancja Carlsona i Doyle'a : mechanizm praw mocy w projektowanych systemach

Molloy i Reed's Krytyczny punkt dla losowych wykresów o podanej sekwencji stopni, który wprowadza „Model wymazanej konfiguracji”

Klaster Newmana i przywiązanie preferencyjne w rozwijających się sieciach (o czym już wspomniano)

Można również jawnie wygenerować rozkład stopni i utworzyć wykres w ten sposób, ale nie jest dla mnie jasne, jak blisko modeluje wykres internetowy na poziomie routera.

Jest oczywiście znacznie więcej literatury na ten temat i podałem tylko kilka (jak uważam) najważniejszych wydarzeń.

$G(n,p)$$G(n,m)$) nie działają dokładnie, ponieważ stopień wolny od skali lub prawa mocy rozkładał losowe wykresy rozchodząc się drugi moment w rozkładzie stopni. Nie twierdzę, że wiem wystarczająco dużo na ten temat, aby kategorycznie twierdzić o „większości” dowodów, ale z tego, co widziałem, jeden z pierwszych kilku wierszy dowodów właściwości na losowych wykresach Erdos-Renyi wyraźnie zakłada skończoność drugi moment w rozkładzie stopni. Z mojego punktu widzenia ma to sens, ponieważ skończona druga chwila sprawia, że ​​wykresy Erdosa-Renyi są bardziej lokalnie drzewiaste (patrz Informacje Mertensa i Montanariego , fizyka i obliczenia), co skutecznie zapewnia niezależność właściwości / ścieżek / struktur. Ponieważ dystrybuowane losowe wykresy stopnia mocy mają rozbieżny drugi moment, ta lokalna drzewiasta struktura jest zniszczona (a zatem wymaga różnych technik dowodowych?). Byłbym szczęśliwy, gdyby ta intuicja została unieważniona, gdyby ktoś z większą wiedzą lub wglądem miał pokazać, dlaczego tak nie jest.

Mam nadzieję, że to pomaga.

Chociaż to stary temat, odpowiadam, ponieważ wiele osób wciąż odwiedza takie posty. Motywuje mnie komentarz z innej odpowiedzi.

Zaproponowano model Barabasi-Albert i inne modele, które wytwarzają wykresy bez skali, do modelowania Internetu na poziomie routera i na poziomie systemu autonomicznego. Chociaż początkowo takie modele były uważane za dokładne, okazało się, że nie mamy pełnego obrazu topologii Internetu z powodu trudności w wykryciu wszystkich łączy. Chociaż uważa się, że jest to ciężki ogon, jest w toku.

W celach informacyjnych możesz przeczytać: RG Clegg, C Di Cairano-Gilfedder, S Zhou, Krytyczne spojrzenie na modelowanie prawa energetycznego w Internecie

Istnieje kilka książek o grafów losowych, jak Bollobás' Księdze i istnieje kilka modeli grafów losowych, takich jak małe świat Wikipedii Link lub preferencyjny przywiązanie Link Wikipedii , do sieci model z małych odległości pomiędzy komputerami lub tych z rozkładu stopni następujących prawa energetycznego odpowiednio.

Myślę, że nie ma łatwego sposobu modelowania prawdziwej sieci komputerowej, ale jestem całkiem pewien, że G (n, p) nie modelowałby jej zbyt dobrze. Chyba że pracujesz z bardzo określoną zorganizowaną siecią.

Moje zalecenie to praca ankietowa napisana przez wynalazców generatora losowych grafów R-MAT. http://portal.acm.org/citation.cfm?id=1132954

Generator losowych wykresów R-MAT jest bardzo prosty i szeroko stosowany. Na przykład ten generator został przyjęty w benchmarku Graph500 ( http://www.graph500.org/ ).