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

Именно обработку всех запросов пользователей осуществляет центр обработки данных, который должен обеспечить единый информационный ресурс с гарантированными уровнями достоверности, доступности и безопасности данных. На каждом таком сервере может находиться от одной до нескольких десятков виртуальных машин, которые способны обрабатывать и удовлетворять соответствующими компонентами или приложениями запросы на предоставление сервиса. Однако "неустойчивая" структура центра обработки данных (ЦОД), в результате миграции является виртуальных машин, вносить задержки при обслуживании запросов на предоставление сервиса [13].

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

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

При исследовании алгоритмов решения задачи условного постинга в социальных сетях, был выявлен ряд алгоритмов и моделей, которые можно успешно применять при моделировании распространения информации в социальных сетях. Апробация была произведена в рамках конференции «Cisco Connect - 2015», где были представлены результаты разработки программного продукта для маркетингового агентства. По результатам конференции, были внесены доработки и произведена повторная апробация в рамках «VK Challenge - 2015», где участники смогли протестировать продукт, а автор оценить возможности многопоточной работы системы при нагрузке более 1000 запросов в минуту.

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

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

Выводы по первой главе. Постановка задач исследования

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

Целью выпускной квалификационной работы является планирование и проведение кампании по продвижению рекламного проекта социальных Twitter-медиа, а также продвижение в собственной социальной сети Writer-ru.ru с моделированием алгоритма расспространения информации в социальных сетях.

Для достижения поставленной цели были решены следующие исследовательские задачи:

· Рассмотреть понятие функционарования социальных сетей.

· Определить критерии эффективности продвижения аккаунта в социальных сетях.

· Разработать методы продвижения проектов в социальных сетях.

· Составить план по автоматизации продвижения услуг в социальных сетях.

· Провести кампанию по продвижению услуг в Twitter.

· Проанализировать эффективность проведенной кампании по продвижению услуг в Twitter.

· Разработать собственную социальную сеть для моделирования алгоритма распространенния информации социальных сетях.

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

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

социальный информация алгоритм интерфейс

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

.1 Обзор алгоритма распространения информации в социальных сетях

Пусть сервис является объектом для предоставления услуги клиентам cloud сети, основной характеристикой которого является продолжительность обработки запроса tобр. Рассмотрим атомарный сервис ― сервис, реализованный одной программой, установленной на одной виртуальной машине. Если установлено несколько атомарных сервисов на одной физической машине, производительность таких сервисов уменьшается, поскольку доступ сервисов к ресурсам физической машины происходит по методу временного разделения. Поэтому в случае увеличения количества сервисов на одной РМ, рост интенсивности поступления запросов на РМ и увеличения интенсивности поступления запросов на каждый сервис увеличивается продолжительность обслуживания запросов каждым сервисом. В случае уменьшение производительности сервиса система управления переносит этот сервис на другую VM или РМ.

Логическая топология не меняется, но данные проходят по другим физическим каналам. В таком случае общее время передачи сервиса от пользователя к ЦОД и в обратном направлении рассчитываться так:

                                                    (2.1)

где: n ― количество запросов;

tкоммут. ― время прохождения запроса через систему коммутации;п.к.з. ― время поиска каналов, по которым будет осуществляться передача;обр. ― время обработки запроса, который является суммой времен обработки запроса сервисом, который состоит из k атомарных сервисов:

                                                                             (2.2)

Поскольку оптимальный путь передачи изменяется, то это приводит к увеличению времени поиска каналов, по которым будет осуществляться передача - tп.к.з., что, в свою очередь, приведет к увеличению общего времени передачи (рисунок 6).

Время поиска маршрута, мкс

Рисунок 6 - Зависимость времени передачи сервису данных от временни поиска канала, по которому производиться передача

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

Метрика этого алгоритма представляется в виде:

                (2.3)

где: Кn ― коэффициенты, которые задает администратор для корректировки композитной метрики;― минимальное значение пропускной способности на пути следования оптимального маршрута, по которому будут направляться данные;― загруженность каждого звена в сети;― суммарная задержка на интерфейсах;― надежность пути.

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

Предположим, что некоторый интерфейс на выходе, при передаче информации от физического сервера А к виртуальной машине, имеет значение задержки t, до порогового значения задержки Т, то есть t <T. Виртуальная машина с целым программным комплексом в результате воздействия различных факторов мигрирует на физический сервер В. Алгоритм поиска пути по критерию минимального времени прохождения, передавая запрос на предоставление сервиса, анализирует, что такого логического оптимального маршрута уже не существует, поскольку на выходе из интерфейса, в случае передачи по "старому" маршруту, значение задержки t превышает пороговое значение Т (рисунок 7).

Суммарная задержка на интерфейсах, мс

Рисунок 7 - Зависимость времени поиска оптимального маршрута от суммарной задержки на интерфейсах

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

Дано:

· Количество разновидностей медиапланирования - n;

· Количество видов имеющихся ресурсов - m;

· Значение ценовых коэффициентов на единицу медиапланирования j-го вида - ,;

· Запасы ресурсов i-го вида - bi, ;

· Матрица затрат ресурсов на медиапланирование - А, в какой aij- затраты i-го вида ресурса на j-й вид медиапланирования;

· Значение ценовых коэффициентов параметрической составляющей ЦФ для каждого го вида медиапланирования - ,.

Переменные:

· - количество медиапланирования.

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

Целевая функция - максимизировать прибыль от продажи услуг медиапланирования:

(2.4)

Ограничения:

  (2.5)

  (2.6)

. (2.7)

Данная задача является задачей параметрического программирования с параметром в целевой функции.

Назначением задачи является определение коэффициентов параметрической составляющей задачи, то есть значений вектора.

Для определения коэффициентов, параметрических составляющих задачи (2.4) - (2.7) необходимо применить один из методов оценки неизвестных величин. К таким методам оценки относятся: метод наименьших квадратов (МНК), взвешенный метод наименьших квадратов, метод - оценок и метод наименьших модулей (МНМ) [1]. При разработке комплекса задач для определения вектора применялся МНМ, в нем минимизируется следующая функция (суммарное отклонение):

, (2.8)

где - неизвестные параметры;

- функция, параметры которой мы оцениваем;

- результаты -го наблюдения .

Задача (2.4) - (2.7) является классической задачей линейного параметрического программирования (ЗЛП) [7], а задача (2.8) может быть сведена к ЗЛП, поэтому решать их будем, используя алгоритмы разработаны для данного класса задач.

Общим методом решения задач данного класса является симплекс-метод. Симплекс-метод - метод решения задачи линейного программирования, в котором осуществляется направлен движение по допустимым базисным решениям к нахождению оптимального решения; симплекс-метод также называют методом постепенного улучшения плана. Метод был разработан американским математиком Джорджем Данцигом в 1947 году.

В основе метода параметрического программирования для ЗПУ с параметром в целевой функции лежат процедуры прямого симплекс-метода с некоторой модификацией, следовательно, для задачи (2.4) - (2.7) будем применять процедуры алгоритма именно этого метода.

Относительно задачи (2.8), то она сводится к задаче линейного программирования, позволит решить ее симплекс-методом.

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

Пусть при  задача имеет оптимальное решение . Без потери общности предположим, что в оптимальном решения небазисные переменные имеют номера 1,…,. Запишем преобразованную задачу, соответствующую оптимальному развязку  ()

(2.9)

где

(2.10)

Здесь коэффициенты составляющей  исчисленные на основе базиса, оптимального относительно ЦФ  при , так что компоненты вектора  необязательно неотъемлемые. Поскольку решение  оптимальный относительно , то

(2.11)

При  параметрическая составляющая не играет никакой роли. При увеличении  от нуля происходит поворот вектора нормали ЦФ , при достижении  определенного значения это может привести к изменению оптимума.