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

8.1. Параметры сложных сетей

 

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

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

        

8.1.1. Параметры узлов сети

 

Для отдельных узлов выделяют следующие параметры:

-         входная степень узла - количество ребер графа, которые входят в узел;

-         выходная степень узла - количество ребер графа, которые выходят из узла;

-         расстояние от данного узла до каждого из других;

-         среднее расстояние от данного узла до других;

-         эксцентричность (eccentricity) - наибольшее из геодезических расстояний (минимальных расстояние между узлами) от данного узла к другим;

-         посредничество (betwetnness), показывающее, сколько кратчайших путей проходит через данный узел;

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

 

8.1.2. Общие параметры сети

 

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

Существует несколько актуальных задач исследования сложных сетей, среди которых можно выделить следующие основные:

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

-          выделение компонент (частей сети), которые связаны внутри и не связаны между собой;

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

-          выделение группировок - групп эквивалентных узлов (которые имеют максимально похожие профили связей).

 

8.1.3. Распределение степеней узлов

 

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

         Сети со степенным  распределением  степеней узлов  называются безмасштабными (scale-free). Именно безмасштабные распределения часто наблюдаются в  реально существующих сложных сетях. При степенном распределении возможно существование узлов с очень высокой степенью, что практически не наблюдается в сетях с пуассоновым распределением.

        

8.1.4. Путь между узлами

 

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

        

где  - количество узлов,кратчайшее расстояние между узлами  и .

Венгерскими математиками П. Эрдёшем (P. Erdős) и А. Реньи (A. Rényi) было показано, что среднее расстояние между двумя вершинами в случайном графе растет как логарифм от числа вершин [88, 89].

 

Пауль Эрдёш (1913-1996)

 

С именем П. Эрдёша связаны не только исследования сложных сетей, но и популярное число Эрдёша, которое используется как один из критериев определения уровня математиков в соответствующем социуме, базирующийся  на так называемой сети соавторства.  Известно,  что Эрдёш написал около полутора тысяч статей, а также, что количество его соавторов превышало 500.  Столь большое число соавторов  и породило  такое понятие, как число Эрдёша, которое  определяется следующим образом: у самого Эрдёша это число равно нулю; у соавторов Эрдёша это число равно единице; соавторы людей с числом Эрдёша, равным единице, имеют число Эрдёша два; и так далее.

  Таким образом, число Эрдёша это длина  пути от некоторого автора до самого Эрдёша по совместным работам.  Известен факт, что  90% математиков обладают числом Эрдёша не выше 8, что соответствует теории "малых миров", речь о которой пойдет ниже.

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

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

 

8.1.5. Коэффициент кластерности

 

Д. Уаттс (D. Watts) и С. Строгатц (S. Strogatz) в 1998 году определили такой параметр  сетей, как коэффициент кластерности [147], который соответствует уровню связности узлов в сети. Этот коэффициент характеризует тенденцию к образованию групп взаимосвязанных узлов, так называемых клик (clique). Кроме того, для конкретного узла коэффициент кластеризации показывает, сколько ближайших соседей данного узла являются также ближайшими соседями друг для друга.

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

 

Watts

strogatz

Д. Уаттс и С. Строгатц

        

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

 

8.1.6. Посредничество

 

Посредничество (betweenness) – это параметр, показывающий, сколько кратчайших путей проходит через узел. Эта характеристика отражает роль данного узла в установлении связей в сети. Узлы с наибольшим посредничеством играют главную роль в установлении связей между другими узлами в сети. Посредничество  узла  определяется по формуле:

,

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

 

8.1.7. Эластичность сети

 

Свойство эластичности сетей относится к распределению расстояний между узлами при изъятии отдельных узлов. Эластичность сети зависит от ее связности, т.е. существовании путей между парами узлов. Если узел будет изъят из сети, типичная длина этих путей увеличится. Если этот процесс продолжать достаточно долго, сеть перестанет быть связной. Р. Альберт (Réka Albert) из университета штата Пенсильвания, США при исследовании атак на интернет-серверы изучала эффект изъятия узла сети, представляющей собой  подмножество WWW из 326000 страниц [65].

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

 

8.1.8. Структура сообщества

 

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