Google Matrix For PageRanking

Google Matrix არის სტოქასტური მატრიცის კერძო შემთხვევა, რომელსაც გუგლი იყენებს PageRank-ის ალგორითმში. მატრიცა წარმოადგენს გრაფს, რომლის წიბოებიც წარმოადგენენ კავშირებს წიბოებს შორის. თითოეული გვერდის რანკი/რეიტინგი შეიძლება დაგენერირდეს იტერაციულად Google Matrix-დან ახარისხების მეთოდით.

 

რომ დავაგენერიროთ Google Matrix G, პირველ რიგში უნდ ადავაგენერიროთ მოსაზღვრეობის მატრიცა A, რომელიც წარმოადგენს კავშირებს გვერდებს ან წვეროებს (nodes) შორის. ჩავთვალოთ, რომ გვაქვს N ცალი გვერდი, ჩვენ შეგვიძლია შევავსოთ A შემდეგი წესის მიხედვით:

  • A მატრიცის ელემენტი A[i][j] იქნება 1-ის ტოლი თუ კვანძ j-ს აქვს კავშირი/ლინკი კვანძ i-თან, წინააღმდეგ შემთხვევაში იქნება 0-ის ტოლი. ეს არის კავშირების მსოაზღვრეობის მატრიცა.
  • დაკავშირებული მატრიცა S წარმოადგენს გადასვლებს მოცემული ქსელის მარკოვის ჯაჭვში. S იგება A-გან , j სვეტის ელემენტების გაყოფით k[j]-ზე, სადაც k[j] არის j წვეროდან გამავალი კავშრების/ლინკების ჯამური რაოდენობა. სვეტები, რომლებსაც აქვს 0-ები, ანუ არ აქვს გამავალი კავშირები, იცვლება მუდმივი მნიშვნელობით 1/N

as

საბოლოოდ Google Matrix G შეიძლება გამოვსახოთ S-ის გამოყენებით

a

სადაც b არის ჩახშობის კოეფიციენტი. როგორც წესი S არის მეჩხერი მატრიცა და თანამედროვე მიმართული ქსელისთვის მას აქვს დაახლოებით 10 არანულოვანი ელემენტი თითოეულ სვეტში ან სტრიქონში, აქედან გამომდინარე დაახლოებით 10N გადამრავლების ოპერაციაა საჭირო G მატრიცის ვექტორზე გადამრავლებისას.

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s