войти зарегистрироваться

АлгоритмыPageRank-сеть разнородных объектов

Данная заметка является развитием предыдущего текста, "Проблемы обобщения PageRank". Суть в том, чтобы более-менее полноценно рейтинговать людей с помощью алгоритма PageRank. Почему именно PageRank? Ну, конечно можно составить что-то типа суммы-анкеты из разных слагаемых и вычислять ее для каждого пользователя. Например, образование среднее столько-то баллов, высшее столько-то, должность офисный планктон столько-то, топ-менеджер столько-то, ученая степень есть/нету, опыт работы столько-то лет (вычисляем функцию от количества лет), рейтинг на Хабре такой-то, количество френдов в Фейсбуке столько-то и т. д. и т. п. Мало что список получится длинным и непонятно, учтете ли вы все наиболее значимые факторы. Но понадобится еще каким-то образом (скорее «на глазок») определить коэффициенты значимости при каждом слагаемом, и это тоже задача. Метод PageRank дает на мой взгляд любопытный способ решить эту последнюю задачу.

АлгоритмыПроблемы обобщения PageRank

Если на вас ссылается кто-то авторитетный, это поднимает ваш статус больше, чем ссылки («голоса») от многих малоавторитетных источников — такова была первоначальная идея ранжирования сайтов Гуглом. Она нашла свое очевидное продолжение в social network analysis, где формула для PageRank является разновидностью центральностей, т.е. определением того, какой из узлов социального графа является более «центральным» и по какому признаку. Я не специалист в данной тематике; из беглого осмотра по диагонали мне показалось, что social network analysis в интернете применяется в основном для нужд social media marketing, где ранжирование людей не является основной целью. Скорее, цель smm — эффективней продвигать бренды, увеличивать продажи и т. п. Однако ранжирование людей может быть самостоятельной интересной целью. Вот здесь я краткотезисно перечислил эти интересы.

JAVAКак Ларри Пейдж изучал Java

Нынешний руководитель Google Ларри Пейдж во времена студенческой юности не был выдающимся программистом. Стивен Леви рассказывает об истории создания программ Backrub и PageRank в своей книге "In the Plex" (цитаты: 1, 2, там же ссылка на первую часть книги, которая лежит в открытом доступе).

Пейдж никак не мог добиться нормальной работы краулера и индексатора из-за большого количества багов в коде и ещё по причине использования нового и нестабильного языка Java. Система всё время падала и не годилась для реальной работы. В архивах ньюс-группы comp.lang.java за 1996 год сохранились вопросы Пейджа. Он пытается выяснить у знающих людей, как назначить User-Agent для заголовка HTTP.

Блог компании ИмхонетСчитаем репутацию пользователей социальных сетей


Зачем нужна репутация?


Репутация может отражать множество связей в системе, связей между системами, их величину и актуальность. Репутация — это статус данного элемента в системе, будь-то это конкретный человек, книга, фильм, сайт или что-то другое. Она позволяет конечному пользователю ориентироваться среди большого объема информации, выбирать для себя лучшее, а так же, если он сам является элементом системы как, например, в социальных сетях, самому «показать себя».

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

GoogleВеб-метрика от Google

image
В рамках проекта «Давайте сделаем интернет быстрее», Google опубликовал некоторые статистические данные о размере, количестве ресурсов и других показателях страниц во Всемирной паутине. Статистика была собрана из выборки в несколько миллиардов веб-страниц в процессе анализа и индексирования «движком» поискового гиганта.
При обработке этих страниц алгоритмом принимались во внимание не только основные html¬-страницы сайтов, но и производились попытки обнаружить и обработать остальные ресурсы, размещаемые на сайтах: таблицы стилей, скрипты и изображения.

GoogleЭксклюзив: Как алгоритм Google управляет интернетом

От переводчика: не думаю, что открываю Америку этим переводом, по большому счету искушенный хабрапользователь не найдет для себя много нового и необычного. Однако, на мой взгляд, это неплохая общеобразовательная статья, в которой удобно собраны и рассмотрены основные вехи и принципы работы поисковых машин. Оригинал статьи опубликован в журнале Wired за март 2010 года. Предупреждаю сразу — статья длинная.

imageХотите ли вы узнать, как Google собирается изменить вашу жизнь? Остановитесь около комнаты совещаний Уагадугу во вторник утром. Это решается здесь, в Калифорнии, в Маунтин Вью, в головном офисе самой влиятельной интернет-компании в мире, в комнате, наполненной тремя десятками инженеров, менеджеров и руководителей, которые определяют, как сделать поисковую машину еще умнее. В этом году компания Google представила около 550 усовершенствований в свой легендарный алгоритм, и каждое определяет выдачу информации. Решения, принимаемые на еженедельном Совещании по Качеству Поиска, влияют на результаты выдачи поисковой системы для любых ваших запросов — «принтер Samsung SF-755p», «страничка Ed Hardy на MySpace» или даже «столица Буркина Фасо», которая, кстати, называется также, как и эта комната для совещаний. Руководит процессом Уди Мэнбер, глава Google по поиску с 2006 года. Предполагаемые изменения вместе с результатами месяцев тестирования в различных странах и на всевозможных языках представляются одно за другим. На экранах рядом друг с другом отображаются результаты запросов до и после изменения. Следом за выдачей результата поиска «гитарный центр вау-вау» — Мэнбер кричит: «Получилось!»

Поисковая оптимизацияGoogle обнаружил ссылки в RSS-фидах

В официальном блоге для веб-мастеров Google объявил о расширении функционала поискового краулера, который забивает адреса в базу для индексации. Теперь он научился извлекать URL из фидов RSS/Atom. Вполне возможно, что эти ссылки будут также использоваться для расчёта PageRank. Скоро многие сайты в целях поисковой оптимизации наверняка начнут переходить на полнотекстовые фиды с обильным количеством внутренних ссылок.

В принципе, добавить сайт в индекс никогда не было проблемой. Даже если на сайт не было ни одной входящей ссылки, то его можно было добавить в индекс Google, просто открыв в браузере с установленным Google Toolbar. Как вариант, можно добавить URL на специальной страничке добавления новых сайтов. Теперь достаточно подписаться на его фид в Google Reader.

Новая фича не только помогает найти новые сайты, но позволяет индексировать новый контент в режиме, близком к реальному времени. Правда, вызывает некоторое удивление, что Google только сейчас научился работать с RSS, но дело явно сдвинулось с мёртвой точки. В планах у них теперь интеграция пуш-бота PubSubHubbub, который позволяет индексировать фиды практически мгновенно после обновления.

Персональные блоги Сайты с 10 PR

Подобные списки в Сети есть давно, но многие устарели. Сервис Separser, например, выдает в рубрике «Самые сильные сайты по PR» лишь 2 сайта с десяткой. Поэтому я решил составить свой список сайтов, PageRank которых равен 10/10:

Поисковые машины и технологииPageRank предсказывает нобелевских лауреатов

Ранжирование учёных по количеству ссылок на их работы — неблагодарное дело. Кто угодно может называть несколько уязвимых мест такой системы.

1. Не все ссылки одинаковы. Значимость ссылающейся работы — это важный фактор.
2. Учёные из разных областей науки пользуются цитатами и ссылками по-разному. Работа в области наук о жизни цитируется шесть раз, работа по физике — три раза, а по математике — всего один.
3. Прорывные работы могут цитироваться реже обычного, потому что они затрагивают нишевые научные области на раннем этапе их развития.
4. Важные работы часто прекращают цитировать, когда они попадают в учебники.

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

Сергей Маслов из Брукхейвенской национальной лаборатории в Нью-Йорке и Сидни Реднер из Бостонского университета задали себе такой же вопрос и предположили, что алгоритм Google PageRank может помочь немного разобраться в проблеме.

Персональные блоги Как квантовые физики PageRank считали

А я всегда говорил, что есть связь между теорией алгоритмов и физикой. Вот, первые подтверждения от профессионалов. Группа учёных предложила смотреть на PageRank как на волновую функцию в потенциале, который определяется разностью входящих и исходящих ссылок на страницу. Учитывая это, и применяя простую алгебраическую магию над исходной формулой для PageRank, математики приходят к уравнению типа уравнения Шрёдингера, решением которого является функция PageRank. Человечеству это, кроме осознания удивительных взаимосвязей в природе, даёт ещё и возможность вычислять PageRank (не точно, похоже, а только приблизительно) в три раза быстрее, чем существующим итеративным методом.

Статья доступна здесь: arxiv.org/abs/0807.4325