ในทางคณิตศาสตร์กราฟสุ่มเป็นคำทั่วไปที่ใช้อ้างถึงการแจกแจงความน่าจะเป็นบนกราฟกราฟสุ่มอาจอธิบายได้ง่ายๆ ด้วยการแจกแจงความน่าจะเป็น หรือด้วยกระบวนการสุ่มที่สร้างกราฟเหล่านั้น^{[ 1 ] [ 2 ]}ทฤษฎีกราฟสุ่มอยู่ตรงจุดตัดระหว่างทฤษฎีกราฟและทฤษฎีความน่าจะเป็นจากมุมมองทางคณิตศาสตร์ กราฟสุ่มใช้เพื่อตอบคำถามเกี่ยวกับคุณสมบัติของ กราฟ ทั่วไปการประยุกต์ใช้ในทางปฏิบัติพบได้ในทุกสาขาที่ ต้องการสร้างแบบจำลอง เครือข่ายที่ซับซ้อน – ดังนั้นจึงมีแบบจำลองกราฟสุ่มหลายแบบที่เป็นที่รู้จัก ซึ่งสะท้อนให้เห็นถึงเครือข่ายที่ซับซ้อนหลากหลายประเภทที่พบในสาขาต่างๆ ในบริบททางคณิตศาสตร์กราฟสุ่ม หมายถึง แบบจำลองกราฟสุ่ม Erdős–Rényiเกือบทั้งหมดในบริบทอื่นๆ แบบจำลองกราฟใดๆ ก็อาจถูกเรียกว่ากราฟสุ่มได้

กราฟสุ่มได้มาจากการเริ่มต้นด้วยเซตของ จุดยอดที่แยกจากกัน nจุด และเพิ่มขอบที่ต่อเนื่องกันระหว่างจุดยอดเหล่านั้นแบบสุ่ม จุดมุ่งหมายของการศึกษาในสาขานี้คือการพิจารณาว่าจะมีโอกาสเกิดคุณสมบัติเฉพาะของกราฟขึ้นในขั้นตอนใด^{[ 3 ]}แบบจำลองกราฟสุ่มที่แตกต่างกันจะสร้างการกระจายความน่าจะเป็น ที่แตกต่างกัน บนกราฟ แบบจำลองที่ศึกษากันมากที่สุดคือแบบจำลองที่เสนอโดยEdgar Gilbertแต่มักเรียกว่าแบบจำลอง Erdős–Rényiซึ่งแสดงด้วยG ( n , p ) ในแบบจำลองนี้ ขอบที่เป็นไปได้ทุกขอบจะเกิดขึ้นอย่างอิสระด้วยความน่าจะเป็น 0 < p < 1 ความน่าจะเป็นของการได้กราฟสุ่มเฉพาะใดๆ ที่มี ขอบm คือ โดย ใช้สัญลักษณ์^{[ 4 ]}${\displaystyle p^{m}(1-p)^{Nm}}$${\displaystyle N={\tbinom {n}{2}}}$

แบบจำลองที่เกี่ยวข้องอย่างใกล้ชิด ซึ่งเรียกอีกอย่างว่าแบบจำลอง Erdős–Rényi และใช้สัญลักษณ์G ( n , M ) จะกำหนดความน่าจะเป็นเท่ากันให้กับกราฟทั้งหมดที่มี ขอบ M เส้นพอดี โดยที่ 0 ≤ M ≤ N , G ( n , M ) จะมีองค์ประกอบ และแต่ละองค์ประกอบจะเกิดขึ้นด้วยความน่าจะเป็น[ ^{3 ] แบบ} จำลองG ( n , M ) สามารถมองได้ว่าเป็นภาพรวม ณ เวลาใดเวลาหนึ่ง ( M ) ของกระบวนการกราฟสุ่มซึ่งเป็นกระบวนการสุ่มที่เริ่มต้นด้วย จุดยอด nจุดและไม่มีขอบ และในแต่ละขั้นตอนจะเพิ่มขอบใหม่หนึ่งเส้นที่เลือกอย่างสม่ำเสมอจากชุดของขอบที่หายไป ${\displaystyle {\tbinom {N}{M}}}$${\displaystyle 1/{\tbinom {N}{M}}}$${\displaystyle {\tilde {G}}_{n}}$

ถ้าหากเราเริ่มต้นด้วยเซตของจุดยอดอนันต์ และให้ขอบที่เป็นไปได้ทุกเส้นเกิดขึ้นอย่างอิสระด้วยความน่าจะเป็น 0 < p < 1 เราจะได้วัตถุGที่เรียกว่ากราฟสุ่มอนันต์ยกเว้นในกรณีที่pเป็น 0 หรือ 1 กราฟG ดังกล่าว เกือบจะแน่นอนว่าจะมีคุณสมบัติดังต่อไปนี้:

กำหนดให้ V มีสมาชิกn + m ตัว จะมีจุดยอดcในVที่อยู่ติดกับสมาชิกแต่ละตัวของและไม่อยู่ติดกับสมาชิกใด ๆของ${\displaystyle a_{1},\ldots ,a_{n},b_{1},\ldots ,b_{m}\in V}$${\displaystyle a_{1},\ldots ,a_{n}}$${\displaystyle b_{1},\ldots ,b_{m}}$

ปรากฏว่า ถ้าเซตของจุดยอดสามารถนับได้แล้ว จะมีกราฟเพียงกราฟเดียวที่มีคุณสมบัตินี้ (โดยไม่นับรวมไอ โซมอร์ฟิซึม) นั่นคือ กราฟราโดดังนั้น กราฟสุ่มที่มีจุดยอดนับได้อนันต์ใดๆ ก็เกือบจะเป็นกราฟราโดอย่างแน่นอน ซึ่งด้วยเหตุนี้บางครั้งจึงเรียกว่ากราฟสุ่ม เฉยๆ อย่างไรก็ตาม ผลลัพธ์ที่คล้ายกันนี้ไม่เป็นจริงสำหรับกราฟที่นับไม่ได้ ซึ่งมีกราฟจำนวนมาก (ที่ไม่เป็นไอโซมอร์ฟิซึมกัน) ที่มีคุณสมบัติดังกล่าว

อีกแบบจำลองหนึ่งซึ่งเป็นการขยายแบบจำลองกราฟสุ่มของกิลเบิร์ต คือแบบจำลองผลคูณจุดสุ่ม กราฟผลคูณจุดสุ่มจะเชื่อมโยงแต่ละจุดยอดกับเวกเตอร์จริงความน่าจะเป็นของขอบuvระหว่างจุดยอดuและv ใดๆ จะเป็นฟังก์ชันของผลคูณจุดu • vของเวกเตอร์ที่เกี่ยวข้อง

เมทริกซ์ความน่าจะเป็นของเครือข่ายจำลองกราฟสุ่มผ่านความน่าจะเป็นของขอบ ซึ่งแสดงถึงความน่าจะเป็นที่ขอบที่กำหนดจะปรากฏในช่วงเวลาที่ระบุ แบบจำลองนี้สามารถขยายไปสู่กราฟแบบมีทิศทางและไม่มีทิศทาง กราฟแบบมีน้ำหนักและไม่มีน้ำหนัก และโครงสร้างกราฟแบบคงที่หรือแบบไดนามิกได้ ${\displaystyle p_{i,j}}$${\displaystyle e_{i,j}}$

สำหรับM ≃ pNโดยที่Nคือจำนวนขอบสูงสุดที่เป็นไปได้ โมเดลที่ใช้กันอย่างแพร่หลายที่สุดสองแบบคือG ( n , M ) และG ( n , p ) แทบจะใช้แทนกันได้^{[ 5 ]}

กราฟปกติแบบสุ่มถือเป็นกรณีพิเศษ โดยมีคุณสมบัติที่อาจแตกต่างจากกราฟแบบสุ่มโดยทั่วไป

เมื่อเรามีแบบจำลองของกราฟสุ่มแล้ว ฟังก์ชันทุกฟังก์ชันบนกราฟจะกลายเป็นตัวแปรสุ่มการศึกษาแบบจำลองนี้มีจุดประสงค์เพื่อพิจารณาว่าคุณสมบัตินั้นอาจเกิดขึ้นหรือไม่ หรืออย่างน้อยก็ประมาณความน่าจะเป็นที่จะเกิดขึ้น^{[ 4 ]}

คำว่า 'เกือบทุก' ในบริบทของกราฟสุ่มหมายถึงลำดับของพื้นที่และความน่าจะเป็น โดยที่ความน่าจะเป็นของข้อผิดพลาดมีแนวโน้มเข้าใกล้ศูนย์^{[ 4 ]}

ทฤษฎีกราฟสุ่มศึกษาคุณสมบัติทั่วไปของกราฟสุ่ม ซึ่งเป็นคุณสมบัติที่เกิดขึ้นได้ด้วยความน่าจะเป็นสูงสำหรับกราฟที่สุ่มมาจากการแจกแจงแบบเฉพาะ ตัวอย่างเช่น เราอาจถามว่าสำหรับค่า n ที่กำหนดความน่าจะเป็นที่กราฟ n เชื่อมต่อกันคือเท่าใดในการศึกษาคำถามดังกล่าว นักวิจัยมักมุ่งเน้นไปที่พฤติกรรมเชิงอะซิมโทติกของกราฟสุ่ม ซึ่งก็คือค่าที่ความน่าจะเป็นต่างๆ ลู่เข้าหาเมื่อ n มีขนาดใหญ่มากทฤษฎีการซึมผ่านอธิบายลักษณะการเชื่อมต่อของกราฟสุ่ม โดยเฉพาะอย่างยิ่งกราฟที่มีขนาดใหญ่เป็นอนันต์ ${\displaystyle n}$${\displaystyle p}$${\displaystyle G(n,p)}$${\displaystyle n}$

การซึมผ่านเกี่ยวข้องกับความแข็งแกร่งของกราฟ (หรือเรียกว่าเครือข่าย) กำหนดให้กราฟแบบสุ่มของโหนดและดีกรีเฉลี่ยจากนั้นเราจะลบโหนดบางส่วนออกแบบสุ่มและเหลือเพียงบางส่วนเท่านั้นมีเกณฑ์การซึมผ่านที่สำคัญอยู่ค่า หนึ่ง ซึ่งหากต่ำกว่าเกณฑ์นี้ เครือข่ายจะแตกเป็นเสี่ยงๆ ในขณะที่หากสูงกว่าเกณฑ์นี้ จะมีส่วนประกอบที่เชื่อมต่อกันขนาดใหญ่^{[ 1 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]}${\displaystyle n}$${\displaystyle \langle k\rangle }$${\displaystyle 1-p}$${\displaystyle p}$${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$${\displaystyle p_{c}}$

การแพร่กระจายเฉพาะที่ หมายถึงการลบโหนดหนึ่งออกไปพร้อมกับโหนดข้างเคียง โหนดข้างเคียงถัดไป ฯลฯ จนกระทั่งได้สัดส่วนของโหนดในเครือข่ายที่ถูกลบออกไป มีการแสดงให้เห็นว่าสำหรับกราฟสุ่มที่มีการกระจายแบบปัวซงของดีกรีนั้นผลลัพธ์จะเหมือนกับการลบแบบสุ่มทุก ประการ${\displaystyle 1-p}$${\displaystyle p_{c}={\tfrac {1}{\langle k\rangle }}}$

กราฟสุ่มถูกนำมาใช้กันอย่างแพร่หลายในวิธีการทางความน่าจะเป็นซึ่งเป็นการพยายามพิสูจน์การมีอยู่ของกราฟที่มีคุณสมบัติบางอย่าง การมีอยู่ของคุณสมบัติบนกราฟสุ่มมักจะบ่งชี้ถึงการมีอยู่ของคุณสมบัตินั้นบนกราฟเกือบทั้งหมด ผ่านทาง ทฤษฎีบทความสม่ำเสมอของเซเมอเรดี (Szemerédi regularity lemma )

ในกราฟปกติแบบสุ่มคือเซตของกราฟปกติที่มีโดยที่และเป็นจำนวนธรรมชาติและเป็นจำนวนคู่^{[ 3 ]}${\displaystyle G(n,r-reg)}$${\displaystyle r}$${\displaystyle r=r(n)}$${\displaystyle n}$${\displaystyle m}$${\displaystyle 3\leq r<n}$${\displaystyle rn=2m}$

ลำดับดีกรีของกราฟขึ้นอยู่กับจำนวนขอบในเซตเท่านั้น^{[ 3 ]}${\displaystyle G}$${\displaystyle G^{n}}$

${\displaystyle V_{n}^{(2)}=\left\{ij\ :\ 1\leq j\leq n,i\neq j\right\}\subset V^{(2)},\qquad i=1,\cdots ,n.}$

ถ้าขอบในกราฟสุ่มมีขนาดใหญ่พอที่จะทำให้เกือบทุกขอบมีดีกรีขั้นต่ำอย่างน้อย 1 แล้วเกือบทุกขอบจะเชื่อมต่อกัน และถ้าเป็นจำนวนคู่ เกือบทุกขอบจะมีการจับคู่ที่สมบูรณ์แบบ โดยเฉพาะอย่างยิ่ง ทันทีที่จุดยอดโดดเดี่ยวสุดท้ายหายไปในกราฟสุ่มเกือบทุกกราฟ กราฟนั้นก็จะเชื่อมต่อกัน^{[ 3 ]}${\displaystyle M}$${\displaystyle G_{M}}$${\displaystyle G_{M}}$${\displaystyle G_{M}}$${\displaystyle n}$${\displaystyle G_{M}}$

กระบวนการสร้างกราฟเกือบทุกแบบที่มีจำนวนจุดยอดเป็นเลขคู่ โดยที่ขอบแต่ละด้านมีดีกรีต่ำสุดเท่ากับ 1 หรือกราฟแบบสุ่มที่มีจำนวนขอบมากกว่าเล็กน้อยและมีความน่าจะเป็นใกล้เคียงกับ 1 จะทำให้มั่นใจได้ว่ากราฟนั้นมีการจับคู่ที่สมบูรณ์ ยกเว้นจุดยอดไม่เกินหนึ่งจุด ${\displaystyle {\tfrac {n}{4}}\log(n)}$

สำหรับค่าคงที่บางค่า กราฟที่มีป้ายกำกับเกือบทุกกราฟที่มี จุดยอดและ ขอบอย่างน้อย จะเป็นกราฟ แฮมิลโทเนียนโดยที่ความน่าจะเป็นมีแนวโน้มเข้าใกล้ 1 ขอบเฉพาะที่เพิ่มดีกรีต่ำสุดเป็น 2 จะทำให้กราฟนั้นเป็นกราฟแฮมิลโทเนียน ${\displaystyle c}$${\displaystyle n}$${\displaystyle cn\log(n)}$

คุณสมบัติของกราฟสุ่มอาจเปลี่ยนแปลงหรือคงเดิมภายใต้การแปลงกราฟ ตัวอย่างเช่น Mashaghi A. และคณะ ได้แสดงให้เห็นว่าการแปลงที่แปลงกราฟสุ่มเป็นกราฟคู่ขอบ (หรือกราฟเส้น) จะสร้างกลุ่มกราฟที่มีการกระจายดีกรีเกือบเหมือนกัน แต่มีความสัมพันธ์ของดีกรีและสัมประสิทธิ์การจัดกลุ่มที่สูงกว่าอย่างมีนัยสำคัญ^{[ 9 ]}

เมื่อกำหนดกราฟสุ่มGที่มีลำดับnโดยมีจุดยอดV ( G ) = {1, ..., n } โดยใช้อัลกอริทึมแบบโลภตามจำนวนสี จุดยอดสามารถถูกระบายสีด้วยสี 1, 2, ... (จุดยอด 1 ถูกระบายสีด้วยสี 1 จุดยอด 2 ถูกระบายสีด้วยสี 1 หากไม่ติดกับจุดยอด 1 มิฉะนั้นจะถูกระบายสีด้วยสี 2 เป็นต้น) ^{[ 3 ]} จำนวนการระบายสีที่เหมาะสมของกราฟสุ่มที่กำหนดจำนวนสีq ซึ่งเรียกว่า พหุนามสียังคงไม่เป็นที่ทราบแน่ชัดจนถึงปัจจุบัน การปรับขนาดของศูนย์ของพหุนามสีของกราฟสุ่มที่มีพารามิเตอร์nและจำนวนขอบmหรือความน่าจะเป็นของการเชื่อมต่อpได้รับการศึกษาเชิงประจักษ์โดยใช้อัลกอริทึมที่อิงตามการจับคู่รูปแบบเชิงสัญลักษณ์^{[ 10 ]}

ต้นไม้สุ่ม (Random tree)คือต้นไม้หรือกลุ่มต้นไม้ที่เกิดขึ้นจากกระบวนการสุ่มในกราฟสุ่มจำนวนมากที่มีลำดับnและขนาดM ( n ) การกระจายของจำนวนส่วนประกอบของต้นไม้ที่มีลำดับk นั้น เป็นแบบปัวซง เชิงอะซิมโทติก ประเภทของต้นไม้สุ่ม ได้แก่ต้นไม้แผ่คลุมสม่ำเสมอ (Uniform spanning tree) , ต้นไม้แผ่คลุมขั้นต่ำแบบสุ่ม (Random minimum spanning tree) , ต้นไม้ไบนารีแบบสุ่ม (Random binary tree) , ต้นไม้ สุ่มแบบสำรวจอย่างรวดเร็ว (Rapidly exploring random tree) , ต้นไม้บราวน์ (Brownian tree ) และป่าสุ่ม (Random forest )

พิจารณาแบบจำลองกราฟสุ่มที่กำหนดบนปริภูมิความน่าจะเป็นและให้เป็นฟังก์ชันค่าจริงซึ่งกำหนด คุณสมบัติ mประการให้กับแต่ละกราฟ สำหรับค่า คงที่กราฟสุ่มแบบมีเงื่อนไขคือแบบจำลองที่การวัดความน่าจะ เป็นกำหนดความน่าจะเป็นเป็นศูนย์ให้กับ กราฟ ทั้งหมดที่${\displaystyle (\โอเมก้า ,{\คณิตศาสตร์ {F}},P)}$${\displaystyle {\mathcal {P}}(G):\Omega \rightarrow R^{m}}$${\displaystyle \Omega }$${\displaystyle \mathbf {p} \in R^{m}}$${\displaystyle P}$${\displaystyle {\mathcal {P}}(G)\neq \mathbf {p} }$

กรณีพิเศษคือกราฟสุ่มแบบเอกรูปที่มีเงื่อนไขซึ่งกำหนดความน่าจะเป็นเท่ากันให้กับกราฟทั้งหมดที่มีคุณสมบัติที่ระบุไว้ สามารถมองได้ว่าเป็นการขยายความของแบบจำลอง Erdős–Rényi G ( n , M ) เมื่อข้อมูลเงื่อนไขไม่จำเป็นต้องเป็นจำนวนขอบMแต่เป็นคุณสมบัติกราฟอื่นๆ ที่กำหนดขึ้นเองในกรณีนี้ มีผลลัพธ์เชิงวิเคราะห์น้อยมาก และจำเป็นต้องใช้การจำลองเพื่อหาการแจกแจงเชิงประจักษ์ของค่าเฉลี่ยของคุณสมบัติ ${\displaystyle P}$${\displaystyle {\คณิตศาสตร์ {P}}(G)}$

การใช้แบบจำลองกราฟสุ่มครั้งแรกเกิดขึ้นโดยHelen Hall JenningsและJacob Morenoในปี 1938 โดยพิจารณา "โซซิโอแกรมโอกาส" (แบบจำลอง Erdős-Rényi แบบมีทิศทาง) ในการศึกษาเปรียบเทียบสัดส่วนของลิงก์ที่ตอบสนองซึ่งกันและกันในข้อมูลเครือข่ายของพวกเขากับแบบจำลองสุ่ม^{[ 11 ]} การใช้งานอีกอย่างหนึ่งภายใต้ชื่อ "เครือข่ายสุ่ม" เกิดขึ้นโดยRay SolomonoffและAnatol Rapoportในปี 1951 โดยใช้แบบจำลองกราฟแบบมีทิศทางที่มีดีกรีขาออกคงที่และการเชื่อมต่อกับจุดยอดอื่นที่เลือกแบบสุ่ม^{[ 12 ]}

แบบ จำลอง กราฟสุ่มของแอร์ดอส–เรนยี ถูกกำหนดครั้งแรกโดย พอล แอร์ดิชและอัลเฟรด เรนยีในรายงานเรื่อง "On Random Graphs" เมื่อปี พ.ศ. 2502 ^{และเป็นอิสระ}จากกิลเบิร์ตในรายงาน "กราฟสุ่ม" ของเขา^{[ 6 ]}

• การควบแน่นแบบโบส-ไอน์สไตน์: แนวทางทฤษฎีเครือข่าย  – แบบจำลองในวิทยาศาสตร์เครือข่ายPages displaying short descriptions of redirect targets
• วิธีโพรง  – วิธีทางคณิตศาสตร์ในฟิสิกส์เชิงสถิติ
• เครือข่ายที่ซับซ้อน  – เครือข่ายที่มีลักษณะทางโทโพโลยีที่ไม่ธรรมดาPages displaying short descriptions of redirect targets
• วิวัฒนาการสองเฟส  – กระบวนการที่ขับเคลื่อนการจัดระเบียบตนเองภายในระบบปรับตัวที่ซับซ้อน
• แบบจำลองErdős–Rényi  – สองแบบจำลองที่เกี่ยวข้องกันอย่างใกล้ชิดสำหรับการสร้างกราฟสุ่ม
• แบบจำลองกราฟสุ่มแบบเอกซ์โปเนนเชียล  – แบบจำลองทางสถิติสำหรับการวิเคราะห์เครือข่ายPages displaying short descriptions of redirect targets
• ทฤษฎีกราฟ  – สาขาหนึ่งของคณิตศาสตร์เชิงดิสครีต
• เครือข่ายที่พึ่งพาซึ่งกันและกัน  – สาขาย่อยของวิทยาศาสตร์เครือข่าย
• วิทยาศาสตร์เครือข่าย  – สาขาวิชาการ
• การซึมผ่าน  – การกรองของเหลวผ่านวัสดุที่มีรูพรุน
• ทฤษฎีการซึมผ่าน  – ทฤษฎีทางคณิตศาสตร์เกี่ยวกับพฤติกรรมของกลุ่มที่เชื่อมต่อกันในกราฟสุ่ม
• ทฤษฎีกราฟสุ่มของการเกิดเจล  – ทฤษฎีทางคณิตศาสตร์สำหรับกระบวนการโซล-เจล
• กราฟปกติ  – กราฟที่แต่ละจุดยอดมีจำนวนจุดข้างเคียงเท่ากัน
• เครือข่ายไร้มาตราส่วน  – เครือข่ายที่มีการกระจายระดับดีกรีเป็นไปตามกฎกำลังPages displaying short descriptions of redirect targets
• การตอบสนองแบบกึ่งเชิงเส้น  – การขยายทฤษฎีการตอบสนองเชิงเส้นในระดับเมโซสโคปิก
• แบบจำลองบล็อกสุ่ม  – แนวคิดในวิทยาศาสตร์เครือข่าย
• เกณฑ์มาตรฐาน Lancichinetti–Fortunato–Radicchi  - อัลกอริทึมPages displaying short descriptions with no spaces