แบบจำลอง Barabási –Albert (BA)เป็นอัลกอริทึมสำหรับการสร้างเครือข่ายแบบไร้มาตราส่วน แบบสุ่ม โดยใช้ กลไก การเชื่อมต่อแบบเลือก ปฏิบัติ ระบบธรรมชาติและระบบที่มนุษย์สร้างขึ้นหลายระบบ รวมถึงอินเทอร์เน็ต เครือข่าย เวิลด์ไวด์เว็บเครือข่ายการอ้างอิงและเครือข่ายสังคม บางเครือข่าย เชื่อกันว่าเป็นเครือข่ายแบบไร้มาตราส่วนโดยประมาณ และแน่นอนว่ามีโหนดจำนวนน้อย (เรียกว่าฮับ) ที่มีดีกรีสูงผิดปกติเมื่อเทียบกับโหนดอื่นๆ ในเครือข่าย แบบจำลอง BA พยายามอธิบายการมีอยู่ของโหนดดังกล่าวในเครือข่ายจริง อัลกอริทึมนี้ตั้งชื่อตามผู้คิดค้นคือAlbert-László BarabásiและRéka Albert

เครือข่ายที่สังเกตได้จำนวนมาก (อย่างน้อยก็โดยประมาณ) จัดอยู่ในประเภทของเครือข่ายไร้มาตราส่วนซึ่งหมายความว่าเครือข่ายเหล่านั้นมี การกระจายระดับ ดีกรีแบบกฎกำลัง (หรือไร้มาตราส่วน) ในขณะที่แบบจำลองกราฟสุ่ม เช่นแบบจำลอง Erdős–Rényi (ER)และแบบจำลอง Watts–Strogatz (WS)ไม่แสดงลักษณะกฎกำลัง แบบจำลอง Barabási–Albert เป็นหนึ่งในแบบจำลองที่เสนอหลายแบบที่สร้างเครือข่ายไร้มาตราส่วน โดยรวมเอาแนวคิดทั่วไปที่สำคัญสองประการ ได้แก่ การเติบโตและการเชื่อมต่อแบบเลือกปฏิบัติทั้งการเติบโตและการเชื่อมต่อแบบเลือกปฏิบัตินั้นพบได้ทั่วไปในเครือข่ายจริง

การเติบโตหมายถึงจำนวนโหนดในเครือข่ายเพิ่มขึ้นเมื่อเวลาผ่านไป

การเชื่อมโยงแบบเลือกปฏิบัติ (Preferential attachment)หมายความว่า โหนดที่เชื่อมต่อกันมากเท่าไหร่ ก็ยิ่งมีโอกาสได้รับลิงก์ใหม่มากขึ้นเท่านั้น โหนดที่มีระดับ การเชื่อมต่อสูงกว่า จะมีศักยภาพในการดึงดูดลิงก์ที่เพิ่มเข้ามาในเครือข่ายได้มากกว่า โดยทั่วไปแล้ว เราสามารถเข้าใจการเชื่อมโยงแบบเลือกปฏิบัติได้หากเรานึกถึงเครือข่ายสังคมที่เชื่อมโยงผู้คนเข้าด้วยกัน ในที่นี้ ลิงก์จาก A ไป B หมายความว่าบุคคล A "รู้จัก" หรือ "คุ้นเคย" กับบุคคล B โหนดที่มีการเชื่อมโยงอย่างหนาแน่นแสดงถึงบุคคลที่รู้จักกันดีและมีเครือข่ายความสัมพันธ์มากมาย เมื่อผู้มาใหม่เข้าสู่ชุมชน พวกเขามีแนวโน้มที่จะทำความรู้จักกับบุคคลที่มีชื่อเสียงมากกว่าที่จะทำความรู้จักกับบุคคลที่ไม่ค่อยมีใครรู้จัก แบบจำลอง BA ถูกเสนอขึ้นโดยสมมติว่าในเวิลด์ไวด์เว็บ หน้าเว็บใหม่ๆ จะเชื่อมโยงไปยังศูนย์กลาง (hub) มากกว่า กล่าวคือ เว็บไซต์ที่รู้จักกันดีมาก เช่นGoogleมากกว่าหน้าเว็บที่แทบไม่มีใครรู้จัก หากใครบางคนเลือกหน้าเว็บใหม่ที่จะเชื่อมโยงโดยการสุ่มเลือกจากลิงก์ที่มีอยู่แล้ว ความน่าจะเป็นในการเลือกหน้าเว็บนั้นจะแปรผันตรงกับระดับการเชื่อมต่อของลิงก์นั้น แบบจำลอง BA อ้างว่านี่คือคำอธิบายของกฎความน่าจะเป็นของการเชื่อมโยงแบบเลือกปฏิบัติ

ต่อมาโมเดล Bianconi–Barabásiพยายามแก้ไขปัญหานี้โดยการแนะนำพารามิเตอร์ "ความเหมาะสม" การเชื่อมต่อแบบเลือกปฏิบัติเป็นตัวอย่างของ วงจร ป้อนกลับเชิงบวกซึ่งความแปรผันแบบสุ่มในตอนเริ่มต้น (โหนดหนึ่งมีจำนวนลิงก์มากกว่าหรือเริ่มสะสมลิงก์เร็วกว่าโหนดอื่น) จะได้รับการเสริมแรงโดยอัตโนมัติ ทำให้ความแตกต่างนั้นขยายใหญ่ขึ้นอย่างมาก บางครั้งเรียกสิ่งนี้ว่าปรากฏการณ์แมทธิว หรือ " คนรวยยิ่งรวยขึ้น " ดูเพิ่มเติมที่การเร่งปฏิกิริยาอัตโนมัติ

พารามิเตอร์เพียงตัวเดียวในแบบจำลอง BA คือจำนวนเต็มบวก เครือข่ายเริ่มต้นด้วยเครือข่ายของโหนด ${\displaystyle m}$${\displaystyle m_{0}\geq m}$

ในแต่ละขั้นตอน ให้เพิ่มโหนดใหม่หนึ่งโหนด จากนั้นสุ่มเลือกเพื่อนบ้านจากจุดยอดที่มีอยู่ของเครือข่าย โดยมีความน่าจะเป็นที่แปรผันตามจำนวนลิงก์ที่โหนดที่มีอยู่มีอยู่แล้ว (เอกสารต้นฉบับไม่ได้ระบุวิธีการจัดการกรณีที่เลือกโหนดที่มีอยู่เดียวกันหลายครั้ง) ตามหลักการแล้ว ความน่าจะเป็นที่โหนดใหม่จะเชื่อมต่อกับโหนดคือ^{[ 1 ]}${\displaystyle m}$${\displaystyle p_{i}}$${\displaystyle i}$

${\displaystyle p_{i}={\frac {k_{i}}{\sum _{j}k_{j}}},}$

โดยที่คือระดับของโหนดและผลรวมจะคำนวณจากโหนดที่มีอยู่ทั้งหมด(กล่าวคือ ตัวหารจะมีค่าเป็นสองเท่าของจำนวนขอบปัจจุบันในเครือข่าย) ขั้นตอนนี้สามารถทำได้โดยการสุ่มเลือกขอบหนึ่งเส้นอย่างสม่ำเสมอก่อน จากนั้นจึงสุ่มเลือกจุดยอดหนึ่งในสองจุดบนขอบนั้น ${\displaystyle k_{i}}$${\displaystyle i}$${\displaystyle j}$

โหนดที่มีการเชื่อมโยงหนาแน่น ("ฮับ") มักจะสะสมการเชื่อมโยงเพิ่มขึ้นอย่างรวดเร็ว ในขณะที่โหนดที่มีการเชื่อมโยงเพียงไม่กี่แห่งมีโอกาสน้อยที่จะถูกเลือกเป็นปลายทางสำหรับการเชื่อมโยงใหม่ โหนดใหม่มัก "ชอบ" ที่จะเชื่อมต่อกับโหนดที่มีการเชื่อมโยงหนาแน่นอยู่แล้ว

การกระจายระดับดีกรีที่ได้จากแบบจำลอง BA นั้นเป็นแบบไร้มาตราส่วน โดยเฉพาะอย่างยิ่ง มันเป็นกฎกำลังในรูปแบบ

${\displaystyle P(k)\sim k^{-3}\,}$

การกระจายของ ดัชนีhหรือดัชนี Hirsch แสดงให้เห็นว่าไม่มีมาตราส่วนและเสนอให้เป็นดัชนีล็อบบี้เพื่อใช้เป็นมาตรวัดความเป็นศูนย์กลาง^{[ 2 ]}

${\displaystyle H(k)\sim k^{-6}\,}$

นอกจากนี้ ยังสามารถหาผลการวิเคราะห์ความหนาแน่นของโหนดที่มีดัชนี h เท่ากับ 1 ได้ในกรณีที่${\displaystyle m_{0}=1}$

${\displaystyle H(1){\Big |}_{m_{0}=1}=4-\pi \,}$

ความสัมพันธ์ระหว่างระดับของโหนดที่เชื่อมต่อกันเกิดขึ้นเองโดยธรรมชาติในแบบจำลอง BA เนื่องมาจากวิวัฒนาการของเครือข่าย ความน่าจะเป็นของการพบลิงก์ที่เชื่อมต่อโหนดที่มีระดับ กับโหนดบรรพบุรุษที่มีระดับ ในแบบจำลอง BA สำหรับกรณีพิเศษของ(ต้นไม้ BA) กำหนดโดย ${\displaystyle n_{k\ell }}$${\displaystyle k}$${\displaystyle \ell }$${\displaystyle m=1}$

${\displaystyle n_{k\ell }={\frac {4\left(\ell -1\right)}{k\left(k+1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}+{\frac {12\left(\ell -1\right)}{k\left(k+\ell -1\right)\left(k+\ell \right)\left(k+\ell +1\right)\left(k+\ell +2\right)}}.}$

สิ่งนี้ยืนยันการมีอยู่ของความสัมพันธ์ระดับ เนื่องจากหากการกระจายไม่สัมพันธ์กัน เราจะได้^{[ 1 ]}${\displaystyle n_{k\ell }=k^{-3}\ell ^{-3}}$

โดยทั่วไปสัดส่วนของลิงก์ที่เชื่อมต่อโหนดที่มีดีกรี กับโหนดที่มีดีกรี คือ^{[ 3 ]}${\displaystyle m}$${\displaystyle k}$${\displaystyle \ell }$

${\displaystyle p(k,\ell )={\frac {2m(m+1)}{k(k+1)\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

นอกจากนี้ การกระจายระดับเพื่อนบ้านที่ใกล้ที่สุดนั่นคือ การกระจายระดับของเพื่อนบ้านของโหนดที่มีระดับจะได้รับจาก^{[ 3 ]}${\displaystyle p(\ell \mid k)}$${\displaystyle k}$

${\displaystyle p(\ell \mid k)={\frac {m(k+2)}{k\ell (\ell +1)}}\left[1-{\frac {{\binom {2m+2}{m+1}}{\binom {k+\ell -2m}{\ell -m}}}{\binom {k+\ell +2}{\ell +1}}}\right].}$

กล่าวอีกนัยหนึ่ง หากเราเลือกโหนดที่มีดีกรี แล้วสุ่มเลือกโหนดข้างเคียงหนึ่งโหนด ความน่าจะเป็นที่โหนดข้างเคียงที่สุ่มเลือกนี้จะมีดีกรี จะคำนวณได้จากสูตรข้างต้น ${\displaystyle k}$${\displaystyle \ell }$${\displaystyle p(\ell |k)}$

กรณีนี้ เป็นเรื่องง่าย: เครือข่ายเป็นต้นไม้และสัมประสิทธิ์การจัดกลุ่มเท่ากับศูนย์ ผลลัพธ์เชิงวิเคราะห์สำหรับสัมประสิทธิ์การจัดกลุ่มของแบบจำลอง BA ได้รับโดย Klemm และ Eguíluz ^{[ 4 ]}และได้รับการพิสูจน์โดย Bollobás ^{[ 5 ]}แนวทางสนามเฉลี่ยเพื่อศึกษาค่าสัมประสิทธิ์การจัดกลุ่มถูกนำมาใช้โดย Fronczak, Fronczak และ Holyst ^{[ 6 ]}${\displaystyle m=1}$

ค่าสัมประสิทธิ์การจัดกลุ่มเฉลี่ยของแบบจำลอง Barabási–Albert ขึ้นอยู่กับขนาดของเครือข่าย N:

${\displaystyle \langle C\rangle \sim lnN^{2}/N.}$

พฤติกรรมนี้แตกต่างจากพฤติกรรมของเครือข่ายแบบโลกขนาดเล็ก (small-world networks) ซึ่งการจัดกลุ่มจะไม่ขึ้นอยู่กับขนาดของระบบ

การจัดกลุ่มตามระดับของโหนด แทบจะไม่ขึ้นอยู่กับ^{[ 6 ]}${\displaystyle C(k)}$${\displaystyle k}$

ความหนาแน่นสเปกตรัมของแบบจำลอง BA มีรูปร่างที่แตกต่างจากความหนาแน่นสเปกตรัมแบบครึ่งวงกลมของกราฟสุ่ม มีรูปร่างคล้ายสามเหลี่ยม โดยส่วนบนอยู่เหนือครึ่งวงกลมและขอบลดลงตามกฎกำลัง^{[ 7 ]}ใน^{[ 8 ]} (ส่วนที่ 5.1) พิสูจน์แล้วว่ารูปร่างของความหนาแน่นสเปกตรัมนี้ไม่ใช่ฟังก์ชันสามเหลี่ยมที่แน่นอน โดยการวิเคราะห์โมเมนต์ของความหนาแน่นสเปกตรัมเป็นฟังก์ชันของเลขชี้กำลังของกฎกำลัง

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

แบบจำลอง B ยังคงรักษาการเชื่อมต่อแบบเลือกปฏิบัติไว้ แต่ตัดการเติบโตออกไป แบบจำลองเริ่มต้นด้วยจำนวนโหนดที่ไม่เชื่อมต่อกันคงที่ และเพิ่มลิงก์ โดยเลือกโหนดที่มีดีกรีสูงเป็นปลายทางของลิงก์ก่อน แม้ว่าการกระจายดีกรีในช่วงแรกของการจำลองจะดูเหมือนแบบไร้มาตราส่วน แต่การกระจายนั้นไม่เสถียร และในที่สุดก็จะกลายเป็นแบบเกาส์เซียนเกือบทั้งหมดเมื่อเครือข่ายใกล้ถึงจุดอิ่มตัว ดังนั้นการเชื่อมต่อแบบเลือกปฏิบัติเพียงอย่างเดียวจึงไม่เพียงพอที่จะสร้างโครงสร้างแบบไร้มาตราส่วนได้

ความล้มเหลวของแบบจำลอง A และ B ในการนำไปสู่การกระจายแบบไร้มาตราส่วนแสดงให้เห็นว่าการเติบโตและการเชื่อมต่อแบบพิเศษจำเป็นต้องเกิดขึ้นพร้อมกันเพื่อสร้างการกระจายแบบกฎกำลัง คงที่ ที่สังเกตได้ในเครือข่ายจริง^{[ 1 ]}

แบบจำลอง BA สามารถคิดได้ว่าเป็นกรณีเฉพาะของแบบจำลองการยึดติดแบบไม่เชิงเส้นทั่วไป (NLPA) ^{[ 10 ]}อัลกอริทึม NLPA เหมือนกับแบบจำลอง BA โดยที่ความน่าจะเป็นของการยึดติดถูกแทนที่ด้วยรูปแบบทั่วไปมากกว่า

${\displaystyle p_{i}={\frac {k_{i}^{\alpha }}{\sum _{j}k_{j}^{\alpha }}},}$

โดยที่เป็นเลขชี้กำลังบวกคงที่ ถ้าNLPA จะลดลงเหลือแบบจำลอง BA และเรียกว่า "เชิงเส้น" ถ้าNLPA เรียกว่า "กึ่งเชิงเส้น" และการกระจายระดับของเครือข่ายมีแนวโน้มที่จะเป็นการกระจายแบบเลขชี้กำลังแบบยืดถ้าNLPA เรียกว่า "เหนือเชิงเส้น" และโหนดจำนวนน้อยเชื่อมต่อกับโหนดอื่นๆ เกือบทั้งหมดในเครือข่าย สำหรับทั้งและคุณสมบัติไร้มาตราส่วนของเครือข่ายจะถูกทำลายในขีดจำกัดของขนาดระบบอนันต์ อย่างไรก็ตาม ถ้ามีค่ามากกว่า เพียงเล็กน้อยNLPA อาจส่งผลให้การกระจายระดับดูเหมือนจะไร้มาตราส่วนชั่วคราว^{[ 11 ]}${\displaystyle \alpha }$${\displaystyle \alpha =1}$${\displaystyle 0<\alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha <1}$${\displaystyle \alpha >1}$${\displaystyle \alpha }$${\displaystyle 1}$

การเชื่อมโยงแบบเลือกปฏิบัติปรากฏขึ้นครั้งแรกในปี 1923 ในแบบจำลองโถที่มีชื่อเสียงของนักคณิตศาสตร์ชาวฮังการีGyörgy Pólyaในปี 1923 ^{[ 12 ]} วิธีสมการหลักซึ่งให้การพิสูจน์ที่โปร่งใสกว่า ถูกนำมาใช้กับปัญหาโดยHerbert A. Simonในปี 1955 ^{[ 13 ]}ในระหว่างการศึกษาขนาดของเมืองและปรากฏการณ์อื่นๆ มีการนำมาใช้ครั้งแรกเพื่ออธิบายความถี่ของการอ้างอิงโดยDerek de Solla Priceในปี 1976 ^{[ 14 ]} Price สนใจในการสะสมการอ้างอิงของเอกสารทางวิทยาศาสตร์ และแบบจำลองของ Priceใช้ "ข้อได้เปรียบสะสม" (ชื่อที่เขาใช้เรียกการเชื่อมโยงแบบเลือกปฏิบัติ) เพื่อสร้างการกระจายแบบหางหนา ในภาษาของเครือข่ายการอ้างอิงสมัยใหม่ แบบจำลองของ Price สร้างเครือข่ายแบบมีทิศทาง นั่นคือเวอร์ชันของแบบจำลอง Barabási–Albert ชื่อ "การแนบแบบพิเศษ" และความนิยมในปัจจุบันของแบบจำลองเครือข่ายแบบไร้มาตราส่วนเป็นผลมาจากงานของAlbert-László BarabásiและRéka Albertซึ่งค้นพบว่ากระบวนการที่คล้ายกันนี้มีอยู่ในเครือข่ายจริง และในปี 1999 ได้นำการแนบแบบพิเศษมาใช้เพื่ออธิบายการกระจายระดับที่สังเกตได้ทางตัวเลขบนเว็บ^{[ 15 ]}

• แบบจำลอง Bianconi–Barabási
• กระบวนการร้านอาหารจีน
• เครือข่ายที่ซับซ้อน
• แบบจำลอง Erdős–Rényi (ER)
• โมเดลของไพรซ์
• ทฤษฎีการซึมผ่าน
• เครือข่ายไร้มาตราส่วน
• เครือข่ายโลกขนาดเล็ก
• แบบจำลองวัตต์และสโตรกาตซ์

• "ชายคนนี้สามารถครองโลกได้"
• "การนำ Java ไปใช้สำหรับBarabási–Albert"
• "การสร้างกราฟโมเดลBarabási–Albert ในโค้ด"