О сервисе 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. Элементы теории перколяции

«- Подожди-ка Хуанита. Ты уж реши.  Эта «Лавина»,

она что: наркотик, вирус или религия?

Хуанита пожала плечами. - А что есть разница?»

Нил Стивенсон

 

9.1. Задача теории перколяции

 

Одной из важных характеристик сложных сетей является возможность протекания по их ребрам тока,  жидкости, информации (трафика) и т.п. Впервые задача перколяции (от англ. percolation – просачивание, протекание) была сформулирована в 1957 г. в работе С.Р. Бродбента (S.R. Broadbent) и Дж.М. Хаммерсли (J.M. Hammersley) [81]. В последствии была развита целая область исследований (в теории графов, теории вероятностей, физике, химии...), названная теорией перколяции, имеющая многочисленные применения на практике. Оказывается, что многие вопросы, которые возникают при анализе сетевой безопасности в Интернет, также непосредственно относятся к теории перколяции [132].

Дж.М. Хаммерсли (1920-2004)

 

Перед теорией перколяции стоят многие вопросы, которые выходят за стандартные рамки дискретной математики и теории вероятностей [48]. Самая простая формулировка задачи теории перколяций следующая. Дана решетка из связей, случайная часть которых  «черная» - проводящая, а остальная – «белая», не проводящая поток. Необходимо найти такую минимальную концентрацию  «черных» связей, при которой еще есть связный путь по «черным» связям сквозь всю решетку. То есть такую концентрацию, когда решетка  в целом проводит.

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

При переходе через порог протекания, т.е. при возникновении бесконечного кластера, свойства системы, характеризующие ее в целом, резко меняются. Если, например, «черная» связь проводит ток, а «белая» нет, то проводимость всей системы   вблизи  имеет вид, представленный на рис. 39.

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

Рис. 40. Проводимость системы вблизи порога протекания

(в логарифмическом масштабе)

 

Решетка может быть упорядоченной - квадратной, треугольной, кубической…  Она может быть и случайной, со случайным числом связей, приходящихся на данный узел. Естественно, что для различных случаев величина порога протекания будет разной. Удивительным оказалось то, что задача определения , казалось бы простая задача, «не поддалась» точным методам теории вероятностей. За редкими исключениями  не удается вычислить аналитически –  необходимо довольно сложное численное моделирование.

         В настоящее время известно много важных обобщений перколяционной задачи, например, рассматриваются случаи, когда «непроводящие» связи проводят, но намного хуже проводящих ведущих;  можно говорить о разных значениях проводимости для разных связей;  можно рассматривать однонаправленные «диодные связи» и т.п.

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