О сервисе 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)

9.5. Перколяция на случайных сетях

 

Перколяцию можно рассматривать и на случайных сетях Эрдоша-Реньи, Уаттса-Строгатса, и т.п. В этом случае вместо бесконечного перколяционного кластера принято говорить о гигантской связной компоненте (giant connected component).

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

  М. Ньюманом (M. Newman) и Д. Уаттсом [117] была рассмотрена задача перколяции на сетях малого мира. При этом была использована модификация сети малого мира. В отличие от того как малый мир вводился в [146] новые связи, далее называемые shortcuts, набрасывались в начальную сеть дополнительно,  все старые связи между соседями не прерывались, оставаясь на своих местах. Как и в стандартной теории протекания может быть введена характерная длина (в теории протекания она называется корреляционной длиной):

  ,

где  - вероятность встретить переброшенную связь (shortcuts),  - число этих связей,  - число узлов сети,  - число соседей, - мерность сети.

Смысл этой длины простой – это характерное расстояние между концами разных наброшенных связей (shortcuts).

Для кратчайшего пути  (среднего, конечно) существует скейлиговая функция:

,

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

,

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

Если же , т.е. , то выполняется:

,

сеть является малым миром, расстояние между узлами растет много медленнее, как логарифм числа узлов.

Вернемся теперь к вопросу о перколяционных свойствах таких сетей. Ответим на несколько вопросов. Что будет происходить, если некоторая доля  узлов выпадет, т.е. не будет проводить (информацию, ток, …)? Чему равно критическое значение , когда в сети еще существует гигантская связная компонента (giant connected component), т.е. когда значительное (сравнимое с полным) число узлов сети еще соединено между собой? В работе [117] показано, что порог протекания  (- число неразорванных связей) связан с долей переброшенных связей (shortcuts)  следующим образом (рис. 48)

.

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

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

  ,

где степень узла лежит в диапазоне .

ris49a-1

ris49b-1

Рис. 49. Зависимость порога протекания -  от доли переброшенных связей - : сверху вниз – число соседей один, два и десять. На правой части ось абсцисс - в логарифмическом масштабе

 

При  выражение для  упрощается . Т.о. образом, если доля выкинутых (разрушенных) узлов больше чем  гигантский кластер отсутствует, т.е. можно считать, что сеть разрушена. Подробно об этом и о том, что происходит в других диапазонах параметра  можно прочитать в [85].