Исследование методов и реализация алгоритма моделирования распространения информации в социальных сетях

Размещено на http://www.allbest.ru/

Исследование методов и реализация алгоритма моделирования распространения информации в социальных сетях

Айналимов Б.О.,

Научный руководитель КоротковаН.Н.

Волжский политехнический институт (филиал) ФГБОУ ВПО "Волгоградский государственный технический университет" Волжский, Россия

Анализ социальных данных стремительно набирает популярность во всём мире [1, 2] благодаря появлению в 1990-х годах онлайновых сервисов социальных сетей (SixDegrees, LiveJournal, Facebook, Twitter, YouTube и другие). Таким образом, социальные сети являются уникальным источником данных о личной жизни и интересах реальных людей. Это открывает беспрецедентные возможности для решения исследовательских и бизнес-задач. Такой бизнес-задачей может являться отправка отложенных и условных статусов (постов) в Twitter.

Обработка социальных данных требует разработки соответствующих алгоритмических и инфраструктурных решений, позволяющих учитывать их размерность. К примеру, база данных социальной сети Twitter на сегодняшний день содержит более 1 миллиарда пользовательских аккаунтов и более 100 миллиардов связей между ними. Каждый день пользователи добавляют более 200 миллионов фотографий и оставляют более 2 миллиардов комментариев к различным объектам сети.

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

Цель данной работы: повышение эффективности взаимодействия менеджера рекламного агентства с большим количеством аккаунтов социальной сети Twitter при медиапланировании. Для достижения поставленной цели необходимо решения следующих исследовательских задач: социальный сеть размерность аккаунт

1) математическое описание методов и реализации алгоритма моделирования распространения информации в социальных сетях.

2) разработка алгоритмов и программная реализация web-ориентированной информационной системы условного и отложенного постинга в Twitter.

3) экспериментальная оценка эффективности предлагаемых критериев и алгоритмов.

СРАВНИТЕЛЬНЫЙ АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ И РЕАЛИЗАЦИИ АЛГОРИТМА МОДЕЛИРОВАНИЯ РАСПРОСТРАНЕНИЯ ИНФОРМАЦИИ В СОЦИАЛЬНЫХ СЕТЯХ.

Существует ряд методов, позволяющих находить решение задачи об отложенном постинге. При выборе алгоритма решения приходится выбирать между точными алгоритмами, которые не применимы для стеков большой размерности, и приближенными, которые работают быстро, но не обеспечивают оптимального решения задачи. Если перебирать всевозможные подмножества данного набора из n предметов, то получится решение сложности не менее чем O(2n). В настоящее время неизвестен (и, скорее всего, вообще не существует) алгоритм решения этой задачи, сложность которого является многочленом от n.

Таблица 1. Сравнительный анализ методов и алгоритмов

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

Математическое описание АЛГОРИТМА МОДЕЛИРОВАНИЯ РАСПРОСТРАНЕНИЯ ИНФОРМАЦИИ В СОЦИАЛЬНЫХ СЕТЯХ.

Общего критерия оценки применимости жадного алгоритма для решения конкретной задачи не существует, однако, для задач, решаемых жадными алгоритмами, характерны две особенности: во-первых, к ним применим Принцип жадного выбора, а во-вторых, они обладают свойством Оптимальности для подзадач [5].

Принцип жадного выбора

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

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

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

Рассуждение завершается по индукции.

Оптимальность для подзадач

Говорят, что задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит в себе оптимальные решения для всех её подзадач. Например, в задаче о выборе заявок можно заметить, что если -- оптимальный набор заявок, содержащий заявку номер 1, то -- оптимальный набор заявок для меньшего множества заявок , состоящего из тех заявок, для которых [4].

Программная реализация алгоритма моделирования распространения информации в социальной сети «Twitter».

Был разработан метод поиска неявных сообществ пользователей социальных сетей на основе социальных связей между ними. Предложенный алгоритм локально имитирует человеческое общение между парами индивидуумов, а глобально моделирует инфекционный процесс. Основой алгоритма является процесс обмена метками сообществ между вершинами в соответствии с динамическими правилами взаимодействия, в ходе которого поощряется объединение сообществ ближайших контактов отдельных пользователей в глобальные сообщества. Дополнительным шагом алгоритма является определение сообществ с недостаточной внутренней связанностью и разделение их на более связные подсообщества [6]. Разработанный метод обладает следующими особенностями:

* применимость к ориентированным и неориентированным графам;

* учёт весов на рёбрах;

* поиск как пересекающихся, так и непересекающихся сообществ;

* поиск как локальных (среди ближайших контактов пользователя), так и глобальных сообществ;

* низкая вычислительная сложность: , где - количество рёбер в графе;

* возможность распределённой реализации в рамках вычислительной модели Pregel [3]

ER-модель базы данных, интегрированной с алгоритмом показан на рис.2.

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

Разработанное программное обеспечение упрощает взаимодействия менеджера рекламного агентства с социальной сетью Twitter при решении задачи медиапланирования.

Список литературы

1. Журнал «Вестник Ленинградского государственного университета им. А.С.Пушкина.» (№1. том VII. 2013 г.)

2. Журнал «Труды Международного симпозиума «Надежность и качество».» (том I. 2013 г.)

3. Журнал «International Journal of Open Information Technologies.» (№1. том II. 2014 г.)

4. Najork M., Wiener J. L. Breadth-first crawling yields high-quality pages. Proceedings of the 10th international conference on World Wide Web. - ACM, 2001. - С. 114-118.

5. Leskovec J., Faloutsos C. Sampling from large graphs. Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. - ACM, 2006. - С. 631-636.

6. Gjoka M. et al. Practical recommendations on crawling online social networks. Selected Areas in Communications, IEEE Journal on. - 2011. - Т. 29. - №. 9. - С. 1872-1892.

Размещено на Allbest.ru