Еще по теме:

Алина Крутоголова

Есть вопросы?

Задайте их прямо сейчас, и мы ответим в течение 8 рабочих часов.

Расчет PageRank | Растолкованный PageRank,

Объяснив, что такое вес PageRank, т. е., что вы узнаете, когда получаете информацию о нем, и насколько он важен… в этом разделе я расскажу вам примерно как он вычисляется. Знать это не обязательно, однако, если вы поймете это, вы будете лучше понимать, как следует его применять.

Когда Google был только исследовательским проектом, они [Брин и Пэйдж — прим. А. С.] написали статью, подробно описывающую формулу, которая определяет вес PageRank для страницы. Хотя они, возможно, уже не используют в точности эту формулу, она представляется достаточно корректной для сегодняшних целей. Вот она:

PR(A) = (1-d) + d (PR(T₁)/C(T₁) + … + PR(T_n)/C(T_n)),

где PR(A) — это вес PageRank страницы A (тот вес, который мы хотим вычислить),

D — это коэффициент затухания, который обычно устанавливают равным 0,85,

PR(T₁) — вес PageRank страницы, указывающей на страницу A,

C(T₁) — число ссылок с этой страницы,

PR(T_n)/C(T_n) означает, что мы делаем это для каждой страницы, указывающей на страницу A

Жуть! Для тех из вас, кто не является математиком, здесь есть полная информация по этой формуле — вы не можете просто вычислить вес PageRank за один прием, как показано тут. Чтобы вычислить вес PageRank страницы A вам понадобится знать веса PageRank всех страниц, указывающих на страницу A. Их веса PageRank будут частично зависеть от страницы A, указывающей на них, либо каких-то других страниц, ссылающихся на них. Какая глупая формула. Что она нам говорит, так это одну очень важную вещь о весе PageRank любой страницы.

Вес PageRank, передаваемый на страницу A со страницы B, которая указывает на нее, уменьшается с каждой ссылкой куда-нибудь, которая находится на странице B. Это означает, что вес страницы, по существу, это мера ее голоса; страница может разделить этот голос между одной, двумя или многими ссылками, но общая голосующая сила будет всегда той же самой.

Сейчас забудьте формулу на некоторое время, потому что легче рассмотреть пример реализации, который очень похож на PageRank. Он должен помочь нам лучше понять PageRank. Назовем его MiniRank.

Вначале мы не знаем, какие веса MiniRank у этих страниц, поэтому мы их просто присвоим. Для простоты, мы выберем число один. В результате диаграмма становится…

Все еще легко! Сейчас вспомните правила передачи веса. Вначале мы применяем коэффициент затухания. (Коэффициент затухания, в основном, говорит о том, что страница не может голосовать так, чтобы другая страница была столь же важна, как она сама. Это означает, что страницы, к которым труднее добраться в Web, менее важны.) Затем мы делим сохранившийся вес на число ссылок. Мы подсчитываем итоговый вес, который должен быть добавлен ко всем до единой страницам, перед тем как мы окончательно его прибавим.

Итак, глядя вначале на страницу A, видим, что значение веса MiniRank, доступное для передачи, после затухания равно 1 * 0,85 = 0,85. Со страницы ведут две ссылки, поэтому, по окончании итерации, мы добавим 0,425 к весу MiniRank страницы B и 0,425 к весу MiniRank страницы C. Мы не можем сделать это до тех пор, пока мы не рассчитали все ссылки страницы, потому что это повлияет на результаты.

Перейдем к странице B. Она содержит только одну ссылку. Поэтому, она передаст 1 * 0,85 = 0,85 странице C, когда мы сделаем все вычисления для ссылок.

Страница C также имеет одну ссылку. Поэтому она передаст вес 1 * 0,85 = 0,85 странице A.

Страница D имеет одну ссылку, поэтому она передает 0,85 странице C.

Сейчас мы можем добавить все суммы ко всем весам страниц.

Новые значения весов MiniRank показывают, сколь важна страница C. Но мы еще не завершили. Поскольку все страницы начали с одного значения, по правде говоря, мы вычислили только популярность в ссылках (link popularity). Суть PageRank и MiniRank такова, что страницам, на которые чаще ссылаются, следует получить больше голосов; поэтому мы должны проделать то же самое еще раз! На этот раз страница C имеет большее влияние, потому что ее текущий вес MiniRank выше.

Так, посмотрим на страницу A вначале. Ее текущий вес MiniRank равен 1,85. Величина MiniRank, доступная для передачи, после применения затухания составляет 1,85 * 0,85 = 1,5725. Есть две ссылки со страницы, поэтому по завершению итерации мы добавим 0,78625 к весу MiniRank страницы B и весу MiniRank страницы C.

Перейдем к странице B. У нее есть только одна ссылка. Следовательно, она передаст 1,425 * 0,85 = 1,21125 странице C, когда мы завершим все вычисления со ссылками.

Страница C также имеет одну ссылку, но при этом обладает огромным весом 3,125 MiniRank. Поэтому она передаст 3,125 * 0,85 = 2,65625 странице A.

Страница D имеет одну ссылку, поэтому она передает 0,85 странице C.

Мы получаем….

Мы уже можем видеть то, что следовало ожидать: страница C имеет наибольший вес MiniRank, страница A — следующий по величине. На практике нам нужно было бы повторить эти действия от 50 до 100 раз, чтобы гарантировать, что низкая точность предыдущих итераций сведена на нет. Просто!

Понравилось это:

Нравится Загрузка…

Растолкованный PageRank. Как рассчитывается Pagerank Расчет pagerank

Все его используют, но мало кто знает, как он работает. Google PageRank, это один из важнейших для веб-разработчиков параметров.

Поиск среди миллиардов существующих и миллионов создаваемых каждый день страниц, задача более сложная, чем вы можете сразу представить. PageRank, только один из сотен факторов, используемых Google для улучшения качества поиска. Но как он работает, и какие факторы на него влияют, а какие нет, и, что мы знаем о PageRank?

В этой статье мы излагаем только факты.

Последнюю неделю мы рассмотрели множество фактов и предположений, которые показались нам реалистичными. Кроме того, мы собрали некоторые академические материалы по поиску и 16 полезных инструментов для работы с PageRank.

Наиболее важные факты кратко описаны в начале статьи.

Как работает PageRank?

1. PageRank один из многочисленных методов используемых Google для определения релевантности и важности страницы.
2. Google интерпретирует ссылку со страницы A на страницу B как голос A в пользу B, конечно учитывается не только количество голосов, но и качество голосующих страниц.
3. PageRank основан на количестве входящих ссылок , но не только на нем, релевантность и качество тоже важны.
4. Не все ссылки одинаково влияют на PageRank.
5. Если на странице с PR8 есть только одна ссылка, то сайт, на который она ссылается, получит весь PR который она может передать, если же ссылок 100 то каждая ссылка будет передавать только часть этого PR.
6. Плохие входящие ссылки не влияют на PR.
7. В PR учитывается время существования сайта, релевантность входящих ссылок и время их существования.
8. При расчете PR контент не учитывается.
9. PR рассчитывается не для сайта в целом, а для каждой страницы в отдельности.
10. Важна каждая входящая ссылка, за исключением ссылок с забаненых сайтов.
11. PR это не только целые значения от 0 до 10, это вещественное число.
12. Достичь каждого следующего уровня PR все сложнее, предположительно используется логарифмическая шкала.
13. PR пересчитывается постоянно, но данные для тулбара обновляются раз в несколько месяцев.
14. Google старается найти страницы солидные и релевантные одновременно.

Факторы, влияющие на PageRank

1. Частые обновления сайта не увеличивают PR автоматически.
2. Высокий PR не гарантирует высокие позиции в результатах поиска.
3. Каталоги DMOZ и Yahoo! не увеличивают PR автоматически.
4. .edu и.gov сайты не увеличивают PR автоматически.
5. Внутренние страницы не обязательно имеют меньший PR чем главная.
6. Ссылки с сайта Wikipedia не увеличивают PR автоматически.
7. Ссылки с атрибутом nofollow не влияют на PR.
8. Эффективные внутренние ссылки влияют на PR.
9. Ссылки с тематических сайтов влияют сильнее.
10. Текст, используемый в ссылке, часто может быть важнее, чем PR ссылающейся страницы.
11. Исходящие и входящие ссылки на качественные тематические сайты положительно влияют на PR.
12. Несколько одинаковых ссылок с одной страницы считаются за одну.
13. Сайт может быть забанен за ссылки на забаненные сайты.

1.1 Что такое PageRank?

• PR это только один из методов используемых Google для определения релевантности и важности страницы. [PageRank Explained Correctly 6 ]
• Google использует множество факторов для ранжирования страниц, PageRank один из лучших . PR отражает два важных момента, как много страниц ссылаются на данную и какого уровня страницы на нее ссылаются. Пять шесть ссылок с таких сайтов как www.cnn.com 7 или www.nytimes.com 8 , могут быть более полезны, чем гораздо большее количество ссылок с менее солидных сайтов. [Google Librarian Central 9 ]
• PR может отражать только приблизительное качество страницы , но никак не связан с ее тематической релевантностью, которую можно определить только учитывая контекст ссылок, и такие факторы как плотность ключевых слов, заголовок страницы и т.п. [PageRank: An Essay 10 ]

1.2 Как работает PageRank?

• Никто точно не знает, как Google рассчитывает PR. [Google PageRank Explained 11 ]
• PR(A) = (1-d) + d(PR(t1)/C(t1) + … + PR(tn)/C(tn)). Так выглядит примерная формула расчета PR, где t1-tn страницы, ссылающиеся на A, С(tn) количество исходящих ссылок на соответствующий странице, d коэффициент обычно равный 0.85.
• Можно предположить, что PR вычисляется по формуле PR = 0.15 + 0.85 * (часть PR каждой ссылающейся страницы передаваемая нашей). Количество PR, которое страница может использовать, чтобы голосовать за другие, чуть меньше чем ее собственный PR, а точнее 0.85 * PR, это количество и делиться между страницами, на которые она ссылается. [Google’s Page Rank 12 ]
• Алгоритм вычисления PR, основан на распределении собственного PR страницы, между страницами на которые она ссылается. К примеру, если на странице с PR8 есть только одна ссылка, то страница, на которую она ссылается, получит весь доступный PR, но если на этой странице 100 ссылок, то каждая из них получит только сотую часть доступного PR. [The Importance of PageRank 13 ]
• Вследствие, такого алгоритма вычисления PR, ссылка со страницы с PR4 и 5 внешними ссылками, эффективнее ссылки со страницы с PR8 и 100 внешних ссылок. PR ссылающихся страниц важен, но не менее важно и количество исходящих ссылок, которое они содержат, чем больше исходящих ссылок тем меньше PR перейдет каждой. [Google’s Page Rank 12 ]
• PR использует входящие ссылки как индикатор важности страницы. Google интерпретирует ссылку со страницы A на страницу B как голос страницы A в пользу страницы B. Учитывается не только количество голосов, но и качество голосующих страниц. Чем выше PR страницы, тем большее значение имеет ее голос. [Google: Technology 14 ]
• Не все ссылки одинаково полезны. Чем выше PR ссылающейся страницы, тем больший PR она передает, но нужно учитывать и то, что этот PR делиться в равной степени между всеми страницами на которые она ссылается. Поэтому ссылка со страницы с PR4 и единственной исходящей ссылкой, может дать больше чем ссылка со страницы с PR5 и 100 исходящих ссылок. Типичный пример всем известные миллионодоларовые главные страницы, такая страница с PR7 и сотнями исходящих ссылок, несмотря на свою важность, передает другим страницам незначительный PR. [Google PageRank Explained 11 ]
• Каждый следующий уровень PR достигается значительно сложнее

Как оптимизировать мой расчет PageRank?

В книге Программирование коллективного разума я нашел следующую функцию для вычисления PageRank:

def calculatepagerank(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("drop table if exists pagerank")
    self.con.execute("create table pagerank(urlid primary key,score)")
    self.con.execute("create index prankidx on pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("insert into pagerank select rowid,1.0 from urllist")
    self.dbcommit()

    for i in range(iterations):
        print "Iteration %d" % i
        for (urlid,) in self.con.execute("select rowid from urllist"):
            pr=0.15

            # Loop through all the pages that link to this one
            for (linker,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
                # Get the PageRank of the linker
                linkingpr=self.con.execute("select score from pagerank where urlid=%d" % linker).fetchone()[0]

                # Get the total number of links from the linker
                linkingcount=self.con.execute("select count(*) from link where fromid=%d" % linker).fetchone()[0]

                pr+=0.85*(linkingpr/linkingcount)

            self.con.execute("update pagerank set score=%f where urlid=%d" % (pr,urlid))
        self.dbcommit()

Однако эта функция работает очень медленно из-за всех запросов SQL в каждой итерации

>>> import cProfile
>>> cProfile.run("crawler.calculatepagerank()")
         2262510 function calls in 136.006 CPU seconds

   Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.000    0.000  136.006  136.006 <string>:1(<module>)
     1   20.826   20.826  136.006  136.006 searchengine.py:179(calculatepagerank)
    21    0.000    0.000    0.528    0.025 searchengine.py:27(dbcommit)
    21    0.528    0.025    0.528    0.025 {method 'commit' of 'sqlite3.Connecti
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler
1339864  112.602    0.000  112.602    0.000 {method 'execute' of 'sqlite3.Connec 
922600    2.050    0.000    2.050    0.000 {method 'fetchone' of 'sqlite3.Cursor' 
     1    0.000    0.000    0.000    0.000 {range}

Поэтому я оптимизировал функцию и придумал это:

def calculatepagerank2(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("drop table if exists pagerank")
    self.con.execute("create table pagerank(urlid primary key,score)")
    self.con.execute("create index prankidx on pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("insert into pagerank select rowid,1.0 from urllist")
    self.dbcommit()

    inlinks={}
    numoutlinks={}
    pagerank={}

    for (urlid,) in self.con.execute("select rowid from urllist"):
        inlinks[urlid]=[]
        numoutlinks[urlid]=0
        # Initialize pagerank vector with 1.0
        pagerank[urlid]=1.0
        # Loop through all the pages that link to this one
        for (inlink,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
            inlinks[urlid].append(inlink)
            # get number of outgoing links from a page        
            numoutlinks[urlid]=self.con.execute("select count(*) from link where fromid=%d" % urlid).fetchone()[0]            

    for i in range(iterations):
        print "Iteration %d" % i

        for urlid in pagerank:
            pr=0.15
            for link in inlinks[urlid]:
                linkpr=pagerank[link]
                linkcount=numoutlinks[link]
                pr+=0.85*(linkpr/linkcount)
            pagerank[urlid]=pr
    for urlid in pagerank:
        self.con.execute("update pagerank set score=%f where urlid=%d" % (pagerank[urlid],urlid))
    self.dbcommit()

Эта функция во много раз быстрее (но использует гораздо больше памяти для всех временных словарей), потому что она позволяет избежать ненужных запросов SQL в каждой итерации:

>>> cProfile.run("crawler.calculatepagerank2()")
     90070 function calls in 3.527 CPU seconds
Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.004    0.004    3.527    3.527 <string>:1(<module>)
     1    1.154    1.154    3.523    3.523 searchengine.py:207(calculatepagerank2
     2    0.000    0.000    0.058    0.029 searchengine.py:27(dbcommit)
 23065    0.013    0.000    0.013    0.000 {method 'append' of 'list' objects}
     2    0.058    0.029    0.058    0.029 {method 'commit' of 'sqlite3.Connectio
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler
 43932    2.261    0.000    2.261    0.000 {method 'execute' of 'sqlite3.Connecti
 23065    0.037    0.000    0.037    0.000 {method 'fetchone' of 'sqlite3.Cursor'
     1    0.000    0.000    0.000    0.000 {range}

Но можно ли еще больше уменьшить количество запросов SQL, чтобы ускорить работу функции? Обновление: исправлен отступ в calculatepagerank2().

for urlid, in self.con.execute('select rowid from urllist'):
    inlinks[urlid] = []
    numoutlinks[urlid] = 0
    pagerank[urlid] = 1.0

for src, dest in self.con.execute('select fromid, toid from link'):
    inlinks[dest].append(src)
    numoutlinks[src] += 1

for (urlid,) in self.con.execute("select rowid from urllist"):
    ...
    for (inlink,) in self.con.execute("select distinct fromid from link where toid=%d" % urlid):
        ...
        numoutlinks[urlid]=self.con.execute("select count(*) from link where fromid=%d" % urlid).fetchone()[0]            

import collections
import itertools
def constant_factory(value):
    return itertools.repeat(value).next

inlinks=collections.defaultdict(set)

pagerank=collections.defaultdict(constant_factory(1.0))

import collections
def constant_factory(value):
    return itertools.repeat(value).next
def calculatepagerank2(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("DROP TABLE IF EXISTS pagerank")
    self.con.execute("CREATE TABLE pagerank(urlid primary key,score)")
    self.con.execute("CREATE INDEX prankidx ON pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("INSERT INTO pagerank SELECT rowid,1.0 FROM urllist")
    self.dbcommit()

    inlinks=collections.defaultdict(set)

    sql='''SELECT fromid,toid FROM link WHERE toid IN (SELECT rowid FROM urllist)'''
    for f,t in self.con.execute(sql):
        inlinks[t].add(f)

    numoutlinks={}
    sql='''SELECT fromid,count(*) FROM link WHERE fromid IN (SELECT rowid FROM urllist) GROUP BY fromid'''
    for f,c in self.con.execute(sql):
        numoutlinks[f]=c

    pagerank=collections.defaultdict(constant_factory(1.0))
    for i in range(iterations):
        print "Iteration %d" % i
        for urlid in inlinks:
            pr=0.15
            for link in inlinks[urlid]:
                linkpr=pagerank[link]
                linkcount=numoutlinks[link]
                pr+=0.85*(linkpr/linkcount)
            pagerank[urlid]=pr
    sql="UPDATE pagerank SET score=? WHERE urlid=?"
    args=((pagerank[urlid],urlid) for urlid in pagerank)
    self.con.executemany(sql, args)
    self.dbcommit()

    def calculatepagerank4(self,iterations=20):
    # clear out the current PageRank tables
    self.con.execute("drop table if exists pagerank")
    self.con.execute("create table pagerank(urlid primary key,score)")
    self.con.execute("create index prankidx on pagerank(urlid)")

    # initialize every url with a PageRank of 1.0
    self.con.execute("insert into pagerank select rowid,1.0 from urllist")
    self.dbcommit()

    inlinks={}
    numoutlinks={}
    pagerank={}

    for (urlid,) in self.con.execute("select rowid from urllist"):
        inlinks[urlid]=[]
        numoutlinks[urlid]=0
        # Initialize pagerank vector with 1.0
        pagerank[urlid]=1.0

    for src,dest in self.con.execute("select distinct fromid, toid from link"):
        inlinks[dest].append(src)
        numoutlinks[src]+=1          

    for i in range(iterations):
        print "Iteration %d" % i

        for urlid in pagerank:
            pr=0.15
            for link in inlinks[urlid]:
                linkpr=pagerank[link]
                linkcount=numoutlinks[link]
                pr+=0.85*(linkpr/linkcount)
            pagerank[urlid]=pr

    args=((pagerank[urlid],urlid) for urlid in pagerank)
    self.con.executemany("update pagerank set score=? where urlid=?" , args)
    self.dbcommit() 

>>> cProfile.run("crawler.calculatepagerank4()")
     33512 function calls in 1.377 CPU seconds
Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
     1    0.004    0.004    1.377    1.377 <string>:1(<module>)
     2    0.000    0.000    0.073    0.036 searchengine.py:27(dbcommit)
     1    0.693    0.693    1.373    1.373 searchengine.py:286(calculatepagerank4
 10432    0.011    0.000    0.011    0.000 searchengine.py:321(<genexpr>)
 23065    0.009    0.000    0.009    0.000 {method 'append' of 'list' objects}
     2    0.073    0.036    0.073    0.036 {method 'commit' of 'sqlite3.Connectio
     1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler
     6    0.379    0.063    0.379    0.063 {method 'execute' of 'sqlite3.Connecti
     1    0.209    0.209    0.220    0.220 {method 'executemany' of 'sqlite3.Conn
     1    0.000    0.000    0.000    0.000 {range}