تشيرانك

الموسوعة الحرة
العقد ذات الروابط في مستوى PageRank و CheiRank

CheiRank هو متجه ذاتي ذو قيمة ذاتية حقيقية قصوى لمصفوفة جوجلجي*{\displaystyle G^{*}}تم تصميم هذا المقياس لشبكة موجهة ذات اتجاهات روابط معكوسة. وهو مكمل لمتجه PageRank الذي يرتب العقد بناءً على عدد الروابط الواردة إليها. وبسبب انعكاس اتجاهات الروابط، يقيس CheiRank اتصال العقدة الصادر. ويؤدي دمج كلا المتجهين إلى ترتيب ثنائي الأبعاد لتدفق المعلومات عبر الشبكة الموجهة.

تعريف

الشكل 1. توزيع استدعاءات الإجراءات لشبكة نواة لينكس في مستوى احتمالية PageRankx=سجل10⁡Pأنا{\displaystyle x=\log _{10}P_{i}}واحتمالية CheiRanky=سجل10⁡Pأنا*{\displaystyle y=\log _{10}{P}_{i}^{*}}لنظام لينكس الإصدار 2.6.32 بحجم المصفوفةشمال=285509{\displaystyle N=285509}فيα=0.85{\displaystyle \alpha =0.85}يوضح اللون كثافة العقد، حيث يمثل اللون الأبيض الحد الأقصى والأزرق الحد الأدنى، أما المساحة السوداء فلا تحتوي على عقد (من تشيبيليانسكي).

بالنسبة لشبكة موجهة معينة، يتم إنشاء مصفوفة جوجل بالطريقة الموضحة في مقالة " مصفوفة جوجل" . متجه PageRank هو المتجه الذاتي ذو القيمة الذاتية الحقيقية القصوى.λ=1{\displaystyle \lambda =1}تم تقديمه في [ 1 ] ونوقش في مقال PageRank . وبالمثل، فإن CheiRank هو المتجه الذاتي ذو القيمة الذاتية الحقيقية القصوى للمصفوفةجي*{\displaystyle G^{*}}تم بناؤها بنفس طريقةجي{\displaystyle G}ولكن باستخدام الاتجاه المعكوس للروابط في مصفوفة التجاور المعطاة مبدئيًا . كلا المصفوفتينجي{\displaystyle G}وجي*{\displaystyle G^{*}}تنتمي إلى فئة مؤثرات بيرون-فروبينيوس، ووفقًا لنظرية بيرون-فروبينيوس، فإن رتبة تشيPأنا*{\displaystyle P_{i}^{*}}و PageRankPأنا{\displaystyle P_{i}}للمتجهات الذاتية مكونات غير سالبة يمكن تفسيرها على أنها احتمالات. [ 2 ] [ 3 ] وبالتالي، فإن جميعشمال{\displaystyle N}العقدأنا{\displaystyle i}يمكن ترتيب عناصر الشبكة بترتيب احتمالي تنازلي باستخدام الرتبكأنا*،كأنا{\displaystyle K_{i}^{*},K_{i}}بالنسبة لـ CheiRank و PageRankPأنا*،Pأنا{\displaystyle P_{i}^{*},P_{i}}على التوالي. في المتوسط، احتمال PageRankPأنا{\displaystyle P_{i}}يتناسب مع عدد الروابط الواردة معPأنا∝1/كأناβ{\displaystyle P_{i}\propto 1/{K_{i}}^{\beta }}[ 4 ] [ 5 ] [ 6 ] بالنسبة لشبكة الويب العالمية (WWW) ، فإن الأسβ=1/(ν-1)≈0.9{\displaystyle \beta =1/(\nu -1)\approx 0.9}أينν≈2.1{\displaystyle \nu \approx 2.1}يمثل الأسّ توزيع الروابط الواردة. [ 4 ] [ 5 ] وبالمثل، فإن احتمال CheiRank يتناسب في المتوسط ​​مع عدد الروابط الصادرة. Pأنا*∝1/كأنا*β*{\displaystyle P_{i}^{*}\propto 1/{K_{i}^{*}}^{\beta ^{*}}}مع β*=1/(ν*-1)≈0.6{\displaystyle \beta ^{*}=1/(\nu ^{*}-1)\approx 0.6}أينν*≈2.7{\displaystyle \nu ^{*}\approx 2.7}يمثل الأسّ توزيع الروابط الصادرة في شبكة الويب العالمية. [ 4 ] [ 5 ] تم تقديم CheiRank لشبكة استدعاء الإجراءات في برمجيات نواة لينكس ، [ 7 ] وقد استُخدم المصطلح نفسه في Zhirov. [ 8 ] بينما يُبرز PageRank العُقد المعروفة والشائعة جدًا، يُبرز CheiRank العُقد شديدة التواصل. تتشابه عُقد PageRank وCheiRank العليا إلى حدٍ ما مع السلطات والمراكز التي تظهر في خوارزمية HITS [ 9 ] ، لكن HITS يعتمد على الاستعلام بينما احتمالات الترتيبPأنا{\displaystyle P_{i}}وPأنا*{\displaystyle P_{i}^{*}}تصنيف جميع عُقد الشبكة. بما أن كل عقدة تنتمي إلى كلٍ من CheiRank و PageRank، نحصل على تصنيف ثنائي الأبعاد لعُقد الشبكة. وقد أُجريت دراسات سابقة حول PageRank في الشبكات ذات الروابط المعكوسة الاتجاه [ 10 ] [ 11 ] ، ولكن لم تُحلل خصائص التصنيف ثنائي الأبعاد بالتفصيل.

الشكل 2. اعتماد احتمال PageRankP{\displaystyle P}(المنحنى الأحمر) و CheiRankP*{\displaystyle P^{*}}(المنحنى الأزرق) على مؤشرات الترتيب المقابلةك{\displaystyle K}وك*{\displaystyle K^{*}}تُظهر الخطوط المستقيمة المتقطعة اعتماد قانون القوة مع الميلβ=0.92؛0.57{\displaystyle \beta =0.92;0.57}على التوالي، بما يتوافق معβ=1/(ν-1){\displaystyle \beta =1/(\nu -1)}(من زيروف)

أمثلة

يوضح الشكل 1 مثالاً على توزيع العقد في مستوى PageRank و CheiRank لشبكة استدعاء الإجراءات في برنامج نواة لينكس. [ 7 ]

الشكل 3. توزيع كثافة مقالات ويكيبيديا الإنجليزية (2009) في مستوى مؤشري PageRank و CheiRank0<ln⁡ك،ln⁡ك*<ln⁡شمال{\displaystyle 0<\ln K,\ln K^{*}<\ln N}يُشار إليها بالألوان، حيث يُمثل الأزرق الحد الأدنى والأبيض الحد الأقصى (والأسود الصفر)؛ تُظهر النقاط الخضراء/الحمراء أفضل 100 شخصية من PageRank/CheiRank، وتُظهر علامات الجمع الصفراء أفضل 100 شخصية من كتاب هارت، وعدد المقالاتشمال=3282257{\displaystyle N=3282257}(من زيروف)

اعتمادP،P*{\displaystyle P,P^{*}}علىك،ك*{\displaystyle K,K^{*}}يوضح الشكل 2 (من زيروف) شبكة الروابط التشعبية لمقالات ويكيبيديا الإنجليزية. أما الشكل 3 (من زيروف أيضًا) فيوضح توزيع هذه المقالات في مستوى PageRank وCheiRank. ويتضح الفرق بين PageRank وCheiRank من خلال أسماء مقالات ويكيبيديا (2009) ذات أعلى تصنيف. ففي أعلى PageRank نجد: 1. الولايات المتحدة، 2. المملكة المتحدة، 3. فرنسا، بينما في CheiRank نجد: 1. Portal:Contents/Outline of knowledge/Geography and places، 2. List of state leaders by year، 3. Portal:Contents/Index/Geography and places. من الواضح أن PageRank يختار المقالات الأولى التي تتناول موضوعًا واسع الانتشار مع عدد كبير من الروابط الواردة، بينما يختار CheiRank المقالات الأولى ذات المحتوى التواصلي العالي مع العديد من الروابط الصادرة. وبما أن المقالات موزعة في بُعدين، فيمكن ترتيبها بطرق مختلفة تتوافق مع إسقاط مجموعة ثنائية الأبعاد على خط. يمثل الخطان الأفقي والرأسي ترتيب الصفحات (PageRank) وترتيب تشي (CheiRank)، بينما يجمع ترتيب الصفحات الثنائي (2DRank) خصائص ترتيب الصفحات وترتيب تشي كما هو موضح في مرجع زيروف [ 8 ] . ويُظهر هذا الترتيب أفضل مقالات ويكيبيديا: 1. الهند، 2. سنغافورة، 3. باكستان.

يُبرز تصنيف ثنائي الأبعاد خصائص مقالات ويكيبيديا بطريقة جديدة ثرية ومثمرة. وفقًا لتصنيف PageRank، فإنّ أفضل 100 شخصية موصوفة في مقالات ويكيبيديا تندرج ضمن 5 فئات رئيسية من الأنشطة: 58 (سياسة)، 10 (دين)، 17 (فنون)، 15 (علوم)، 0 (رياضة)، مما يُشير إلى مبالغة كبيرة في تقدير أهمية السياسيين. يُعطي تصنيف CheiRank الترتيب 15، 1، 52، 16، 16 على التوالي، بينما يُعطي تصنيف 2DRank الترتيب 24، 5، 62، 7، 2. يُمكن لهذا النوع من التصنيف ثنائي الأبعاد أن يجد تطبيقات مفيدة في مختلف الشبكات الموجهة المعقدة، بما في ذلك شبكة الويب العالمية (WWW).

يظهر كل من CheiRank و PageRank بشكل طبيعي في سياق شبكة التجارة العالمية، أو التجارة الدولية ، حيث يرتبطان بتدفقات الصادرات والواردات لبلد معين على التوالي. [ 12 ]

تُناقش إمكانيات تطوير محركات بحث ثنائية الأبعاد تعتمد على خوارزميتي PageRank وCheiRank. [ 13 ] يمكن وصف الشبكات الموجهة بمعامل الارتباط بين متجهي PageRank وCheiRank: في بعض الشبكات يكون هذا المعامل قريبًا من الصفر (مثل شبكة نواة لينكس)، بينما في شبكات أخرى تكون قيم معامل الارتباط عالية (مثل ويكيبيديا أو شبكات الجامعات). [ 7 ] [ 13 ]

مثال بسيط للشبكة

الشكل 4. مثال على الشبكة الموجهة
الشكل 5. المصفوفة ذات الصلةS{\displaystyle S}
الشكل 6. المصفوفة ذات الصلةS*{\displaystyle S^{*}}

مثال بسيط على كيفية إنشاء مصفوفات جوجلجي{\displaystyle G}وجي*{\displaystyle G^{*}}تُستخدم هذه الطريقة لتحديد متجهات PageRank وCheiRank ذات الصلة، وهي موضحة أدناه. يُبين الشكل 4 مثالًا لشبكة موجهة مكونة من 7 عقد. المصفوفةS{\displaystyle S}تم إنشاء مصفوفة جوجل وفقًا للقواعد الموضحة في مقالة "مصفوفة جوجل" ، كما هو موضح في الشكل 5؛ ومصفوفة جوجل ذات الصلة هيجي=αS+(1-α)هـهـتي/شمال{\displaystyle G=\alpha S+(1-\alpha )ee^{T}/N} ومتجه PageRank هو المتجه الذاتي الأيمن لـجي{\displaystyle G} مع القيمة الذاتية للوحدة (جيP=P{\displaystyle GP=P}وبالمثل، لتحديد متجه تشي رانك الذاتي، يتم عكس جميع اتجاهات الروابط في الشكل 4، ثم المصفوفةS*{\displaystyle S^{*}}يتم بناء الشبكة وفقًا للقواعد نفسها المطبقة على الشبكة ذات اتجاهات الروابط المعكوسة، كما هو موضح في الشكل 6. مصفوفة جوجل ذات الصلة هي جي*=αS*+(1-α)هـهـتي/شمال{\displaystyle G^{*}=\alpha S^{*}+(1-\alpha )ee^{T}/N}ومتجه CheiRank هو المتجه الذاتي الأيمن لـجي*{\displaystyle G^{*}} مع القيمة الذاتية للوحدة (جي*P*=P*{\displaystyle G^{*}P^{*}=P^{*}}). هناα≈0.85{\displaystyle \alpha \approx 0.85}يتم أخذ عامل التخميد بقيمته المعتادة.

انظر أيضاً

مراجع

  1. ↑ برين إس.؛ بيج إل. (1998)، "تشريح محرك بحث ويب نصي فائق واسع النطاق"، شبكات الحاسوب وأنظمة ISDN ، 30 ( 1-7 ): 107، doi : 10.1016/S0169-7552(98)00110-X ، S2CID 7587743 
  2. ↑ لانغفيل، آمي ن .؛ كارل ماير (2006). ترتيب صفحات جوجل وما بعده . مطبعة جامعة برينستون . ISBN 0-691-12202-4.
  3. ↑ أوستن، ديفيد (2008). "كيف تجد جوجل إبرتك في كومة قش الويب" . مقالات مميزة من جمعية التسويق الأمريكية.
  4. 1 2 3 دوناتو د.؛ لورا ل.؛ ليوناردي س.؛ ميلوزي س. (2004)، "خصائص واسعة النطاق للرسم البياني الشبكي"، المجلة الأوروبية للفيزياء ب ، 38 (2): 239، رمز Bibcode : 2004EPJB...38..239D ، doi : 10.1140/epjb/e2004-00056-6 ، S2CID 10640375 
  5. 1 2 3 باندورانجان ج.؛ رانغافان ب.؛ أوبفال إ. (2005)، "استخدام بيج رانك لتوصيف بنية الويب"، رياضيات الإنترنت ، 3 : 1، doi : 10.1080/15427951.2006.10129114
  6. ↑ ليتفاك، ن .؛ شاينهارت، و.ر.و.؛ فولكوفيتش، ي. (2008)، العلاقة الاحتمالية بين درجة الدخول و PageRank ، سلسلة محاضرات في علوم الحاسوب، المجلد 4936، ص 72  
  7. 1 2 3 تشيبيليانسكي، أليكسي د. (2010). "نحو قوانين فيزيائية لهندسة البرمجيات". arXiv : 1003.5455 [ cs.SE ].
  8. 1 2 زيروف آو؛ زيروف أو.في. Shepelyansky DL (2010)، “تصنيف ثنائي الأبعاد لمقالات ويكيبيديا”، المجلة الفيزيائية الأوروبية ب ، 77 (4): 523، أرخايف : 1006.4270 ، بيب كود : 2010EPJB...77..523Z ، دوى : 10.1140/epjb/e2010-10500-7 ، S2CID 18014470 
  9. ↑ كلاينبرغ، جون (1999). "المصادر الموثوقة في بيئة ذات روابط تشعبية" . مجلة ACM . 46 (5): 604-632 . doi : 10.1145/324133.324140 . S2CID 221584113 . 
  10. ↑ فوغاراس، د. (2003)، من أين نبدأ تصفح الويب؟، سلسلة محاضرات في علوم الحاسوب، المجلد 2877، ص 65  
  11. ↑ هريسيتيديس ف.؛ هوانغ هـ.؛ باباكونستانتينو ي. (2008)، "البحث عن الكلمات المفتاحية في قواعد البيانات بناءً على المرجعية"، مجلة ACM لأنظمة قواعد البيانات ، 33 : 1، doi : 10.1145/1331904.1331905 ، S2CID 11978441 
  12. ↑ إرمان، ل.؛ شيبليانسكي، د. ل. (2011). "مصفوفة جوجل لشبكة التجارة العالمية". مجلة الفيزياء البولندية، الجزء أ . 120 (6أ): أ. arXiv : 1103.5027 . Bibcode : 2011AcPPA.120..158E . doi : 10.12693/APhysPolA.120.A-158 . S2CID 18315654 . 
  13. 1 2 إرمان، ل.؛ تشيبيليانسكي، أ.د.؛ شيبيليانسكي، د.ل. (2011). "نحو محركات بحث ثنائية الأبعاد". مجلة الفيزياء أ: الرياضية والنظرية . 45 (27) 275101. arXiv : 1106.6215 . Bibcode : 2012JPhA...45A5101E . doi : 10.1088/1751-8113/45/27/275101 . S2CID 14827486 .