Графом по спаму

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

Развитие интернета в последние годы привело к существенным изменениям в способах общения между людьми. Еще 10–15 лет назад пообщаться с человеком можно было или при личной встрече, или по стационарному телефону, или же воспользоваться почтой, отправив письмо или телеграмму. Сейчас же к этим вариантам общения добавились мобильные телефоны и интернет, включающий в себя массу способов поговорить с человеком — это и электронная почта, и icq, и многочисленные чаты, и собственные блоги.

Характерным явлением в свете развития всемирной паутины стали так называемые социальные сети — сайты с большим числом пользователей, которые сами наполняют содержимое ресурса. Примеры подобных сетей хорошо известны — в России это «ВКонтакте» и «Одноклассники», а в США — Facebook (владелец компания Meta признана в России экстремистской и запрещена).

Вышеперечисленные сети ассоциируются в первую очередь со знакомствами и «общением ради общения». Но есть в интернете и тематические социальные сети, направленные на обмен зачастую конкретной информацией, например, LiveJournal (где каждый пользователь может вести свой блог, размещая там фотографии, аудио- и видеозаписи, ставить теги (ключевые слова), давать свои комментарии) или, к примеру, last.fm (где пользователи объединяются по музыкальным интересам).

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

Авторы работы, опубликованной во вторник в Proceedings of the National Academy of Sciences, с математической точки зрения изучили две социальные сети и смоделировали свою сеть.

В компьютерной лингвистике существует эмпирический закон Хипса, который связывает объем документа с объемом словаря уникальных слов, которые входят в этот документ. В общей форме этот закон выглядит так: v(n)=Kn^b, где v — это объем словаря уникальных слов, составленный из текста, который состоит из n уникальных слов, а K и b — обусловленные эмпирически параметры. Для европейских языков K принимает значение от 10 до 100, а b — от 0,4 до 0,6.

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

Авторы работы, проводимой под руководством итальянца Чиро Каттуто, определили пост пользователя в сети как функцию трех аргументов: U — идентификатора пользователя, R — идентификатора ресурса (проще говоря, URL) и набора тегов T (T1, T2, T3, …), используемых пользователем.

Граф

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

Граф легко представить в виде точек на плоскости (узлов), которые попарно соединяют отрезки (рёбра). Обычно такая аналогия не обманывает, а терминология теории графов (смежные рёбра, соседние узлы и так далее) получает наглядное пояснение.

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

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

Каждому ребру в соответствие можно поставить число, которое принято называть весом. Если это число действительное, его вполне можно интерпретировать, как «длину» ребра. Правда, гарантировано изобразить граф из N вершин (число N называют порядком графа) с сохранением длин всех M рёбер (число M - размер) можно лишь в пространстве с числом измерением не меньшим, чем K=N/M; K может составлять, к примеру, и (N-1)/2. Для графа с действительными весами можно ввести и понятие минимального остова - остовного дерева, сумма длин всех рёбер которого минимальна.

Задача нахождения минимального остова не обязательно имеет одно решение, однако существуют быстрые и надёжные алгоритмы для нахождения хотя бы одного такого решения.

Для исследования реальных сетей авторы выбрали два сайта. Одним из них стал обширный ресурс del.icio.us, который бесплатно дает зарегистрированным пользователям услугу хранения и публикации закладок на страницах интернета, и посетители могут просматривать имеющиеся закладки, упорядочивая их по популярности и тегам. С этого сайта для работы было использовано около 5 млн постов, написанных более 0,5 млн пользователей. В общей сложности отобранные для исследования посты содержали около 2 млн разных ссылок и 2,5 млн тегов.

Другой сайт, который использовался в работе, — BibSonomy — содержит в себе гораздо меньше информации, чем del.icio.us, поскольку в нем пользователи сохраняют библиографические ссылки. В исследованиях использовались посты 1400 пользователей, которые содержали в себе чуть более 125 тыс. ссылок, чуть менее 38 тыс. уникальных тегов и около 0,5 млн тегов в общем.

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

Семантическая сеть

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

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

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

Но главный вывод они озвучивают вполне твердо: социальные сети подчинены определенным законам и хорошо описываются математически.

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