En matemàtiques, un graf aleatori és el terme general per referir-se a les distribucions de probabilitat sobre gràfics. Els grafs aleatoris es poden descriure simplement mitjançant una distribució de probabilitat o mitjançant un procés aleatori que els genera. La teoria dels grafs aleatoris es troba a la intersecció entre la teoria dels grafs i la teoria de la probabilitat. Des d'una perspectiva matemàtica, els gràfics aleatoris s'utilitzen per respondre preguntes sobre les propietats dels grafs típics. Les seves aplicacions pràctiques es troben en totes les àrees en què cal modelar xarxes complexes. – es coneixen molts models de grafs aleatoris, que reflecteixen els diversos tipus de xarxes complexes que es troben en diferents àrees. En un context matemàtic, el graf aleatori es refereix gairebé exclusivament al model de graf aleatori d'Erdős-Rényi. En altres contextos, qualsevol model de graf es pot anomenar graf aleatori.
Models Un graf aleatori s'obté començant amb un conjunt de n vèrtexs aïllats i afegint arestes successives entre ells a l'atzar. L'objectiu de l'estudi en aquest camp és determinar en quina etapa és probable que sorgeixi una propietat particular del graf.Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd. Diferents models de grafs aleatoris produeixen diferents distribucions de probabilitat en els grafs. El més estudiat és el proposat per Edgar Gilbert, però sovint anomenat model Erdős-Rényi, denotat com a G ( n, p ). En ell, cada aresta possible es produeix independentment amb probabilitat 0 < p < 1. La probabilitat d'obtenir qualsevol graf aleatori particular amb m arestes és amb la notació Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
Un model estretament relacionat, també anomenat model d'Erdős-Rényi i denotat com a G ( n, M ), assigna la mateixa probabilitat a tots els gràfics amb exactament M arestes. Amb 0 ≤ M ≤ N, G ( n, M) té elements i cada element apareix amb probabilitat Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd. El model G ( n, M) es pot veure com una instantània en un moment concret ( M) del procés aleatori del graf. , un procés estocàstic que comença amb n vèrtexs i cap aresta, i a cada pas afegeix una nova aresta escollida uniformement del conjunt d'arestes que falten.
Si, en canvi, comencem amb un conjunt infinit de vèrtexs, i de nou deixem que cada aresta possible es produeixi independentment amb probabilitat 0 < p < 1, aleshores obtenim un objecte G anomenat graf aleatori infinit. Excepte en els casos trivials en què p és 0 o 1, aquest G gairebé segurament té la propietat següent:
Donats qualsevol n + m elements , hi ha un vèrtex c a V que és adjacent a cadascun de i no és adjacent a cap de .
Resulta que si el conjunt de vèrtexs és numerable, aleshores hi ha, fins a isomorfisme, només un gràfic amb aquesta propietat, és a dir, el gràfic de Rado. Per tant, qualsevol gràfic aleatori numerablement infinit és gairebé amb seguretat el gràfic de Rado, que per aquesta raó de vegades s'anomena simplement el gràfic aleatori. Tanmateix, el resultat anàleg no és cert per als gràfics innumerables, dels quals hi ha molts gràfics (no isomorfs) que satisfan la propietat anterior.
Un altre model, que generalitza el model de graf aleatori de Gilbert, és el model de producte escalar aleatori. Un graf de producte escalar aleatori associa a cada vèrtex un vector real. La probabilitat d'una aresta uv entre qualsevol vèrtex u i v és una funció del producte escalar u • v dels seus respectius vectors.
La matriu de probabilitat de xarxa modela gràfics aleatoris mitjançant probabilitats d'aresta, que representen la probabilitat que una vora donada existeix durant un període de temps especificat. Aquest model és extensible a estructures de grafs dirigits i no dirigits; ponderats i no ponderats; i estàtics o dinàmics.
Per a M ≃ pN, on N és el nombre màxim d'arestes possibles, els dos models més utilitzats, G ( n, M) i G ( n, p ), són gairebé intercanviables.Bollobas, B. and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003
Els grafs regulars aleatoris formen un cas especial, amb propietats que poden diferir dels grafs aleatoris en general.
Un cop tenim un model de gràfics aleatoris, cada funció dels gràfics esdevé una variable aleatòria. L'estudi d'aquest model consisteix a determinar si una propietat es pugui produir, o si més no estimar la probabilitat que es produeixi.Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
Terminologia El terme «gairebé tots» en el context dels gràfics aleatoris fa referència a una seqüència d'espais i probabilitats, de manera que les probabilitats d'error tendeixen a zero.Béla Bollobás, Probabilistic Combinatorics and Its Applications, 1991, Providence, RI: American Mathematical Society.
Propietats La teoria dels grafs aleatoris estudia les propietats típiques dels grafs aleatoris, aquelles que es compleixen amb alta probabilitat per a grafs extrets d'una distribució particular. Per exemple, podríem demanar un valor determinat de i quina és la probabilitat que està connectat. En l'estudi d'aquestes qüestions, els investigadors sovint es concentren en el comportament asimptòtic dels gràfics aleatoris — els valors als quals convergeixen diverses probabilitats a mesura que creix molt. La teoria de la percolació caracteritza la connectivitat dels grafs aleatoris, especialment els infinitament grans.
La percolació està relacionada amb la robustesa del graf (anomenat també xarxa). Donat un graf aleatori de nodes i un grau mitjà A continuació, eliminem aleatòriament una fracció de nodes i deixar només una fracció Existeix un llindar crític de percolació per sota de la qual la xarxa es fragmenta mentre que per sobre existeix un component connex gegant.Bollobas, B. and Riordan, O.M. "Mathematical results on scale-free random graphs" in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003.Erdős, P. Rényi, A (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297
La percolació localitzada fa referència a l'eliminació d'un node dels seus veïns, els veïns més propers, etc., fins que una fracció de de nodes de la xarxa s'elimina. Es va demostrar que per a un gràfic aleatori amb distribució de Poisson de graus exactament igual que per a l'eliminació aleatòria.
Els grafs aleatoris s'utilitzen àmpliament en el mètode probabilístic, on s'intenta demostrar l'existència de grafs amb certes propietats. L'existència d'una propietat en un graf aleatori sovint pot implicar, mitjançant el lema de regularitat de Szemerédi, l'existència d'aquesta propietat en gairebé tots els grafs.
En gràfics regulars aleatoris, són el conjunt de -gràfics regulars amb de tal manera que i són els nombres naturals, , i és parell.Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
La seqüència de graus d'un gràfic en depèn només del nombre d'arestes dels conjuntsBéla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
Si les vores, en un gràfic aleatori, és prou gran per garantir que gairebé tots té un grau mínim d'almenys 1, aleshores gairebé tots està connectat i, si és parell, gairebé tots té una coincidència perfecta. En particular, en el moment en què l'últim vèrtex aïllat desapareix en gairebé tots els gràfics aleatoris, el gràfic esdevé connectat.Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd.
Gairebé tots els grafs processen en un nombre parell de vèrtexs amb l'aresta que eleva el grau mínim a 1 o un graf aleatori amb una mica més de arestes i amb probabilitat propera a 1 garanteix que el gràfic tingui una coincidència completa, amb l'excepció de com a màxim un vèrtex.
Per a alguna constant , gairebé tots els gràfics etiquetats amb vèrtexs i almenys Les arestes són hamiltonianes. Amb la probabilitat que tendeix a 1, l'aresta particular que augmenta el grau mínim a 2 fa que el graf sigui hamiltonià.
Les propietats d'un gràfic aleatori poden canviar o romandre invariants sota transformacions de gràfics. Mashaghi A. et al., per exemple, van demostrar que una transformació que converteix gràfics aleatoris en els seus gràfics duals d'aresta (o gràfics de línia) produeix un conjunt de gràfics amb gairebé la mateixa distribució de graus, però amb correlacions de grau i un coeficient d'agrupació significativament més alt.
Coloració Donat un graf aleatori G d'ordre n amb el vèrtex V ( G) = {1,..., n }, mitjançant l'algoritme voraç sobre el nombre de colors, els vèrtexs es poden acolorir amb els colors 1, 2,... (el vèrtex 1 és acolorit 1, el vèrtex 2 és acolorit 1 si no és adjacent al vèrtex 1, en cas contrari és acolorit 2, etc.).Béla Bollobás, Random Graphs, 1985, Academic Press Inc., London Ltd. El nombre de coloracions pròpies de grafs aleatoris donat un nombre de q colors, anomenat el seu polinomi cromàtic, roman fins ara desconegut. L'escalat de zeros del polinomi cromàtic de grafs aleatoris amb paràmetres n i el nombre d'arestes m o la probabilitat de connexió p s'ha estudiat empíricament mitjançant un algorisme basat en la coincidència simbòlica de patrons.
Arbres aleatoris Un arbre aleatori és un arbre o arborescència que es forma mitjançant un procés estocàstic. En una àmplia gamma de gràfics aleatoris d'ordre n i mida M(n), la distribució del nombre de components de l'arbre d'ordre k és asimptòticament de Poisson. Els tipus d'arbres aleatoris inclouen l'arbre d'expansió uniforme, l'arbre d'expansió mínima aleatori, l'arbre binari aleatori, el treap, l'arbre aleatori d'exploració ràpida, l'arbre brownià i el bosc aleatori.
Gràfics aleatoris condicionals Considereu un model de graf aleatori donat definit a l'espai de probabilitat i deixar sigui una funció amb valors reals que assigna a cada gràfic de un vector de m propietats. Per a un valor fix , els gràfics aleatoris condicionals són models en què la mesura de probabilitat assigna probabilitat zero a tots els gràfics tals que .
Casos especials són gràfics aleatoris condicionalment uniformes, on assigna la mateixa probabilitat a tots els gràfics que tenen propietats especificades. Es poden veure com una generalització del model Erdős-Rényi G ( n, M ), quan la informació de condicionament no és necessàriament el nombre d'arestes M, sinó qualsevol altra propietat arbitrària del gràfic. En aquest cas, hi ha molt pocs resultats analítics disponibles i cal simulació per obtenir distribucions empíriques de les propietats mitjanes.
Història El primer ús d'un model de graf aleatori va ser per Helen Hall Jennings i Jacob Moreno el 1938, on es va considerar un "sociograma d'atzar" (un model dirigit d'Erdős-Rényi) en estudiar la comparació de la fracció d'enllaços recíprocs a les seves dades de xarxa amb el model aleatori. Un altre ús, sota el nom de "xarxa aleatòria", va ser per Ray Solomonoff i Anatol Rapoport el 1951, utilitzant un model de grafs dirigits amb grau de sortida fix i adjuntacions escollides aleatòriament a altres vèrtexs.
El model Erdős–Rényi de gràfics aleatoris va ser definit per primera vegada per Paul Erdős i Alfréd Rényi en el seu article de 1959 "On Random Graphs"Erdős, P. Rényi, A (1959) "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297 i independentment per Gilbert en el seu article "Random graphs"..
Referències
Categoria:Matemàtiques