О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)

10.4. Модель диффузии информации

           

           

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

Напомним, что в естественных науках под диффузией понимают взаимное проникновение друг в друга соприкасающихся веществ,  вызванное, например, тепловым движением их частиц.

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

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

Концепция клеточных автоматов была впервые предложена больше полстолетия тому назад Дж. Фон Нейманом (J. Von Neumann) [41] и развита С. Вольфрамом (S. Wolfram) в фундаментальной монографии “Новый вид науки” [149].

neum

wolfr8

Дж. Фон. Нейман (1903-1957)  и С. Вольфрам

 

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

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

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

Клеточный автомат представляет собой дискретную динамическую систему, совокупность одинаковых клеток, одинаковым образом соединенных между собой. Все клетки образуют сеть (решетку) клеточных автоматов. Состояние каждой клетки определяются  состоянием клеток, входящих в ее локальную окрестность и называемых ближайшими соседями. Окрестностью конечного автомата с номером    называется множество  его ближайших соседей.  Состояние -го клеточного автомата в момент времени , таким образом, определяется следующим образом:

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

-         изменение значений всех клеток происходит одновременно (единица измерения - такт);

-         сеть клеточных автоматов однородная, т.е. правила изменения состояний для всех клеток одинаковые;

-         на клетку могут повлиять лишь клетки из ее локальной окрестности;

-         множество состояний клетки конечное.

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

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

В случае двумерной решетки, элементами которой являются квадраты, ближайшими соседями, входящими в окрестность элемента ,  можно считать или только элементы, расположенные вверх-вниз и влево-вправо от него (так называемая окрестность фон Неймана: ),  либо добавленные к ним еще и диагональные элементы (окрестность Мура (G. Moore): ).

В модели Мура каждая клетка имеет восемь соседей. Для устранения краевых эффектов решетка топологически  «сворачивается в тор» (рис. 53), т.е. первая строка считается продолжением последней, а последняя – предшествующей первой. То же самое относится и к столбцам.

Рис. 53. Свертывание плоскости в тор. Источник: wikimedia.org

 

Это позволяет определять общее соотношение значения клетки на шаге  по сравнению с шагом :

         С. Вольфрам, классифицируя различные клеточные автоматы, выделил те, динамика которых существенным образом зависит от начального состояния. Подбирая различные начальные состояния, можно получать разнообразнейшие конфигурации и типы поведения. Именно к таким системам относится классический пример - игра "Жизнь", изобретенная Дж. Конвеем (J. Conway) и известная широкому кругу читателей благодаря публикации в книге M. Гарднера (M. Gardner) [12].

Клеточные автоматы с успехом применяются при моделировании процессов распространения инноваций [76]. Клеточные автоматы также используются  при моделировании электоральных процессов, в этом случае предполагается, что избирательные преференции человека определяются установками его ближайшего окружения [43].

 В одной из моделей предполагается, что индивид принимает решение голосовать в момент  за республиканцев или демократов в соответствии с правилом простого большинства. В этой модели учитывались взгляды индивида и четырех его ближайших соседей в момент  (окрестность фон Неймана). Модель исследовалась на большом временном отрезке - до 20 000 тактов. Оказалось, что партийная борьба приводит к очень сложным конфигурациям, которые существенным образом зависят от исходного распределения.

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

Вместе с тем динамике распространения информации присущи некоторые дополнительные свойства, которые были учтены в представленной ниже модели. В модели диффузии информации, наряду  с теми же условиями, которые относятся к клеточному пространству, окрестности Мура и вероятностному правилу принятия новости, дополнительно к у условиям диффузии инноваций предполагалось, что клетка может быть  в одном из трех состояний: 1 - «свежая новость» (клетка окрашивается в черный цвет); 2 - новость, которая устарела, но сохраненная в виде сведений (серая клетка); 3 - клетка не имеет информации, переданной новостным сообщением (клетка белая, информация не дошла или уже забыта). В модели приняты такие правила распространения сообщений:

-         сначала все поле состоит из белых клеток за исключением одной, черной, которая первой «приняла» новость (рис. 54 а);

-         белая клетка может перекрашиваться только в черный цвет или оставаться белой (она может получать новость или оставаться «в неведении»);

-         белая клетка перекрашивается, если выполняется условие, аналогичное модели диффузии инноваций:  (это условие несколько модифицируется для );

-         если клетка черная, а вокруг нее исключительно черные и серые, то она перекрашивается в серые цвета (новость устаревает, но сохраняется как сведения);

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

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

Многочисленные эксперименты с данным клеточным автоматом, доступным в настоящее время в Интернет по адресу http://edu.infostream.ua/newsk.pl показывают, что период его сходимости составляет от 80 до 150 шагов.

Рис. 54. Процесс эволюции системы клеточных автоматов «диффузии новостей»: а - исходное состояние; б-д - промежуточные состояния; е - конечное состояние

        

Типичные зависимости количества клеток, которые находятся в разных состояниях в зависимости от шага итерации приведены на рис. 55. При анализе приведенных графиков следует обратить внимание на такие особенности: 1 - суммарное количество клеток, которые находятся во всех трех состояниях на каждом шагу итерации постоянно и равно количеству клеток, 2 - при стабилизации клеточных автоматов соотношения серых, белых и черных клеток приблизительно составляет: 3:1:0; существует точка пересечения всех трех кривых.

 

ris55

Рис. 55. Количество клеток каждого из цветов в зависимости от шага эволюции: белые клетки - (É); серые клетки - (·); черные клетки – (¡)

 

Детальный анализ полученных зависимостей позволил провести аналогии данной модели «диффузии информации» с некоторыми аналитическими соображениями [107]. Результаты моделирования дают основания предположить, что эволюция серых клеток описывается некоторой непрерывной функцией:

                                                                     

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

Соответственно, динамика белых клеток  (количество клеток в момент ) может моделироваться «перевернутой» функцией  с аналогичными  параметрами:

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

                                                                       

где - количество черных клеток в момент времени .

 

Таким образом, получаем:

                                         

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

                                                              

где - некоторая нормирующая константа.

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

Рис. 56. Непрерывные зависимости, полученные в результате аналитического моделирования, в зависимости от шага эволюции: сплошная линия – серые ( ); пунктирная линия – белые ( ); сплошная жирная линия – черные ( )

 

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