Grafo aleatorio

Los grafos aleatorios poseen estructuras típicas de los procesos aleatorios.

En Matemáticas se denomina grafo aleatorio a un grafo que es generado por algún tipo de proceso aleatorio. La teoría de los grafos aleatorios cae en la intersección entre la teoría de grafos y la teoría de probabilidades y se fundamenta en el estudio de ciertas propiedades de los grafos aleatorios. Uno de los modelos matemáticos más aplicados en la generación de redes aleatorias es modelo Erdös–Rényi.^[1]^[2]

Ramas de estudio

Una de las ramas más estudiadas en el área de las redes aleatorias es el de la teoría de la percolación (nivel de percolación) relacionado con el estudio de la fiabilidad en las redes de comunicación.^[3] Un campo de estudio inicial fue el de redes sociales, estudios sobre la topología de redes evolutivas como puede ser internet, etc. Se ha visto que algunas de las redes actuales crecen según modelos predefinidos en su distribuciones de grado, como puede ser la redes libres de escala.

Concepto

La idea de los grafos aleatorios está dentro de como enlazar de forma aleatoria un conjunto de N nodos, para realizar esto se pueden seguir diversas estrategias, cada una de ellas proporciona un modelo de redes (grafos) aleatorios. Uno de los campos de estudio más activo es el de los grafos aleatorios dinámicos en los que se van añadiendo nodos a medida que pasa el tiempo, estos grafos muestran ciertas propiedades de las redes reales.^[4]

Teoremas

Algunos teoremas se deducen del modelo, por ejemplo, si G(n; p) es un grafo aleatorio con n vértices donde cada enlace tiene una posibilidad p de existir:

Teorema 1: Dado un G(n, p) con un valor p constante e independiente de n, entonces el grafo seguro que posee casi seguro un diámetro igual a 2.

Teorema 2: Para un grafo G(n, p) aleatorio se establece que $\textstyle p=c{\frac {\log n}{n}}$ . Si c > 1 entonces casi todos los grafos no poseen vértices aislados y si c < 1 casi todos los grafos tienen al menos un vértice aislado.

Biografías

Béla Bollobás, Random Graphs, 2nd Edition, 2001, Cambridge University Press
Christine Nickel, Random Dot Product Graphs: A Model for Social Networks, Ph.D. Thesis, The Johns Hopkins University, 2007.

Referencias

↑ Erdős, P. and Rényi, A. "On the Evolution of Random Graphs." Publ. Math. Inst. Hungar. Acad. Sci. 5, 17-61, 1960.
↑ Erdős, P. and Spencer, J. Probabilistic Methods in Combinatorics. New York: Academic Press, 1974.
↑ Janson, S.; Łuczak, T.; and Ruciński, A. Random Graphs. New York: Wiley, 2000.
↑ "Random Graph Dynamics", Rick Durrett, Cornell University, New York,2006

Véase también

Grafo geométrico aleatorio

Datos: Q910404

Read other articles:

Batuan julang

Batuan julang di Taman Nasional Bryce Canyon, Utah Batuan julang atau batuan jamur (Inggris: hoodoocode: en is deprecated ) adalah julangan batu yang tinggi dan tipis yang dibentuk oleh pengikisan, biasanya dengan puncak atau kepala yang lebih besar (maka itu dinamakan batuan jamur). Batuan julang biasanya terdiri dari batuan yang relatif lunak di atasnya dengan batuan lebih keras dan tidak mudah terkikis yang melindungi setiap kolom dari unsur. Mereka umumnya terbentuk di dalam batuan endapa...

Munisipalitas Hjørring

Peta lokasi Munisipalitas Hjørring Munisipalitas Hjørring adalah sebuah kawasan pemukiman (Denmark: kommune) di Region Nordjylland di Denmark tengah. Munisipalitas Hjørring memiliki luas sebesar 929.58 km² dan memiliki populasi sebesar 67.121 jiwa. Referensi Municipal statistics: NetBorger Kommunefakta Diarsipkan 2007-08-12 di Wayback Machine., delivered from KMD aka Kommunedata (Municipal Data) Municipal merges and neighbors: Eniro new municipalities map Diarsipkan 2007-10-11 di Way...

Dance Again... the Hits

Dance Again... the HitsAlbum hit terbaik karya Jennifer LopezDirilis20 Juli 2012 (2012-07-20)Direkam1998–2012Genre Dance Pop latin R&B Durasi52:07LabelEpicProduser 7 Marc Anthony Sean Puffy Combs Emilio Estefan Jr. GoonRock Irv Gotti Kuk Harrell Rich Harrison Rodney Jerkins Richie Jones Ilya Salmanzadeh Jennifer Lopez Dave McPherson Troy Oliver Tone & Poke RedOne Julio Reyes Cory Rooney Ron G. Kike Santander Dave Scheuer Stargate Ryan Tedder Ric Wake Kronologi Jennifer Lope...

Duranbah Beach

Surfing beach in New South Wales, Australia Duranbah Beach Duranbah Beach (/djʊəˈrænbɑː/ dew-RAN-bah), officially known as Flagstaff Beach,[1] is the northernmost beach in New South Wales. Located in the Tweed Shire, Duranbah Beach is situated between the mouth of the Tweed River and the rocky headland Point Danger which also marks the Queensland-New South Wales border. The beach is 350 meters in length with vegetated dunes running along 200 metres.[2] The southern ...

British Forces Post Office

British postal service for the armed forces A British Wilding series postage stamp used at a BFPO on Christmas Island in 1957. The British Forces Post Office (BFPO) provides a postal service to HM Forces separate from that provided by Royal Mail in the United Kingdom. BFPO addresses are used for the delivery of mail in the UK and around the world. BFPO moved from its original base at Inglis Barracks, Mill Hill to its current base at RAF Northolt in west London in 2007.[1] Mission The ...

Nonode

This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Nonode – news · newspapers · books · scholar · JSTOR (June 2013) (Learn how and when to remove this message) Basic FM quadrature detector circuit using a nonode Nonode 6Л1П (6L1P), Manufactured in Novosibirsk, 1970 A nonode is a type of thermionic valve that has nine active el...

Філософія

Частина серії проФілософіяLeft to right: Plato, Kant, Nietzsche, Buddha, Confucius, AverroesПлатонКантНіцшеБуддаКонфуційАверроес Філософи Епістемологи Естетики Етики Логіки Метафізики Соціально-політичні філософи Традиції Аналітична Арістотелівська Африканська Близькосхідна іранська Буддій�...

Transgender

Gender identity other than sex assigned at birth Not to be confused with Transsexual. TransgenderTransgender flagClassificationGender identityAbbreviationsTGOther termsAssociated termsTranssexual Part of a series onTransgender topics OutlineHistoryTimeline Gender identities Androgyne Bissu, Calabai, Calalai Burrnesha Cisgender Gender bender Hijra Non-binary or genderqueer Gender fluidity Kathoey Koekchuch Third gender Bakla Faʻafafine Femminiello Khanith Māhū ...

Armed Forces Institute of Cardiology

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Armed Forces Institute of Cardiology – news · newspapers · books · scholar · JSTOR (February 2016) (Learn how and when to remove this message) Hospital in Punjab, PakistanArmed Forces Institute of Cardiologyمسلح افواج امراض دل ہسپتالGovern...

The Fallen Angels (band)

For the Gram Parsons-led band, see Live 1973. The Fallen Angels in 1968. The Fallen Angels were an American psychedelic rock band formed in Washington D.C., in 1966. Spearheaded by the group's lead vocalist and bassist, Jack Bryant, the band originally released two albums and several singles, which were marked by lyrical and instrumental experimentation. Despite never breaking through on a national scale, the Fallen Angels were popular in the American music underground, and their music has b...

هيرلين لي سيك

هيرلين لي سيك شعار الاسم الرسمي (بالفرنسية: Herlin-le-Sec)‏ الإحداثيات 50°21′18″N 2°19′46″E / 50.355°N 2.3294444444444°E / 50.355; 2.3294444444444 [1] [2] تقسيم إداري البلد فرنسا[3] التقسيم الأعلى باد كاليه خصائص جغرافية المساحة 3.86 كيلومتر مربع[1] ...

Winter Offensive of 1947 in Northeast China

1947 military offensive Winter Offensive of 1947 in Northeast ChinaPart of the Chinese Civil WarDateDecember 15, 1947 – March 15, 1948LocationNortheast ChinaResult Communist victoryBelligerents Flag of the National Revolutionary ArmyNational Revolutionary Army PLAPeople's Liberation ArmyCommanders and leaders Chen Cheng Wei Lihuang Lin Biao Luo RonghuanStrength 580,000 730,000Casualties and losses 156,000 unknown vteCampaigns of the Chinese Civil War Outline of the Chinese Civil War First P...

国技

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: 国技 – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2022年11月) 国の象徴元首国旗国旗歌国歌国章国技国璽国石 ...

Гавайцы

Гавайцы Современное самоназвание Hawaiʻi maoli Численность и ареал Всего: ≈160 тыс. чел.[комм. 2] США: 156 456[комм. 1] (перепись 2010)[2] Гавайи Канада: 3 300 (2016)[3] Новая Зеландия: 429 (2018)[4] Описание Язык английский, гавайский креольский[англ.], гавайский Рели�...

Princess Marie of Waldeck and Pyrmont

Princess William of Württemberg Marie of Waldeck and PrymontPrincess William of WürttembergBorn(1857-05-23)23 May 1857Arolsen, Waldeck and PyrmontDied30 April 1882(1882-04-30) (aged 24)Ludwigsburg, WürttembergSpousePrince William of WürttembergIssuePauline, Princess of WiedPrince UlrichNamesGeorgine Henriette MarieHouseWaldeck and PyrmontFatherGeorge Victor, Prince of Waldeck and PyrmontMotherPrincess Helena of Nassau Princess Georgine Henriette Marie of Waldeck and Pyrmont (23 May 1...

أورانج (نيويورك)

لمعانٍ أخرى، طالع أورانج (توضيح). أورانج الإحداثيات 42°19′59″N 77°02′07″W / 42.333055555556°N 77.035277777778°W / 42.333055555556; -77.035277777778 [1] تقسيم إداري البلد الولايات المتحدة[2] التقسيم الأعلى مقاطعة شويلر خصائص جغرافية المساحة 54.45 ميل مربع ارتفاع 522 م...

Babalon

Goddess in Thelema Not to be confused with Babylon. This article contains too many or overly lengthy quotations. Please help summarize the quotations. Consider transferring direct quotations to Wikiquote or excerpts to Wikisource. (December 2021) BabalonMother of AbominationsSeal of BabalonConsortChaos Part of a series onThelemaUnicursal hexagram The Rights of Man Holy Books and Stele The Book of the Law The Holy Books of Thelema The Stele of Revealing Key figures Ankh-af-na-Khonsu François ...

Black Market Reloaded

Darknet market Black Market ReloadedType of siteDarknet marketAvailable inEnglishURLr6rcmz6lga4i5vb4.onion (defunct)[1][2]CommercialdownloadCurrent statusOffline Black Market Reloaded was a .onion hidden Tor website which sold illegal drugs and other illegal goods such as stolen credit cards and firearms. Its popularity increased dramatically after the closure of Silk Road, its largest competitor.[3] In late November 2013, the owner of Black Market Reloaded a...

三角窓

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: 三角窓 – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2019年11月) マツダ・T1500の三角窓三角窓（さんかくまど）とは...

Faust Symphony

Choral symphony by Franz Liszt A Faust Symphony in three character pictures (German: Eine Faust-Symphonie in drei Charakterbildern), S.108, or simply the Faust Symphony, is a choral symphony written by Hungarian composer Franz Liszt inspired by Johann Wolfgang von Goethe's drama, Faust. The symphony was premiered in Weimar on 5 September 1857, for the inauguration of the Goethe–Schiller Monument there. Structure The first clue as to the work's structure is in Liszt's title: A Faust Symphony...