14 июля 2011 г.

Алгоритм группирования контактов в Gmail

Оригинал статьи: Gmail’s Friend Suggest Algorithm

Недавняя статья Google (в PDF) предлагает немало интересной информации об алгоритме, используемом в Gmail для группирования контактов (Friend Suggest).

Анализируя исходящие и входящие сообщения, Gmail создаёт социальный граф для каждого пользователя. «Мы называем гиперграф, составленный из всех дуг, ведущих к тому или иному пользователю и ведущих от него, эгоцентричной сетью этого пользователя. <…> Дуги в этом неявном социальном графе характеризуются как направлением, так и весом. Направление дуги определяется тем, сформирована она исходящим письмом пользователя или входящим письмом, направленном пользователю. Также существуют двунаправленные (входяще-исходящие) дуги, соединяющие пользователя и неявную группу, если пользователь как посылал письма этой группе, так и получал письма от неё. Утверждая, что пользователь получал письма от некой группы, мы объединяем отправителя письма и нескольких получателей в неявную группу. <…> Вес дуги определяется частотой почтовых взаимодействий между пользователем и группой, причём недавние взаимодействия имеют больший вес».

Вот такой существует социальный граф, пусть это и неочевидно и не так много функций Gmail используют его. Алгоритм группирования контактов Friend Suggest использует неявные группы, предлагая добавить тот или иной контакт в список получателей письма (функция «Don’t forget Bob!») или, напротив, исключить контакт, включённый в список по ошибке (функция «Got the wrong Bob?»). Эти функции недавно перешли из разряда экспериментальных (Gmail Labs) в основной интерфейс.


«Наш алгоритм вдохновлён следующим наблюдением: хотя пользователи неохотно тратят своё время и силы на то, чтобы создать явную группу в Контактах, они, тем не менее, неявно организуют свои контакты в группы, взаимодействуя с адресатами».

По сведениям Google, не менее 10 % сообщений Gmail отсылаются более чем одному адресату и не менее 4 % отсылаются более чем 5 адресатам. Все эти сообщения позволяют Google проводить автоматическое группирование контактов и динамически его корректировать.

Google утверждает, что алгоритм Friend Suggest можно применять и для других целей, «например, для определения достойных доверия (trusted) рекомендаций в онлайн-системах отзывов и рекомендаций или для улучшения совместного доступа пользователей к различному онлайн-контенту».

От переводчика

«Не тот Боб» проиллюстрирован выше. А вот как работает у меня «Не забудьте Боба»: