Краулинг сети

Материал из Социодинамики
Перейти к: навигация, поиск

Краулинг (англ. crawling- ползущий) – процедура анализа веб-страниц; общий процесс загрузки страниц, просмотра текста и ссылок.

В рамках web-центра прикладной пакет SD/Crawler представляет собой многофункциональный краулер для сбора информации по социальной сети. Он реализует различные пути доступа к данным из социальной сети, например, использование API оператора сети (vkontakte.ru, facebook.com, livejournal.com) или разбор html-кода, который выдается при входе на соответствующие персональные страницы.

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

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

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

Для эффективного сбора информации в социальных сетях важно обеспечить высокую производительность краулера, что достигается за счет баланса операций по просмотру и записи данных в социальной сети, и операций по их передаче в Интернет. Для этого были проведены тестовые измерения производительности краулера SD/Crawler в сети LiveJournal (ЖЖ). За один день функционирования краулер обрабатывает данные около 700 тысяч пользователей сети со средней скоростью работы 490 пользователей в минуту. При этом выполняется около 270 итераций (которые соответствуют заданиям отдельных агентов). Анализ структуры временных затрат показал, что наиболее ресурсоемкими являются операции работы с базой данных (около 70 %), в частности, сохранение связей между пользователями (18.6 %) и списков интересов пользователей (39.4 %). Временные затраты на работу с сетью не превышают 27 %, что указывает на необходимость оптимизации доступа к базе данных.


Литература

1. Castillo C. Effective Web Crawling (Ph.D. thesis). University of Chile. 2004. http://chato.cl/research/crawling_thesis.

2. Chau D. H., Pandit S., Wang S., Faloutsos C. Parallel crawling for online social networks // Proceedings of the 16th international conference on World Wide Web. 2007.

3. Cho J., Garcia-Molina H.,; Page L. Efficient Crawling Through URL Ordering // Seventh International World-Wide Web Conference. Brisbane, Australia. 1998-04/ http://ilpubs.stanford.edu:8090/347/.

4. Kobayashi M., Takeda K. Information retrieval on the web // ACM Computing Surveys (ACM Press). 2000. 32 (2). P. 144–173.

Личные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты