مصفوفة جوجل

مصفوفة جوجل هي مصفوفة عشوائية خاصة يستخدمها خوارزمية PageRank من جوجل . تمثل هذه المصفوفة رسمًا بيانيًا، حيث تمثل الحواف الروابط بين الصفحات. ويمكن بعد ذلك حساب قيمة PageRank لكل صفحة بشكل تكراري من مصفوفة جوجل باستخدام طريقة القوة . ولكن لكي تتقارب طريقة القوة، يجب أن تكون المصفوفة عشوائية وغير قابلة للاختزال وغير دورية .

من أجل إنشاء مصفوفة جوجل G ، يجب علينا أولاً إنشاء مصفوفة تجاور A التي تمثل العلاقات بين الصفحات أو العقد.

بافتراض وجود N صفحة، يمكننا ملء A عن طريق القيام بما يلي:

1. عنصر مصفوفة${\displaystyle A_{i,j}}$يتم ملؤها بـ 1 إذا كانت العقدة${\displaystyle j}$يحتوي على رابط إلى العقدة${\displaystyle i}$، و 0 فيما عدا ذلك؛ هذه هي مصفوفة تجاور الروابط.
2. يتم إنشاء مصفوفة S ذات صلة ، تتوافق مع الانتقالات في سلسلة ماركوف لشبكة معينة، من المصفوفة A عن طريق قسمة عناصر العمود "j" على عدد من${\displaystyle k_{j}=\Sigma _{i=1}^{N}A_{i,j}}$أين${\displaystyle k_{j}}$يمثل N العدد الإجمالي للروابط الصادرة من العقدة j إلى جميع العقد الأخرى. تُستبدل الأعمدة التي تحتوي على عناصر مصفوفة صفرية ، والتي تُمثل العقد المعلقة، بقيمة ثابتة 1/N . تُضيف هذه العملية رابطًا من كل عقدة وجهة، وهي حالة معلقة. ${\displaystyle a}$إلى كل عقدة أخرى.
3. بحسب هذا البناء، فإن مجموع جميع عناصر أي عمود في المصفوفة S يساوي واحدًا. وبهذا، تُعرَّف المصفوفة S رياضيًا تعريفًا دقيقًا، وتنتمي إلى فئة سلاسل ماركوف وفئة مؤثرات بيرون-فروبينيوس. وهذا ما يجعل S مناسبة لخوارزمية بيج رانك .

ويمكن التعبير عن مصفوفة جوجل النهائية G عبر S على النحو التالي:

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

بحسب هذا البناء، فإن مجموع جميع العناصر غير السالبة داخل كل عمود من أعمدة المصفوفة يساوي واحدًا. المعامل العددي${\displaystyle \alpha }$يُعرف باسم عامل التخميد.

عادةً ما تكون S مصفوفة متفرقة، وبالنسبة للشبكات الموجهة الحديثة ، فإنها تحتوي على حوالي عشرة عناصر غير صفرية فقط في صف أو عمود، وبالتالي يلزم حوالي 10 N عملية ضرب لضرب متجه في المصفوفة G. ^{[ 2 ] [ 3 ]} 

مثال على المصفوفة${\displaystyle S}$تم تقديم عملية البناء عبر المعادلة (1) ضمن شبكة بسيطة في مقالة CheiRank .

تستخدم جوجل عامل تخميد للمصفوفة الفعلية${\displaystyle \alpha }$حوالي 0.85. ^{[ 2 ] [ 3 ] [ 4 ]} المصطلح${\displaystyle (1-\alpha )}$تُعطي هذه المصفوفة احتمالية انتقال المتصفح عشوائياً إلى أي صفحة.${\displaystyle G}$ينتمي إلى فئة عوامل بيرون-فروبينيوس لسلاسل ماركوف . ^{[ 2 ]} تظهر أمثلة على بنية مصفوفة جوجل في الشكل 1 لشبكة روابط مقالات ويكيبيديا في عام 2009 على نطاق صغير وفي الشكل 2 لشبكة جامعة كامبريدج في عام 2006 على نطاق واسع.

ل${\displaystyle 0<\alpha <1}$لا توجد سوى قيمة ذاتية قصوى واحدة${\displaystyle \lambda =1}$مع المتجه الذاتي الأيمن المقابل الذي يحتوي على عناصر غير سالبة${\displaystyle P_{i}}$والتي يمكن اعتبارها توزيعًا احتماليًا ثابتًا. ^{[ 2 ]} هذه الاحتمالات مرتبة تنازليًا حسب قيمها، مما يُعطي متجه PageRank${\displaystyle P_{i}}$مع ترتيب الصفحات${\displaystyle K_{i}}$يستخدم محرك بحث جوجل هذا لترتيب صفحات الويب. عادةً ما يكون لدى المرء هذا الأمر بالنسبة للشبكة العنكبوتية العالمية.${\displaystyle P\propto 1/K^{\beta }}$مع${\displaystyle \beta \approx 0.9}$يتناسب عدد العقد التي لها قيمة PageRank معينة تناسبًا طرديًا مع${\displaystyle N_{P}\propto 1/P^{\nu }}$مع الأس${\displaystyle \nu =1+1/\beta \approx 2.1}$[ ^{6 ] [ 7 ]} المتجه الذاتي الأيسر ^عند${\displaystyle \lambda =1}$تحتوي على عناصر مصفوفة ثابتة. مع${\displaystyle 0<\alpha }$تتحرك جميع القيم الذاتية مع${\displaystyle \lambda _{i}\rightarrow \alpha \lambda _{i}}$باستثناء القيمة الذاتية القصوى${\displaystyle \lambda =1}$^{[ 2 ]} يتغير متجه PageRank مع${\displaystyle \alpha }$لكن المتجهات الذاتية الأخرى مع${\displaystyle \lambda _{i}<1}$تبقى دون تغيير بسبب تعامدها مع المتجه الأيسر الثابت عند${\displaystyle \lambda =1}$الفجوة بين${\displaystyle \lambda =1}$وقيم ذاتية أخرى هي${\displaystyle 1-\alpha \approx 0.15}$يُعطي تقاربًا سريعًا لمتجه أولي عشوائي إلى PageRank بعد حوالي 50 عملية ضرب${\displaystyle G}$مصفوفة.

في${\displaystyle \alpha =1}$المصفوفة${\displaystyle G}$ يحتوي عمومًا على العديد من القيم الذاتية المنحلة${\displaystyle \lambda =1}$ (انظر على سبيل المثال [6] ^{[ 8 ] ). يوضح الشكل 3 من [ 5 ]} والشكل 4 من ^{[ 8 ]} أمثلة على طيف القيم الذاتية لمصفوفة جوجل لشبكات موجهة مختلفة.

يمكن أيضًا إنشاء مصفوفة جوجل لشبكات أولام المُولَّدة بواسطة طريقة أولام [8] للخرائط الديناميكية. نُوقشت الخصائص الطيفية لهذه المصفوفات في المراجع [9، 10، 11، 12، 13، 15]. ^{[ 5 ] [ 9 ]} في عدد من الحالات، يُوصف الطيف بقانون ويل الفركتلي [10، 12].

يمكن أيضًا إنشاء مصفوفة جوجل لشبكات موجهة أخرى، مثل شبكة استدعاء الإجراءات لبرنامج نواة لينكس المذكور في [15]. في هذه الحالة، يكون طيف${\displaystyle \lambda }$يتم وصفها بقانون ويل الكسري ذي البعد الكسري${\displaystyle d\approx 1.3}$(انظر الشكل 5 من ^{[ 9 ]} ). يُظهر التحليل العددي أن الحالات الذاتية للمصفوفة${\displaystyle G}$تكون موضعية (انظر الشكل 6 من ^{[ 9 ]} ). تسمح طريقة أرنولدي التكرارية بحساب العديد من القيم الذاتية والمتجهات الذاتية للمصفوفات ذات الحجم الكبير نسبيًا [13]. ^{[ 5 ] [ 9 ]}

أمثلة أخرى على${\displaystyle G}$تشمل المصفوفات مصفوفة جوجل للدماغ [17] وإدارة عمليات الأعمال [18]، انظر أيضًا. ^{[ 1 ]} تم وصف تطبيقات تحليل مصفوفة جوجل على تسلسلات الحمض النووي في [20]. يسمح نهج مصفوفة جوجل هذا أيضًا بتحليل تشابك الثقافات من خلال تصنيف مقالات ويكيبيديا متعددة اللغات حول الأشخاص [21].

تم وصف مصفوفة جوجل مع عامل التخميد بواسطة سيرجي برين ولاري بيج في عام 1998 [22]، انظر أيضًا المقالات حول تاريخ PageRank [23]، [24].

• تشيرانك
• تكرار أرنولدي
• سلسلة ماركوف
• موظف التحويل
• نظرية بيرون-فروبينيوس
• محركات البحث على الإنترنت

• مصفوفة جوجل في سكولاربيديا
• إغلاق العلاقات العامة لشركة جوجل
• محاضرات فيديو في ورشة عمل IHES بعنوان "مصفوفة جوجل: الأساسيات والتطبيقات وما بعدها"، أكتوبر 2018