เมทริกซ์ของกูเกิล

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

ในการสร้างเมทริกซ์G ของ Google เราต้องสร้างเมทริกซ์ความสัมพันธ์A ก่อน ซึ่งเป็นเมทริกซ์ที่แสดงถึงความสัมพันธ์ระหว่างหน้าเว็บหรือโหนดต่างๆ

สมมติว่ามีNหน้า เราสามารถกรอกข้อมูลในตารางA ได้ โดยทำดังนี้:

1. ค่าในเมทริกซ์จะเป็น 1 ถ้าโหนดหนึ่งเชื่อมโยงกับอีกโหนดหนึ่งและจะเป็น 0 ถ้าไม่ใช่ นี่คือเมทริกซ์ความสัมพันธ์ของลิงก์${\displaystyle A_{i,j}}$${\displaystyle j}$${\displaystyle i}$
2. เมทริกซ์S ที่เกี่ยวข้อง กับการเปลี่ยนสถานะในห่วงโซ่มาร์คอฟของเครือข่ายที่กำหนด จะถูกสร้างขึ้นจาก เมทริก ซ์ Aโดยการหารองค์ประกอบของคอลัมน์ "j" ด้วยจำนวน โดยที่คือจำนวนรวมของลิงก์ขาออกจากโหนด  jไปยังโหนดอื่นๆ ทั้งหมด คอลัมน์ที่มี องค์ประกอบ เมทริกซ์เป็นศูนย์ซึ่งสอดคล้องกับโหนดที่ไม่มีลิงก์ จะถูกแทนที่ด้วยค่าคงที่1/Nกระบวนการนี้จะเพิ่มลิงก์จากทุกโหนดปลายทาง (สถานะที่ไม่มีลิงก์) ไปยังทุกโหนดอื่นๆ${\displaystyle k_{j}=\Sigma _{i=1}^{N}A_{i,j}}$${\displaystyle k_{j}}$${\displaystyle a}$
3. จากโครงสร้างของเมทริกซ์ S ผลรวมของทุกองค์ประกอบในคอลัมน์ใดๆ จะเท่ากับหนึ่ง ด้วยวิธีนี้ เมทริกซ์Sจึงมีความนิยามทางคณิตศาสตร์ที่ดี และจัดอยู่ในกลุ่มของลูกโซ่ Markov และกลุ่มของตัวดำเนินการ Perron-Frobenius ซึ่งทำให้SเหมาะสมสำหรับอัลกอริทึมPageRank

จากนั้นเมทริกซ์ Google สุดท้าย G สามารถแสดงได้ผ่านSดังนี้:

${\displaystyle G_{ij}=\alpha S_{ij}+(1-\alpha ){\frac {1}{N}}\;\;\;\;\;\;\;\;\;\;\;(1)}$

ตามโครงสร้างแล้ว ผลรวมขององค์ประกอบที่ไม่เป็นลบทั้งหมดภายในแต่ละคอลัมน์ของเมทริกซ์จะมีค่าเท่ากับหนึ่ง ค่าสัมประสิทธิ์เชิงตัวเลขนี้เรียกว่า ตัวประกอบลดทอน (damping factor) ${\displaystyle \alpha }$

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

ตัวอย่างของการสร้างเมทริกซ์โดยใช้สมการ (1) ภายในเครือข่ายแบบง่ายมีอยู่ในบทความ CheiRank${\displaystyle S}$

สำหรับเมทริกซ์จริง Google ใช้ปัจจัยการลดทอนประมาณ 0.85 ^{[ 2 ] [ 3 ] [ 4 ]}เงื่อนไขนี้ให้ความน่าจะเป็นที่ผู้ใช้จะกระโดดไปยังหน้าใดก็ได้แบบสุ่ม เมทริกซ์นี้จัดอยู่ในกลุ่มตัวดำเนินการ Perron-Frobeniusของ ห่วง โซ่ Markov [ ^{2 ] ตัวอย่าง}โครงสร้างเมทริกซ์ของ Google แสดงในรูปที่ 1 สำหรับเครือข่ายไฮเปอร์ลิงก์บทความ Wikipedia ในปี 2009 ในขนาดเล็ก และในรูปที่ 2 สำหรับเครือข่ายมหาวิทยาลัยเคมบริดจ์ในปี 2006 ในขนาดใหญ่ ${\displaystyle \alpha }$${\displaystyle (1-\alpha )}$${\displaystyle G}$

เนื่องจากมีค่าไอเกนสูงสุดเพียงค่าเดียวที่มีเวกเตอร์ไอเกนขวาที่สอดคล้องกันซึ่งมีองค์ประกอบที่ไม่เป็นลบซึ่งสามารถมองได้ว่าเป็นการกระจายความน่าจะเป็นแบบคงที่^{[ 2 ]}ความน่าจะเป็นเหล่านี้เรียงลำดับตามค่าที่ลดลงจะให้เวกเตอร์ PageRank พร้อมกับ PageRank ที่ Google Search ใช้ในการจัดอันดับเว็บเพจ โดยปกติแล้วสำหรับ World Wide Web จะมีค่า โดยที่จำนวนโหนดที่มีค่า PageRank ที่กำหนดจะแปรผันตามโดยมีเลขชี้กำลัง^{[ 6 ] [ 7 ]}เวกเตอร์ไอเกนซ้ายที่มีองค์ประกอบเมทริกซ์คงที่ โดยที่ค่าไอเกนทั้งหมดจะเคลื่อนที่ตาม ยกเว้นค่าไอเก นสูงสุดซึ่งยังคงไม่เปลี่ยนแปลง^{[ 2 ]}เวกเตอร์ PageRank จะแปรผันตามแต่เวกเตอร์ไอเกนอื่นๆ ที่มีค่ายังคงไม่เปลี่ยนแปลงเนื่องจากความเป็นตั้งฉากกับเวกเตอร์ซ้ายคงที่ที่ ช่องว่าง ระหว่างและค่าไอเกนอื่นๆ ทำให้เกิดการลู่เข้าอย่างรวดเร็วของเวกเตอร์เริ่มต้นแบบสุ่มไปยัง PageRank ประมาณหลังจากคูณเมทริกซ์ 50 ครั้ง ${\displaystyle 0<\alpha <1}$${\displaystyle \lambda =1}$${\displaystyle P_{i}}$${\displaystyle P_{i}}$${\displaystyle K_{i}}$${\displaystyle P\propto 1/K^{\beta }}$${\displaystyle \beta \approx 0.9}$${\displaystyle N_{P}\propto 1/P^{\nu }}$${\displaystyle \nu =1+1/\beta \approx 2.1}$${\displaystyle \lambda =1}$${\displaystyle 0<\alpha }$${\displaystyle \lambda _{i}\rightarrow \alpha \lambda _{i}}$${\displaystyle \lambda =1}$${\displaystyle \alpha }$${\displaystyle \lambda _{i}<1}$${\displaystyle \lambda =1}$${\displaystyle \lambda =1}$${\displaystyle 1-\alpha \approx 0.15}$${\displaystyle G}$

โดย ทั่วไปเมทริกซ์ จะมีค่าไอเกนที่เสื่อมสภาพจำนวนมาก (ดูเช่น [6] ^{[ 8 ]} ) ตัวอย่างของสเปกตรัมค่าไอเกนของเมทริกซ์ Google ของเครือข่ายทิศทางต่างๆ แสดงในรูปที่ 3 จาก^{[ 5 ]}และรูปที่ 4 จาก^{[ 8 ]}${\displaystyle \alpha =1}$${\displaystyle G}$${\displaystyle \lambda =1}$

เมทริกซ์ Google ยังสามารถสร้างขึ้นสำหรับเครือข่าย Ulam ที่สร้างขึ้นโดยวิธี Ulam [8] สำหรับแผนที่ไดนามิก คุณสมบัติสเปกตรัมของเมทริกซ์ดังกล่าวมีการกล่าวถึงใน [9,10,11,12,13,15] ^{[ 5 ] [ 9 ]}ในหลายกรณี สเปกตรัมจะถูกอธิบายโดยกฎ Weyl แบบแฟรกทัล [10,12]

เมทริกซ์ Google สามารถสร้างขึ้นสำหรับเครือข่ายทิศทางอื่นๆ ได้เช่นกัน เช่น สำหรับเครือข่ายการเรียกใช้ขั้นตอนของซอฟต์แวร์ Linux Kernel ที่แนะนำใน [15] ในกรณีนี้ สเปกตรัมของจะถูกอธิบายโดยกฎ Weyl แบบแฟรกทัลที่มีมิติแฟรกทัล(ดูรูปที่ 5 จาก^{[ 9 ]} ) การวิเคราะห์เชิงตัวเลขแสดงให้เห็นว่าสถานะไอเกนของเมทริกซ์นั้นอยู่ในบริเวณเฉพาะที่ (ดูรูปที่ 6 จาก^{[ 9 ]} ) วิธี การวนซ้ำของ Arnoldiช่วยให้สามารถคำนวณค่าไอเกนและเวกเตอร์ไอเกนจำนวนมากสำหรับเมทริกซ์ที่มีขนาดค่อนข้างใหญ่ได้ [13] ^{[ 5 ] [ 9 ]}${\displaystyle \lambda }$${\displaystyle d\approx 1.3}$${\displaystyle G}$

ตัวอย่างอื่นๆ ของเมทริกซ์ ได้แก่ เมทริกซ์สมองของ Google [17] และการจัดการกระบวนการทางธุรกิจ [18] ดูเพิ่มเติมที่^{[ 1 ]}การประยุกต์ใช้การวิเคราะห์เมทริกซ์ของ Google กับลำดับ DNA ได้รับการอธิบายไว้ใน [20] แนวทางเมทริกซ์ของ Google ดังกล่าวยังช่วยให้สามารถวิเคราะห์การพันกันของวัฒนธรรมผ่านการจัดอันดับบทความ Wikipedia หลายภาษาเกี่ยวกับบุคคล [21] ${\displaystyle G}$

เมทริกซ์ของ Google ที่มีปัจจัยการลดทอนได้รับการอธิบายโดยSergey BrinและLarry Pageในปี 1998 [22] ดูบทความเกี่ยวกับประวัติ PageRank [23], [24] ด้วย

• เชอิแรงค์
• การวนซ้ำของอาร์โนลดี
• โซ่ Markov
• ผู้ดำเนินการโอนย้าย
• ทฤษฎีบทเพอร์รอน-โฟรเบนิอุส
• เครื่องมือค้นหาบนเว็บ

• ตารางข้อมูลของ Google ที่ Scholarpedia
• ฝ่ายประชาสัมพันธ์ของ Google ปิดตัวลง
• วิดีโอบรรยายในการประชุมเชิงปฏิบัติการ IHES หัวข้อ "เมทริกซ์ของ Google: พื้นฐาน การประยุกต์ใช้ และอื่นๆ" ตุลาคม 2561