Цвет точки на карте Энзоль соответствует значению Popularity Rank страницы, а сами точки упорядочены слева направо и сверху вниз в порядке возрастания числа хопов (hops) соответствующих веб-страниц. Страницы, явно указанные в конфиге поисковика, получают значение hops равное 0, страницы, предлагаемые к индексированию через веб-форму или были найденые в одном из интерент-каталогов, получают значение hops равным 1. Все остальные страницы при первом попадании в базу поисковика получают значение hops на 1 больше, чем имела страница, где была обнаружена ссылка на эту страницу. В такой сортировке сглаженная карта выглядит так:

Компания Google запатентовала новый алгоритм PhraseRank, который позволит не только бороться с поисковым спамом, но и автоматически определять сайты, не содержащие полезный контент, и созданные исключительно с целью заработка.

Новый патент уже опубликован, и по мнению представителей Google сможет эффективно защитить результаты поиска от недоброкачественного контента.

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

По-видимому, PhraseRank будет работать одновременно с PageRank'ом, причем первый алгоритм будет отвечать за внутренние факторы ранжирования, а второй — за внешние. Если Google все-таки решится внедрить этот алгоритм в свой поиск, нас ждет глобальное перераспределение мирового поискового трафика.

Новый российский поисковик «Вебальта» старается ни в чем не отставать от крупнейших поисковых систем. В частности, для ранжирования сайтов среди результатов поиска они используют специальный алгоритм «взвешивания» входящих ссылок. Аналогичные системы на Google и «Яндексе» называются PageRank и тИЦ (тематический индекс цитирования). В системе «Вебальта» это WebaltaRank (WR).

Кроме количества входящих ссылок и их рейтинга, при вычислении WR учитывается множество дополнительных факторов, в том числе время регистрации доменного имени и репутация хостинг-провайдера. Рейтинг WR обновляется несколько раз в месяц.

Отличительной особенностью WR является то, что каждый сайт может поместить у себя на странице особый значок, который будет показывать WR этого сайта по версии поисковой системы. Значок «Уровень доверия» демонстрирует определенное количество звездочек (от нуля до пяти) и численное значение WR. Например, сайт ya.ru заслужил четыре звездочки и WR 82, а yandex.ru — четыре с половиной звездочки и WR 98.

Специалисты по поисковой оптимизации активно обсуждают очередное обновление Google PR. Как известно, PR (PageRank) — это ключевой параметр оценки «авторитета» сайта в системе Google. Он выполняет примерно ту же роль, что индекс цитирования в «Яндексе». Значение PR напрямую влияет на позиции сайта в результатах поиска по релевантному запросу.

Примерно 95% текста в 25 млрд документов, проиндексированных Google, составлены из маленького словаря в десять тысяч слов. Это значит, что почти любой поисковый запрос выдаст миллионы документов. Таким образом, вычисление релевантности документа представляет собой нетривиальную математическую задачу. Для этого используется комбинация сложнейших математических методов. К тому же, содержимое веба постоянно изменяется, так что показатель релевантности нужно постоянно пересчитывать. Центральное место в системе ранжирования Google занимают алгоритмы PageRank.

Процесс мышления в человеческом мозге происходит примерно по тем же принципам, которые заложены в основу легендарного алгоритма ранжирования PageRank. Психологи из университета Беркли, специализирующиеся на вычислительных моделях когнитивных процессов, выяснили, что запатентованные компанией Google алгоритмы лучше всего описывают то, что можно наблюдать во время экспериментов по изучению словарной памяти у хомо сапиенс. Результаты своей работы “Google and the Mind: Predicting Fluency With PageRank” Том Гриффитс с коллегами опубликовали в журнале Psychological Science, vol 18, p 1069 (платная подписка). В свободном доступе имеются другие научные работы Гриффитса примерно на ту же тему.

В связи с этим вспоминаются прогнозы технического директора Google Крейга Сильверштейна о поисковых технологиях будущего. Три года назад он сказал, что интерфейс Google может быть встроен прямо в мозг с помощью специального генетически модифицированного животного-нейроимплантанта. Действительно, прямой и мгновенный доступ ко всем знаниям человечества на порядок улучшит наши когнитивные способности. В свою очередь, такое нововведение может вывести цивилизацию на новый виток развития и вплотную приблизить её к точке сингулярности.

via New Scientist

В течение долгого времени компания Google хранила в строгом секрете формулы своих поисковых алгоритмов. Причины понятны: во-первых, чтобы защититься от конкурентов; во-вторых, чтобы эту информацию не могли использовать в своих целях «чёрные» оптимизаторы. И вот, наконец, политика скрытности начинает меняться. Глава подразделения поискового качества (Search Quality) Уди Манбер опубликовал сообщение в корпоративном блоге, которое он сам называет первым шагом по открытию ранее секретной информации.

В первом сообщении Уди Манбер рассказывает об основах системы ранжирования поискового движка Google. Он объясняет, что всем известный алгоритм PageRank является частью гораздо более масштабной системы, которая включает в себя языковые модели (обработка фраз, синонимов, опечаток и т.д.), модели обработки запросов (это не лингвистика, а попытка понять суть поисковых запросов), временные модели (на некоторые запросы лучше выдавать самые свежие страницы, проиндексированные в последние 30 минут, а на другие — старые страницы с проверенным качеством), а также модели персонализации.

В первом сообщении Манбера мы не видим ничего «секретного», чего бы не знали раньше. Но это только начало, и в будущем Манбер может опубликовать новую интересную информацию, та что есть смысл внимательно следить за корпоративным блогом Google.

Независимые эксперты с иронией комментируют, что Google всегда была не менее закрытой компанией, чем Microsoft. Даже хуже, более лицемерной, потому что система работы Google такая: они заставляют людей открывать информацию в свободный доступ, собирают её в свой закрытый «чёрный ящик», с помощью которого зарабатывают деньги. Понятно, что такие действия вызывают некоторое недовольство у авторов контента, так что новая стратегия Google по открытию своих алгоритмов — это, в какой-то степени, вынужденный шаг.

База Google достигла знакового рубежа в триллион URL и продолжает расти в геометрической прогрессии.

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

Поисковик начал работу в 1998 году с 28 млн страниц в индексе, а к 2000 году база достигла 1 миллиарда. За последние восемь лет индекс вырос ещё в тысячу раз. Как сообщается в официальном блоге, даже разработчики Google не могли предположить такого стремительного роста количества информации веба. В настоящее время интернет прирастает на несколько миллиардов страниц в день.

Чтобы обрабатывать такие массивы данных, Google в последние годы значительно нарастил мощность своих дата-центров. Если десять лет назад одна рабочая станция в серверной стойке способна рассчитать граф PageRank для всего веба (26 млн страниц) за пару часов, и потом неделю поисковик работал без переиндексации, то сегодня Google обновляет индекс гораздо чаще. Связи между триллионом веб-страниц пересчитываются несколько раз в сутки.

UPD. Статья уже переведена уважаемым Jenek и находится по адресу: designformasters.info/posts/google-page-rank

По просьбам здесь начал переводить статью "Google PageRank: What Do We Know About It?". Пока только то, что успел за вчерашний вечер. Если это кому-нибудь нужно продолжение — напишите, я переведу и выложу все остальное. Вычитка и замеченые ошибки приветствуются, т.к. специально переводить мне еще не приходилось. :)

Google PageRank: Что мы знаем о нем?

Его использует каждый, но почти никто не знает, как он в действительности работает. Google PageRank – это наверно один из важнейших алгоритмов, когда либо разрабатывавшихся в сети. Миллиарды существующих страниц и миллионы страниц появляющихся каждый день – поисковая выдача намного сложнее, чем вы себе представляете. PageRank – один из сотен факторов, которые учитывает Google, чтобы определить наилучший поисковый запрос, помогающий делать поиск простым и эффективным. Но как он на самом деле сделан? Как работает Google PageRank, какие факторы на него воздействуют, а какие нет? И что мы действительно знаем про PageRank?
В этой статье будут только голые факты.
Несколько недель мы производили интенсивные исследования и выбрали массу фактов и предположений о PageRank, которые похожи на действительность. Кроме того, мы собрали научные статьи, относящиеся к поисковой выдаче – таких, как предложения для лучших результатов поиска (например, PageRank, чувствительный к теме). Вы прочитаете про математическую составляющую PageRank, также как и про 16 полезных инструментов для работы с PageRank, которые вы можете использовать для анализа и слежения за вашими веб-проектами.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сегодня мы поговорим о моделировании реальности как о способе мышления, восприятия информации и анализа данных. Будем вместе заново изобретать и улучшать модели, которые сегодня используются в поисковых системах: в метриках качества поиска, при создании факторов ранжирования и даже при построении новых интернет-сервисов. Именно этому посвящена лекция Федора Романенко.



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