Алгоритм PageRank

Продолжаем описание популярных алгоритмов из серии «Топ-10 data mining алгоритмов» и сегодня весьма интересный случай — алгоритм PageRank.

PageRank – это алгоритм ссылочного ранжирования, разработанный для определения относительной важности объекта, связанного с сетью объектов.

Ссылочное ранжирование? Это тип сетевого анализа, определяющий ассоциации (читай, связи) между объектами.

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

Объяснение:

Веб-страницы в интернете связаны друг с другом. Если datascientist.one дает ссылку на РБК, то РБК получает очко в копилку, так как datascientist.one посчитал сайт РБК релевантным.

Но это еще не всё…

Вес балла от datascientist.one оценивается важностью и релевантностью самого сайта.
Другими словами, любая веб-страница, дающая ссылку на datascientist.one, повышает его релевантность.

Резюме?

Эта концепция голосов и релевантности представляет собой PageRank. Голос datascientist.one за РБК увеличивает PageRank РБК, и величина, на которую он увеличится, зависит от влияния и значимости datascientist.one.

Что означают PageRank равные 0,1,2,3 и так далее? Хотя точное значение числа PageRank компания Google не раскрывает, мы можем получить об этом представление.

И вот как:

Видите?

Все это выглядит как соревнование по популярности. Мы все имеем представление о том, какие сайты релевантные и популярные. PageRank просто переводит наше представление в цифры.

Как еще применяется PageRank? PageRank был специально разработан для всемирной сети.

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

Вот 3 инновационных применения PageRank:

Доктор Стефано Аллесина (Stefano Allesina) из Чикагского университета применил PageRank в сфере экологии, чтобы определить, какие из особей являются жизненно важными для поддержания экосистемы.
Twitter разработал WTF (Who-to-Follow) – персонализированный вариант рекомендательного движка, основанного на PageRank, показывающий список людей, на которых стоит подписаться.
Бин Жэнь (Bin Jiang) из Гонконгского политехнического университета использовал вариант PageRank для предсказания перемещения людей на основании топологических метрик в Лондоне.

Требует ли этот метод обучения или он самообучающийся? PageRank обычно расценивают как самообучающийся метод, поскольку он часто используется для определения релевантности веб-страницы.

Почему именно PageRank? Главным достоинством PageRank является надежность, несмотря на сложность получения релевантной входящей ссылки.

Где он используется? Торговая марка PageRank принадлежит компании Google. Однако алгоритм PageRank запатентован Стэндфордским университетом.

Если у вас возник вопрос по поводу того, можете ли вы использовать PageRank: лучше посоветоваться со знающими людьми, но, вероятно, вы можете использовать алгоритм сколько вам угодно, пока он не начнет приносить вам финансовую выгоду.

Вот 3 примера реализации PageRank:

Реализация C++ OpenSource PageRank.
Реализация Python PageRank.
Пакет сетевого анализа igraph в R.

Источник

Пример вычисления pagerank (видео)

Алгоритм PageRank на Python

Вот как выглядит алгоритм ранжирования страниц на Питоне (полные инструкции можно найти по ссылке выше):

import operator
import math, random, sys, csv 
from utils import parse, print_results

class PageRank:
    def __init__(self, graph, directed):
        self.graph = graph
        self.V = len(self.graph)
        self.d = 0.85
        self.directed = directed
        self.ranks = dict()
    
    def rank(self):
        for key, node in self.graph.nodes(data=True):
            if self.directed:
                self.ranks[key] = 1/float(self.V)
            else:
                self.ranks[key] = node.get('rank')

        for _ in range(10):
            for key, node in self.graph.nodes(data=True):
                rank_sum = 0
                curr_rank = node.get('rank')
                if self.directed:
                    neighbors = self.graph.out_edges(key)
                    for n in neighbors:
                        outlinks = len(self.graph.out_edges(n[1]))
                        if outlinks > 0:
                            rank_sum += (1 / float(outlinks)) * self.ranks[n[1]]
                else: 
                    neighbors = self.graph[key]
                    for n in neighbors:
                        if self.ranks[n] is not None:
                            outlinks = len(self.graph.neighbors(n))
                            rank_sum += (1 / float(outlinks)) * self.ranks[n]
            
                # actual page rank compution
                self.ranks[key] = ((1 - float(self.d)) * (1/float(self.V))) + self.d*rank_sum

        return p

if __name__ == '__main__':
    if len(sys.argv) == 1:
        print 'Expected input format: python pageRank.py <data_filename> <directed OR undirected>'
    else:
        filename = sys.argv[1]
        isDirected = False
        if sys.argv[2] == 'directed':
            isDirected = True

        graph = parse(filename, isDirected)
        p = PageRank(graph, isDirected)
        p.rank()

        sorted_r = sorted(p.ranks.iteritems(), key=operator.itemgetter(1), reverse=True)

        for tup in sorted_r:
            print '{0:30} :{1:10}'.format(str(tup[0]), tup[1])

 #       for node in graph.nodes():
 #          print node + rank(graph, node)

            #neighbs = graph.neighbors(node)
            #print node + " " + str(neighbs)
            #print random.uniform(0,1)

def rank(graph, node):
    #V
    nodes = graph.nodes()
    #|V|
    nodes_sz = len(nodes) 
    #I
    neighbs = graph.neighbors(node)
    #d
    rand_jmp = random.uniform(0, 1)

    ranks = []
    ranks.append( (1/nodes_sz) )
    
    for n in nodes:
        rank = (1-rand_jmp) * (1/nodes_sz) 
        trank = 0
        for nei in neighbs:
            trank += (1/len(neighbs)) * ranks[len(ranks)-1]
        rank = rank + (d * trank)
        ranks.append(rank)

import operator

import math, random, sys, csv

from utils import parse, print_results

class PageRank:

def __init__(self, graph, directed):

self.graph = graph

self.V = len(self.graph)

self.d = 0.85

self.directed = directed

self.ranks = dict()

def rank(self):

for key, node in self.graph.nodes(data=True):

if self.directed:

self.ranks[key] = 1/float(self.V)

else:

self.ranks[key] = node.get('rank')

for _ in range(10):

for key, node in self.graph.nodes(data=True):

rank_sum = 0

curr_rank = node.get('rank')

if self.directed:

neighbors = self.graph.out_edges(key)

for n in neighbors:

outlinks = len(self.graph.out_edges(n[1]))

if outlinks > 0:

rank_sum += (1 / float(outlinks)) * self.ranks[n[1]]

else:

neighbors = self.graph[key]

for n in neighbors:

if self.ranks[n] is not None:

outlinks = len(self.graph.neighbors(n))

rank_sum += (1 / float(outlinks)) * self.ranks[n]

# actual page rank compution

self.ranks[key] = ((1 - float(self.d)) * (1/float(self.V))) + self.d*rank_sum

return p

if __name__ == '__main__':

if len(sys.argv) == 1:

print 'Expected input format: python pageRank.py <data_filename> <directed OR undirected>'

else:

filename = sys.argv[1]

isDirected = False

if sys.argv[2] == 'directed':

isDirected = True

graph = parse(filename, isDirected)

p = PageRank(graph, isDirected)

p.rank()

sorted_r = sorted(p.ranks.iteritems(), key=operator.itemgetter(1), reverse=True)

for tup in sorted_r:

print '{0:30} :{1:10}'.format(str(tup[0]), tup[1])

# for node in graph.nodes():

# print node + rank(graph, node)

#neighbs = graph.neighbors(node)

#print node + " " + str(neighbs)

#print random.uniform(0,1)

def rank(graph, node):

nodes = graph.nodes()

#|V|

nodes_sz = len(nodes)

neighbs = graph.neighbors(node)

rand_jmp = random.uniform(0, 1)

ranks = []

ranks.append( (1/nodes_sz) )

for n in nodes:

rank = (1-rand_jmp) * (1/nodes_sz)

trank = 0

for nei in neighbs:

trank += (1/len(neighbs)) * ranks[len(ranks)-1]

rank = rank + (d * trank)

ranks.append(rank)

Алгоритм PageRank в R

Вот как выглядит алгоритм ранжирования страниц на R (более подробную инструкцию можно найти по ссылке):

## Download and install the package
install.packages("igraph")

## Load package
library(igraph)

## Usage
page.rank (graph, algo = c("prpack", "arpack", "power"),
    vids = V(graph), directed = TRUE, damping = 0.85,
    personalized = NULL, weights = NULL, options = NULL) 
page.rank.old (graph, vids = V(graph), directed = TRUE, niter = 1000, 
    eps = 0.001, damping = 0.85, old = FALSE)

## Download and install the package

install.packages("igraph")

## Load package

library(igraph)

## Usage

page.rank (graph, algo = c("prpack", "arpack", "power"),

vids = V(graph), directed = TRUE, damping = 0.85,

personalized = NULL, weights = NULL, options = NULL)

page.rank.old (graph, vids = V(graph), directed = TRUE, niter = 1000,

eps = 0.001, damping = 0.85, old = FALSE)

Аргументы

graph
The graph object.

algo
Character scalar, which implementation to use to carry out the calculation. The default is «prpack», which uses the PRPACK library (https://github.com/dgleich/prpack). This is a new implementation in igraph version 0.7, and the suggested one, as it is the most stable and the fastest for all but small graphs. «arpack» uses the ARPACK library, the default implementation from igraph version 0.5 until version 0.7. power uses a simple implementation of the power method, this was the default in igraph before version 0.5 and is the same as calling page.rank.old.

vids
The vertices of interest.

directed
Logical, if true directed paths will be considered for directed graphs. It is ignored for undirected graphs.

damping
The damping factor (‘d’ in the original paper).

personalized
Optional vector giving a probability distribution to calculate personalized PageRank. For personalized PageRank, the probability of jumping to a node when abandoning the random walk is not uniform, but it is given by this vector. The vector should contains an entry for each vertex and it will be rescaled to sum up to one.

weights
A numerical vector or NULL. This argument can be used to give edge weights for calculating the weighted PageRank of vertices. If this is NULL and the graph has a weight edge attribute then that is used. If weights is a numerical vector then it used, even if the graph has a weights edge attribute. If this is NA, then no edge weights are used (even if the graph has a weight edge attribute.

options
Either a named list, to override some ARPACK options. See arpack for details; or a named list to override the default options for the power method (if algo=»power»). The default options for the power method are niter=1000 and eps=0.001. This argument is ignored if the PRPACK implementation is used.

niter
The maximum number of iterations to perform.

eps
The algorithm will consider the calculation as complete if the difference of PageRank values between iterations change less than this value for every node.

old
A logical scalar, whether the old style (pre igraph 0.5) normalization to use.

Пример

g <- random.graph.game(20, 5/20, directed=TRUE)
page.rank(g)$vector
 
g2 <- graph.star(10)
page.rank(g2)$vector
 
# Personalized PageRank
g3 <- graph.ring(10)
page.rank(g3)$vector
reset <- seq(vcount(g3))
page.rank(g3, personalized=reset)$vector

g <- random.graph.game(20, 5/20, directed=TRUE)

page.rank(g)$vector

g2 <- graph.star(10)

page.rank(g2)$vector

# Personalized PageRank

g3 <- graph.ring(10)

page.rank(g3)$vector

reset <- seq(vcount(g3))

page.rank(g3, personalized=reset)$vector

Итак, немного фактов о самом pagerank:

PageRank — это число, характеризующее исключительно голосующую способность всех входящих ссылок на страницу и то, как сильно они рекомендуют эту страницу.

Каждая уникальная страница сайта, проиндексированная Google, имеет вес PageRank. Люди часто ошибаются, думая о весе сайта, который на самом деле является весом главной страницы этого сайта.

Внутренние ссылки сайта учитываются при расчете веса PageRank для других страниц сайта.

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

Дополнительные файлы: статья и презентация с примерами (англ.).

Алгоритм PageRank

Пример вычисления pagerank (видео)

Алгоритм PageRank на Python

Алгоритм PageRank в R

Аргументы

Пример

Искать

Недавнее

Тематика

Data Scientist # 1

Данные — новый актив!

Войдите в свой аккаунт