ในทฤษฎีเครือข่ายการทำนายการเชื่อมโยงคือปัญหาของการทำนายการมีอยู่ของการเชื่อมโยงระหว่างสองเอนทิตีในเครือข่าย ตัวอย่างของการทำนายการเชื่อมโยง ได้แก่ การทำนายการเชื่อมโยงมิตรภาพระหว่างผู้ใช้ในเครือข่ายสังคมการทำนายการเชื่อมโยงการเขียนร่วมกันในเครือข่ายการอ้างอิงและการทำนายปฏิสัมพันธ์ระหว่างยีนและโปรตีนในเครือข่ายชีวภาพการทำนายการเชื่อมโยงยังสามารถมีแง่มุมเชิงเวลาได้ โดยเมื่อกำหนดภาพรวมของชุดการเชื่อมโยง ณ เวลาหนึ่งเป้าหมายคือการทำนายการเชื่อมโยง ณ เวลาถัดไปการทำนายการเชื่อมโยงสามารถนำไปประยุกต์ใช้ได้อย่างกว้างขวาง ในอีคอมเมิร์ซ การทำนายการเชื่อมโยงมักเป็นงานย่อยสำหรับการแนะนำสินค้าให้กับผู้ใช้ ในการจัดการฐานข้อมูลการอ้างอิง สามารถใช้สำหรับการลบข้อมูลซ้ำซ้อน ในชีวสารสนเทศศาสตร์ มีการใช้เพื่อทำนายปฏิสัมพันธ์ระหว่างโปรตีนกับโปรตีน (PPI) นอกจากนี้ยังใช้เพื่อระบุกลุ่มผู้ก่อการร้ายและอาชญากรที่ซ่อนตัวอยู่ในการใช้งานที่เกี่ยวข้องกับความปลอดภัย^{[ 1 ]}${\displaystyle t}$${\displaystyle t+1}$

พิจารณาเครือข่ายโดยที่แทนโหนดเอนทิตีในเครือข่าย และx แทนเซตของลิงก์ "จริง" ระหว่างเอนทิตีในเครือข่าย เราได้รับเซตของเอนทิตีและเซตย่อยของลิงก์จริง ซึ่งเรียกว่าลิงก์ที่สังเกตได้เป้าหมายของการทำนายลิงก์คือการระบุลิงก์จริงที่ยังไม่ถูกสังเกต ในการกำหนดรูปแบบเชิงเวลาของการทำนายลิงก์ ลิงก์ที่สังเกตได้จะสอดคล้องกับลิงก์จริง ณ เวลา t และเป้าหมายคือการอนุมานเซตของลิงก์จริง ณ เวลา t โดยปกติแล้ว เราจะได้รับเซตย่อยของลิงก์ที่ยังไม่ถูกสังเกต เรียกว่าลิงก์ที่มีศักยภาพและเราจำเป็นต้องระบุลิงก์จริงในบรรดาลิงก์ที่มีศักยภาพเหล่านี้ ${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E\ชุดย่อย |V|}$${\displaystyle |V|}$${\displaystyle V}$${\displaystyle t}$${\displaystyle t+1}$${\displaystyle E'}$

ใน การกำหนด รูปแบบการจำแนกแบบไบนารีของงานทำนายลิงก์ ลิงก์ที่เป็นไปได้จะถูกจำแนกเป็นลิงก์จริงหรือลิงก์เท็จ วิธีการทำนายลิงก์สำหรับสถานการณ์นี้จะเรียนรู้ตัวจำแนกที่แมปลิงก์ไปยังป้ายกำกับบวกและลบในการกำหนดรูปแบบการประมาณความน่าจะเป็น ลิงก์ที่เป็นไปได้จะเชื่อมโยงกับความน่าจะเป็นของการมีอยู่ วิธีการทำนายลิงก์สำหรับสถานการณ์นี้จะเรียนรู้แบบจำลองที่แมปลิงก์ไปยังความน่าจะเป็น ${\displaystyle M_{b}}$${\displaystyle E'}$${\displaystyle M_{b}:E'\to \{0,1\}}$${\displaystyle M_{p}}$${\displaystyle E'}$${\displaystyle M_{p}:E'\to [0,1]}$

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

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

งานการทำนายลิงก์ได้รับความสนใจจากชุมชนวิจัยหลายแห่ง ตั้งแต่สถิติและวิทยาศาสตร์เครือข่ายไปจนถึงการเรียนรู้ของเครื่องและการขุดข้อมูลในทางสถิติ โมเดลกราฟสุ่มแบบสร้าง เช่นโมเดลบล็อกสุ่มเสนอแนวทางในการสร้างลิงก์ระหว่างโหนดในกราฟสุ่มสำหรับเครือข่ายสังคม Liben-Nowell และ Kleinberg เสนอโมเดลการทำนายลิงก์โดยอิงจากการวัดความใกล้เคียงของกราฟที่แตกต่างกัน^{[ 2 ]} ชุมชนการเรียนรู้ของเครื่องและการขุดข้อมูลได้เสนอโมเดลทางสถิติหลายแบบสำหรับการทำนายลิงก์ ตัวอย่างเช่น Popescul และคณะ เสนอ โมเดล การถดถอยโลจิสติก แบบมีโครงสร้าง ที่สามารถใช้คุณลักษณะเชิงสัมพันธ์ได้^{[ 3 ]} O'Madadhain และคณะ เสนอโมเดลความน่าจะเป็นแบบมีเงื่อนไขเฉพาะที่อิงตามคุณลักษณะและคุณลักษณะเชิงโครงสร้าง^{[ 4 ]} Getoor เสนอโมเดลหลายแบบที่อิงตามโมเดลกราฟิกแบบมีทิศทางสำหรับการทำนายลิงก์แบบรวม^{[ 5 ]} แนวทางอื่นๆ ที่อิงตามการเดินแบบสุ่ม^{[ 6 ]}และการแยกตัวประกอบเมทริกซ์ก็ได้รับการเสนอเช่นกัน^{[ 7 ]} ด้วยการมาถึงของการเรียนรู้เชิงลึก วิธีการฝังกราฟหลายวิธีสำหรับการทำนายลิงก์ก็ได้รับการเสนอเช่นกัน^{[ 8 ]} สำหรับข้อมูลเพิ่มเติมเกี่ยวกับการทำนายลิงก์ โปรดดูการสำรวจโดย Getoor et al. ^{[ 9 ]}และ Yu et al. ^{[ 10 ]}

มีการเสนอแนวทางการทำนายลิงก์หลายวิธี รวมถึงแนวทางที่ไม่ต้องมีการกำกับดูแล เช่น การวัดความคล้ายคลึงที่คำนวณจากคุณลักษณะของเอนทิตี วิธี การเดินแบบสุ่มและการแยกตัวประกอบเมทริกซ์และแนวทางที่มีการกำกับดูแล โดยอิงจากแบบ จำลองกราฟิกและการเรียนรู้เชิงลึกแนวทางการทำนายลิงก์สามารถแบ่งออกเป็นสองประเภทใหญ่ๆ ตามประเภทของเครือข่ายพื้นฐาน: (1) แนวทางการทำนายลิงก์สำหรับเครือข่ายที่เป็นเนื้อเดียวกัน (2) แนวทางการทำนายลิงก์สำหรับเครือข่ายที่ไม่เป็นเนื้อเดียวกัน ตามประเภทของข้อมูลที่ใช้ในการทำนายลิงก์ แนวทางต่างๆ สามารถจำแนกได้เป็นแนวทางตามโทโพโลยี แนวทางตามเนื้อหา และวิธีการแบบผสม^{[ 11 ]}

วิธีการเชิงโทโพโลยีโดยทั่วไปตั้งสมมติฐานว่า โหนดที่มีโครงสร้างเครือข่ายคล้ายคลึงกัน มีแนวโน้มที่จะสร้างการเชื่อมโยงกันได้มากกว่า

นี่เป็นวิธีการทั่วไปในการทำนายความเชื่อมโยง ซึ่งจะคำนวณจำนวนเพื่อนบ้านร่วมกัน เอนทิตีที่มีเพื่อนบ้านร่วมกันมากขึ้น มีแนวโน้มที่จะมีความเชื่อมโยงกันมากขึ้น โดยคำนวณดังนี้:

${\displaystyle CN(A,B)={|A\cap B|}}$

ข้อเสียของวิธีการนี้คือไม่ได้คำนึงถึงจำนวนเพื่อนบ้านร่วมกันโดยเปรียบเทียบ

การวัดแบบ Jaccardแก้ปัญหาเรื่องเพื่อนบ้านร่วมกันโดยการคำนวณจำนวนเพื่อนบ้านร่วมกันแบบสัมพัทธ์:

${\displaystyle J(A,B)={{|A\cap B|} \over {|A\cup B|}}}$

การวัด Adamic–Adar ^{[ 12 ]}คือผลรวมของลอการิทึมของจุดตัดของเพื่อนบ้านของโหนดสองโหนด ซึ่งจับความคล้ายคลึงแบบสองฮอป ซึ่งอาจให้ผลลัพธ์ที่ดีกว่าวิธีการแบบฮอปเดียวธรรมดา การคำนวณทำได้ดังนี้:

${\displaystyle A(x,y)=\sum _{u\in N(x)\cap N(y)}{\frac {1}{\log |N(u)|}},}$

เซตของโหนดที่อยู่ติดกับคือ. ${\displaystyle N(u)}$${\displaystyle u}$

วิธีการที่ใช้เพื่อนบ้านเป็นฐานอาจมีประสิทธิภาพเมื่อจำนวนเพื่อนบ้านมีมาก แต่ในกราฟแบบเบาบางนั้นไม่ใช่เช่นนั้น ในสถานการณ์เช่นนี้ การใช้วิธีการที่คำนึงถึงการเดินที่ยาวกว่าจึงเหมาะสมกว่าการวัดของ Katz ^{[ 13 ]}เป็นเมตริกหนึ่งที่สามารถจับสิ่งนี้ได้ โดยคำนวณจากการค้นหาเส้นทางที่มีความยาวในกราฟและเพิ่มจำนวนเส้นทางที่มีความยาวแต่ละเส้นโดยถ่วงน้ำหนักด้วยน้ำหนักที่ผู้ใช้กำหนด ${\displaystyle t}$

ให้Aเป็นเมทริกซ์ความประชิดของเครือข่ายที่กำลังพิจารณา องค์ประกอบของAคือตัวแปรที่มีค่าเป็น 1 ถ้าโหนดiเชื่อมต่อกับโหนดjและ 0 ถ้าไม่ใช่ กำลังของAบ่งบอกถึงการมีอยู่ (หรือไม่มีอยู่) ของลิงก์ระหว่างสองโหนดผ่านตัวกลาง ตัวอย่างเช่น ในเมทริกซ์ถ้าองค์ประกอบแสดงว่าโหนด 2 และโหนด 12 เชื่อมต่อกันผ่านทางเดินที่มีความยาว 3 ถ้าแทนค่าความเป็นศูนย์กลางแบบ Katz ของโหนด  iแล้วทางคณิตศาสตร์: ${\displaystyle (a_{ij})}$${\displaystyle A^{3}}$${\displaystyle (a_{2,12})=1}$${\displaystyle C_{\mathrm {Katz} }(i)}$

${\displaystyle C_{\mathrm {Katz} }(i)=\sum _{k=1}^{\infty }\sum _{j=1}^{n}\alpha ^{k}(A^{k})_{ji}}$

โปรดทราบว่าคำจำกัดความข้างต้นใช้ข้อเท็จจริงที่ว่าองค์ประกอบ ณ ตำแหน่งนั้นสะท้อน ถึงจำนวนการเชื่อมต่อระดับดีกรีทั้งหมดระหว่างโหนดและ${\displaystyle (i,j)}$${\displaystyle A^{k}}$${\displaystyle k}$${\displaystyle i}$${\displaystyle j}$

วิธี การหาความคล้ายคลึงของโหนดจะทำนายการมีอยู่ของลิงก์โดยพิจารณาจากความคล้ายคลึงกันของคุณลักษณะของโหนด

ค่าของคุณลักษณะจะถูกแสดงในรูปของเวกเตอร์ที่ปรับให้เป็นมาตรฐาน และใช้ระยะห่างระหว่างเวกเตอร์เหล่านั้นในการวัดความคล้ายคลึงกัน ระยะห่างที่น้อยแสดงถึงความคล้ายคลึงกันที่สูงกว่า

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

วิธีการวิจัยแบบผสมผสานเป็นการผสานรวมวิธีการที่อิงตามคุณลักษณะและเชิงโครงสร้างเข้าด้วยกัน

การฝังกราฟยังเสนอวิธีที่สะดวกในการทำนายลิงก์อีกด้วย^{[ 8 ]}อัลกอริทึมการฝังกราฟ เช่นNode2vecเรียนรู้พื้นที่การฝังซึ่งโหนดข้างเคียงจะถูกแทนด้วยเวกเตอร์ เพื่อให้การวัดความคล้ายคลึงของเวกเตอร์ เช่น ความคล้ายคลึง ของผลคูณจุดหรือระยะทางแบบยุคลิด ใช้ได้ในพื้นที่การฝัง ความคล้ายคลึงเหล่านี้เป็นฟังก์ชันของทั้งคุณลักษณะทางโทโพโลยีและความคล้ายคลึงตามคุณลักษณะ จากนั้นเราสามารถใช้เทคนิคการเรียนรู้ของเครื่องอื่นๆ เพื่อทำนายขอบบนพื้นฐานของความคล้ายคลึงของเวกเตอร์

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

ตรรกะอ่อนเชิงความน่าจะเป็น (PSL) เป็นแบบจำลองกราฟิกเชิงความน่าจะเป็นบนฟิลด์สุ่มมาร์คอฟแบบสูญเสียบานพับ (HL-MRF) HL-MRF ถูกสร้างขึ้นโดยชุดของกฎคล้ายตรรกะลำดับแรกตามแม่แบบ จากนั้นจึงกำหนดพื้นฐานบนข้อมูล PSL สามารถรวมข้อมูลคุณลักษณะหรือข้อมูลท้องถิ่นเข้ากับข้อมูลเชิงโทโพโลยีหรือข้อมูลเชิงสัมพันธ์ ในขณะที่ PSL สามารถรวมตัวทำนายท้องถิ่น เช่นความคล้ายคลึงโคไซน์ ได้ แต่ก็ยังรองรับกฎเชิงสัมพันธ์ เช่น การเติมเต็มสามเหลี่ยมในเครือข่าย^{[ 14 ]}

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

R-Models (RMLs) เป็นแบบจำลองเครือข่ายประสาทที่สร้างขึ้นเพื่อให้วิธีการเรียนรู้เชิงลึกสำหรับปัญหาการทำนายน้ำหนักลิงก์ แบบจำลองนี้ใช้เทคนิคการฝังโหนดที่ดึงการฝังโหนด (ความรู้เกี่ยวกับโหนด) จากน้ำหนักลิงก์ที่ทราบ (ความสัมพันธ์ระหว่างโหนด) และใช้ความรู้นี้เพื่อทำนายน้ำหนักลิงก์ที่ไม่ทราบ^{[ 16 ]}

Link prediction has found varied uses, but any domain in which entities interact in a structures way can benefit from link prediction.^[17] A common applications of link prediction is improving similarity measures for collaborative filtering approaches to recommendation. Link prediction is also frequently used in social networks to suggest friends to users. It has also been used to predict criminal associations.

In biology, link prediction has been used to predict interactions between proteins in protein-protein interaction networks.^[18] Link prediction has also been used to infer interactions between drugs and targets using link prediction ^[19] Another application is found in collaboration prediction in scientific co-authorship networks.

Entity resolution, also known as deduplication, commonly uses link prediction to predict whether two entities in a network are references to the same physical entity. Some authors have used context information in network structured domains to improve entity resolution.^[20]