กราฟเรขาคณิตไฮเปอร์โบลิก (HGG)หรือเครือข่ายเรขาคณิตไฮเปอร์โบลิก (HGN) เป็น เครือข่ายเชิงพื้นที่ชนิดพิเศษที่ (1) พิกัดแฝงของโหนดถูกกระจายตามฟังก์ชันความหนาแน่นความน่าจะเป็นลงใน พื้นที่ไฮเปอร์โบลิกที่มีความโค้งลบคงที่และ (2) จะมี ขอบระหว่างสองโหนดหากโหนดเหล่านั้นอยู่ใกล้กันตามฟังก์ชันของเมตริก^{[ 1 ] [ 2 ]} (โดยทั่วไป จะเป็น ฟังก์ชันขั้นบันไดของ Heavisideซึ่งส่งผลให้เกิดการเชื่อมต่อแบบกำหนดระหว่างจุดยอดที่อยู่ใกล้กันมากกว่าระยะทางเกณฑ์ที่กำหนด หรือฟังก์ชันที่ลดลงของระยะทางไฮเปอร์โบลิกซึ่งให้ความน่าจะเป็นของการเชื่อมต่อ) HGG เป็นการขยายความของกราฟเรขาคณิตแบบสุ่ม (RGG) ซึ่งพื้นที่ฝังตัวเป็นแบบยุคลิด

ในทางคณิตศาสตร์HGGคือกราฟ ที่มี เซตของจุดยอดV ( จำนวนสมาชิก ) และเซตของขอบEซึ่งสร้างขึ้นโดยพิจารณาจุดยอดเป็นจุดที่วางอยู่บนปริภูมิไฮเปอร์โบลิก 2 มิติ ที่มีความโค้งเกาส์เซียน เชิงลบคงที่และรัศมีตัดขอบ นั่นคือ รัศมีของจานปวงกาเรซึ่งสามารถมองเห็นได้โดยใช้แบบจำลองไฮเปอร์โบโลอิดจุดแต่ละจุดมีพิกัดเชิงขั้วไฮเปอร์โบลิกโดยมีและ${\displaystyle G(V,E)}$${\displaystyle N=|V|}$${\displaystyle \mathbb {H} _{\zeta }^{2}}$${\displaystyle -\zeta ^{2}}$${\displaystyle R}$${\displaystyle i}$${\displaystyle (r_{i},\theta _{i})}$${\displaystyle 0\leq r_{i}\leq R}$${\displaystyle 0\leq \theta _{i}<2\pi }$

กฎไฮเปอร์โบลิกของโคไซน์ช่วยให้สามารถวัดระยะห่าง ระหว่าง ^จุดสองจุดได้[ ^{2 ]}${\displaystyle d_{ij}}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle \cosh(\zeta d_{ij})=\cosh(\zeta r_{i})\cosh(\zeta r_{j})}$${\displaystyle -\sinh(\zeta r_{i})\sinh(\zeta r_{j})\cos {\bigg (}\underbrace {\pi \!-\!{\bigg |}\pi -|\theta _{i}\!-\!\theta _{j}|{\bigg |}} _{\Delta }{\bigg )}.}$

มุมดังกล่าว  คือมุม (ที่เล็กที่สุด) ระหว่าง เวก เตอร์ตำแหน่ง ทั้งสอง${\displaystyle \Delta }$

ในกรณีที่ง่ายที่สุดจะมีการสร้างเส้นเชื่อมก็ต่อเมื่อโหนดสองโหนดอยู่ภายในรัศมีบริเวณใกล้เคียง ที่ กำหนดซึ่งสอดคล้องกับเกณฑ์อิทธิพล ${\displaystyle (i,j)}$ ${\displaystyle r}$${\displaystyle d_{ij}\leq r}$

โดยทั่วไปแล้ว การเชื่อมโยงจะถูกสร้างขึ้นด้วยความน่าจะเป็นที่ขึ้นอยู่กับระยะทาง  ฟังก์ชันการลดลงของการเชื่อมต่อแสดงถึงความน่าจะเป็นของการกำหนดขอบให้กับคู่ของโหนดที่ระยะทางในกรอบงานนี้ กรณีง่ายๆ ของ เพื่อนบ้าน ที่กำหนดไว้ตายตัวเช่นในกราฟเรขาคณิตแบบสุ่มเรียกว่าฟังก์ชันการลดลงของการตัด^ทอน [ ^{3 ]}${\displaystyle d_{ij}}$${\displaystyle \gamma (s):\mathbb {R} ^{+}\to [0,1]}$${\displaystyle s}$

Krioukov และคณะ^{[ 2 ]}อธิบายวิธีการสร้างกราฟเรขาคณิตไฮเปอร์โบลิกที่มีการกระจายโหนดแบบสุ่มสม่ำเสมอ (รวมถึงเวอร์ชันทั่วไป) บนดิสก์รัศมีในกราฟเหล่านี้ให้ผลลัพธ์เป็นการกระจายแบบกำลังสำหรับระดับโหนด พิกัดเชิงมุมของแต่ละจุด/โหนดจะถูกเลือกแบบสุ่มสม่ำเสมอจากในขณะที่ฟังก์ชันความหนาแน่นสำหรับพิกัดรัศมี r จะถูกเลือกตามการกระจายความน่าจะเป็น : ${\displaystyle R}$${\displaystyle \mathbb {H} _{\zeta }^{2}}$${\displaystyle \theta }$${\displaystyle [0,2\pi ]}$${\displaystyle \rho }$

${\displaystyle \rho (r)=\alpha {\frac {\sinh(\alpha r)}{\cosh(\alpha R)-1}}}$

พารามิเตอร์การเติบโตควบคุมการกระจาย: สำหรับ ค่า การกระจายจะเป็นแบบสม่ำเสมอในสำหรับค่าที่น้อยกว่า โหนดจะกระจายไปทางศูนย์กลางของดิสก์มากขึ้น และสำหรับค่าที่มากกว่าจะกระจายไปทางขอบมากขึ้น ในแบบจำลองนี้ ขอบระหว่างโหนดและจะมีอยู่ก็ต่อเมื่อหรือด้วยความน่าจะเป็นถ้าใช้ฟังก์ชันการลดลงของการเชื่อมต่อทั่วไปมากขึ้น ระดับเฉลี่ยถูกควบคุมโดยรัศมีของดิสก์ไฮเปอร์โบลิก สามารถแสดงได้ว่าสำหรับค่า ระดับของโหนดจะเป็นไปตามการกระจายแบบกฎกำลังที่มีเลขชี้กำลัง ${\displaystyle \alpha >0}$${\displaystyle \alpha =\zeta }$${\displaystyle \mathbb {H} _{\zeta }^{2}}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d_{uv}<R}$${\displaystyle \gamma (d_{uv})}$${\displaystyle R}$${\displaystyle \alpha /\zeta >1/2}$${\displaystyle \gamma =1+2\alpha /\zeta }$

ภาพนี้แสดงกราฟที่สร้างขึ้นแบบสุ่มสำหรับค่าต่างๆ ของและในจะเห็นได้ว่ามีผลต่อการกระจายตัวของโหนดและการเชื่อมต่อของกราฟอย่างไร การแสดงผลกราฟใช้รูปแบบดั้งเดิมที่ตัวแปรระยะทางมีค่าไฮเปอร์โบลิกที่แท้จริง ดังนั้นขอบจึงเป็นเส้นตรง${\displaystyle \alpha }$${\displaystyle R}$${\displaystyle \mathbb {H} _{1}^{2}}$${\displaystyle \alpha }$${\displaystyle R}$

แหล่งที่มา: ^{[ 4 ]}

อัลกอริทึมแบบง่ายสำหรับการสร้างกราฟเรขาคณิตไฮเปอร์โบลิกจะกระจายโหนดบนดิสก์ไฮเปอร์โบลิกโดยการเลือกพิกัดเชิงมุมและรัศมีของแต่ละจุดแบบสุ่ม จากนั้นสำหรับแต่ละคู่ของโหนด จะมีการแทรกขอบด้วยความน่าจะเป็นของค่าฟังก์ชันการลดลงของการเชื่อมต่อของระยะทางระหว่างโหนดนั้นๆ รหัสเทียมมีลักษณะดังนี้:

${\displaystyle V=\{\},E=\{\}}$สำหรับทุกคู่ให้ทำถ้าแล้วส่งคืน${\displaystyle i\gets 0}$${\displaystyle N-1}$${\displaystyle \theta \gets U[0,2\pi ]}$${\displaystyle r\gets {\frac {1}{\alpha }}{\text{acosh}}(1+(\cosh \alpha R-1)U[0,1])}$${\displaystyle V=V\cup \{(r,\theta )\}}$${\displaystyle (u,v)\in V\times V,u\neq v}$${\displaystyle U[0,1]\leq \gamma (d_{uv})}$${\displaystyle E=E\ถ้วย \{(u,v)\}}$${\displaystyle V,E}$

${\displaystyle N}$คือจำนวนโหนดที่จะสร้าง การกระจายพิกัดรัศมีโดยฟังก์ชันความหนาแน่นของความน่าจะเป็นทำได้โดยใช้การสุ่มตัวอย่างแบบแปลงผกผันหมายถึงการสุ่มตัวอย่างแบบสม่ำเสมอของค่าในช่วงที่กำหนด เนื่องจากอัลกอริทึมตรวจสอบขอบสำหรับทุกคู่ของโหนด เวลาในการทำงานจึงเป็นแบบกำลังสอง สำหรับแอปพลิเคชันที่มีขนาดใหญ่ วิธีนี้จึงไม่เหมาะสมอีกต่อไป และจำเป็นต้องใช้อัลกอริทึมที่มีเวลาในการทำงานต่ำกว่ากำลังสอง ${\displaystyle \rho }$${\displaystyle U}$${\displaystyle N}$

เพื่อหลีกเลี่ยงการตรวจสอบขอบระหว่างโหนดทุกคู่ ตัวสร้างสมัยใหม่ใช้โครงสร้างข้อมูล เพิ่มเติม ที่แบ่งกราฟออกเป็นแถบ^{[ 5 ] [ 6 ]}การแสดงภาพนี้แสดงให้เห็นกราฟไฮเปอร์โบลิกที่มีขอบเขตของแถบวาดด้วยสีส้ม ในกรณีนี้ การแบ่งจะทำตามแกนรัศมี จุดต่างๆ จะถูกจัดเก็บเรียงลำดับตามพิกัดเชิงมุมในแถบที่เกี่ยวข้อง สำหรับแต่ละจุดขอบเขตของวงกลมไฮเปอร์โบลิกที่มีรัศมีสามารถประมาณค่า (เกิน) และใช้เพื่อทำการตรวจสอบขอบเฉพาะจุดที่อยู่ในแถบที่ตัดกับวงกลมเท่านั้น นอกจากนี้ การเรียงลำดับภายในแต่ละแถบยังสามารถใช้เพื่อลดจำนวนจุดที่จะพิจารณาลงได้อีก โดยพิจารณาเฉพาะจุดที่มีพิกัดเชิงมุมอยู่ในช่วงที่กำหนดรอบๆ จุดหนึ่ง(ช่วงนี้คำนวณโดยการประมาณค่าเกินของวงกลมไฮเปอร์โบลิกรอบๆ เช่นกัน) ${\displaystyle u}$${\displaystyle R}$${\displaystyle u}$${\displaystyle u}$

การใช้อัลกอริธึมนี้และส่วนขยายอื่นๆ จะทำให้ความซับซ้อนของเวลา(โดยที่คือจำนวนโหนด และคือจำนวนขอบ) เป็นไปได้ด้วยความน่าจะเป็นสูง^{[ 7 ]}${\displaystyle {\mathcal {O}}(n\log \log n+m)}$${\displaystyle n}$${\displaystyle m}$

สำหรับ(ความโค้งแบบเกาส์เซียน) HGGs ก่อตัวเป็นกลุ่มของเครือข่ายซึ่งสามารถแสดงการกระจายระดับในเชิงวิเคราะห์ได้ในรูปแบบปิดสำหรับกรณีจำกัดของจำนวนโหนดจำนวนมาก^{[ 2 ]}สิ่งนี้ควรค่าแก่การกล่าวถึงเนื่องจากสิ่งนี้ไม่เป็นจริงสำหรับกลุ่มของกราฟจำนวนมาก ${\displaystyle \zeta =1}$${\displaystyle K=-1}$

HGG ได้รับการเสนอแนะให้เป็นแบบจำลองที่น่าสนใจสำหรับเครือข่ายสังคมโดยที่ความเกินจริงปรากฏขึ้นผ่านการแข่งขันระหว่างความคล้ายคลึงและความนิยมของแต่ละบุคคล^{[ 8 ]}