Русская Википедия:Наука о сетях

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Наука о сетях Наука о сетях — это научная область, которая изучает комплексные сети, такие как коммуникационные, компьютерные, биологические, когнитивные и семантические сети, а также социальные сети, и рассматривает различные элементы или участников процесса, представленных узлами (или вершинами), и связи между элементами или участниками, представленные связями (или рёбрами). Эта научная область заимствует теории и методы из теории графов, статистической механики, интеллектуального анализа данных и визуализации информации из информатики, моделирование логического вывода из статистики и социальную структуру из социологии. Шаблон:Не переведено 5 определяет науку о сетях как «изучение сетевых представлений физических, биологических и социальных явлений, ведущее к прогнозирующим моделям этих явлений».[1]

Предпосылки и история

С изучением сетей сталкивались в различных дисциплинах и использовали эту модель как средство анализа сложных и связанных данных. Наиболее ранняя статья из этой области — знаменитая статья о семи кёнигсбергских мостах, написанная Леонардом Эйлером в 1736 году. Математическое описание вершин и рёбер Эйлером стало основой теории графов — области математики, которая изучает свойства попарных связей в сетевой структуре. Теория графов развивалась и нашла применение в химии[2].

Денеш Кёниг, венгерский профессор математики, написал в 1936 году первую книгу по теории графов, озаглавленную «Теория конечных и бесконечных графов»Шаблон:Sfn.

Файл:Moreno Sociogram 1st Grade.png
Социограмма Морено 1-го класса.

В 1930-х годах Якоб Леви Морено, психолог, работающий в традициях гештальтпсихологии, прибыл в США. Он разработал социограмму и представил её публике в апреле 1933 года на съезде студентов-медиков. Морено утверждал, что «до изобретения социометрии никто не знал, как выглядит в точности межличностная структура группы»Шаблон:Sfn. Социограмма была представлением социальной структуры группы учеников начальной школы. Мальчишки дружили с мальчишками, а девочки — с другими девочками, лишь с одним исключением: один из мальчиков сказал, что ему нравится одна девочка, но чувство не было обоюдным. Сетевое представление социальной структуры произвело такое сильное впечатление, что о нем написали в газете The New York Times[3]. Социограмме нашли множество применений, на ее основе сформулировали подходы к анализу социальных сетей.

Применение теории вероятности в науке о сетях развивалось как ответвление теории графов в виде восьми знаменитых статей Пала Эрдёша и Альфреда Реньи о случайных графах. Для социальных сетей Шаблон:Не переведено 5 или p* является замечательной основой, используемой для представления пространства вероятностных связей, появляющихся в социальной сети. Альтернативным подходом к вероятностным сетевым структурам является Шаблон:Не переведено 5, которая моделирует вероятность рёбер, возникающих в сети, основываясь на историческом присутствии или отсутствии ребра в возникающих сетях.

В 1998 Дэвид Крэкхард и Кэтлин Карли представили идею метасети с моделью PCANS. Они предположили, что «все организации структурированы в трёх направлениях, Физические лица, Задачи и Ресурсы». Их статья ввела концепцию, что сети возникают по различным направлениям, а потому они взаимосвязаны. Эта область выросла в другую подобласть науки о сетях, которая называется Шаблон:Не переведено 5.

Позднее другие научные усилия были сфокусированы на математическом описании различных сетевых топологий. Дункан Ваттс совместил данные на сетях с математическим представлением, описывающим граф «Мир тесен». Альберт-Ласло Барабаши и Шаблон:Не переведено 5 разработали масштабно-инвариантую сеть, которая в общих чертах определяет сетевую топологию, которая содержит узловые вершины (хабы) со множеством соединений, количество которых растёт, сохраняя постоянное отношение числа соединений по отношению к числу всех узлов. Хотя многие сети, такие как интернет, оказываются сохраняющими это отношение, другие сети имеют длинные хвосты распределения узлов, которые лишь приближённо сохраняют масштабную инвариантность.

Инициативы Министерства обороны

Военные силы США первыми (в 1996 году) заинтересовались в сетецентрической войне как концепции военных действий, основанных на науке о сетях. Джон А. Парментола, руководитель научно-исследовательского центра и лабораторий армии США (Шаблон:Lang-en), провозгласил на армейском совете по науке и технике (Шаблон:Lang-en) 1 декабря 2003 года, что наука о сетях становится новой областью исследований в армии. BAST, отдел инженерно-технических и физических наук (Шаблон:Lang-en) Национального совета по исследованиям (Шаблон:Lang-en) государственной академии наук, наделена полномочиями организации обсуждений научных и технологических актуальных вопросов для армии и осуществления надзора за независимыми связанными с армией изучениями, проводимыми академией наук. BAST проводит изучение, может ли помочь определение рамок и финансирование новой области, науки о сетях, закрыть разрыв между потребностями осуществления сетецентрических операций и текущим примитивным состоянием фундаментальных знаний о сетях.

Как результат BAST выпустил в 2005 исследовательскую работу NRC, озаглавленную «Наука о сетях», в которой определяется новая область основных исследований в науке о сетях для армии. Основываясь на полученных в этой работе результатах и рекомендациях и на последующем отчёте NRC 2007 года, озаглавленном «Стратегия для армейских центров науки о сетях, технологии и экспериментов», основные армейские исследовательские ресурсы были перенаправлены на инициализацию новых главных исследовательских программ в науке о сетях. Чтобы построить новые теоретические основы для комплексных сетей, поддерживаются некоторые новые ключевые моменты исследования науки о сетях, адресованные армейским лабораториям:

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

С подачи в 2004 году Фредерика И. Моксли и при поддержке Дэвида С. Альбертса Министерства обороны помогло создать первый Центр Науки о сетях (Шаблон:Lang-en) совместно с военной академией (Шаблон:Lang-en) армии США. Под руководством Моксли и сотрудников USMA были созданы междисциплинарные студенческие курсы науки о сетях для курсантов Вест-Пойнт. Для лучшего внедрения основных положений науки о сетях среди будущих лидеров USMA основали также курс из пяти дисциплин.

В 2006 году армия США и Великобритания (UK) сформировали Шаблон:Не переведено 5 (Шаблон:Lang-en) по Сетевой и Информационной Науке (Шаблон:Lang-en), совместное партнёрство Армейской Исследовательской лаборатории, Министерства Обороны Великобритании и консорциум индустрии и университетов в США и Великобритании. Целью альянса является осуществление исследований в поддержке сетецентрических операций в интересах обеих наций.

В 2009 году армия США сформировала Шаблон:Не переведено 5, альянс по совместным исследованиям Шаблон:Не переведено 5, Шаблон:Не переведено 5 и консорциума 30 промышленных исследовательских центров США. Целью альянса является разработка глубокого понимания общих черт переплетающихся социальных/когнитивных, информационных и коммуникационных сетей, а как результат, улучшение нашей возможности анализировать, предсказывать, разрабатывать и влиять на сложные переплетающиеся системы сетей многих видов.

Затем, как результат этих усилий, министерство обороны США спонсировал многочисленные исследовательские проекты, поддерживающие науку о сетях.

Свойства сетей

Часто сети имеют некоторые атрибуты, которые могут быть вычислены для анализа свойств и характеристик сети. Поведение этих свойств сетей часто определяют сетевые модели и они могут быть использованы для анализа, чем отличаются одни модели от других. Многие определения для других терминов, используемых в науке о сетях, можно найти в статье «Глоссарий теории графов».

Размер

Под размером сети может пониматься число узлов <math>N</math> или, реже, число рёбер <math>E</math>, которое (для связных графов без кратных рёбер) может меняться от <math>N-1</math> (дерево) до <math>E_{\max}</math> (полный граф). В случае простого графа (сеть, в которой существует максимум одно (неориентированное) ребро между любой парой вершин и в которой ни одна из вершин не соединена сама с собой), мы имеем <math>E_{\max}=\tbinom N2=N(N-1)/2</math>. Для ориентированных графов (без петель) <math>E_{\max}=N(N-1)</math>. Для ориентированных графов с разрешёнными петлями <math>E_{\max}=N^2</math>. Для случая графа, в котором разрешены кратные рёбра между парой вершин <math>E_{\max}=\infty</math>.

Плотность

Плотность <math>D</math> сети с <math>N</math> узлами определяется как отношение числа рёбер <math>E</math> к числу возможных рёбер в сети и задаётся (в случае простых графов) биномиальным коэффициентом <math>\tbinom N2</math>, что даёт

<math>D =\frac{E-(N-1)}{Emax - (N-1)}=\frac{2(E-N+1)}{N(N-3)+2}</math>

Другое возможное уравнение — <math>D=\frac{T-2N+2}{N(N-3)+2},</math> где связи <math>T</math> неориентированныШаблон:Sfn[4]. Это даёт лучшее понимание плотности сети, поскольку неориентированные связи могут быть измерены.

Планарная сетевая плотность

Плотность сети <math>D</math>, в которой нет пересечений рёбер, определяется как отношение числа рёбер <math>E</math> к числу максимальному числу рёбер в сети с <math>N</math> узлами без пересекающихся рёбер <math>(E_{\max}=3N-6)</math>, что даёт <math>D=\frac{E-N+1}{2N-5}.</math>

Средняя степень узла

Степень <math>k</math> узла — это число рёбер, связанных с ним. Тесно связана с плотностью сети средняя плотность, <math>\langle k\rangle=\tfrac{2E}{N}</math> (или, в случае ориентированных графов, <math>\langle k\rangle=\tfrac{E}{N}</math>. Множитель 2 в предыдущем равенстве возникает из того, что каждое ребро в неориентированном графе делает вклад в степени двух различных вершин). В модели случайного графа Эрдёша — Реньи (<math>G(N,p)</math>) мы можем вычислить ожидаемое значение <math>\langle k \rangle </math> (равно ожидаемому значению <math>k</math> произвольной вершины) — случайная вершина имеет <math>N-1</math> возможных других вершин с вероятностью соединения <math>p</math>. Тогда <math>\mathbb{E}[\langle k \rangle]=\mathbb{E}[k]= p(N-1)</math>.

Средняя длина кратчайшего пути (или характеристика длины пути)

Средняя длина кратчайшего пути вычисляется путём нахождения кратчайшего пути между всеми парами узлов и вычисления средней длины по всем путям (длиной является число рёбер, содержащихся в пути, то есть расстояние <math>d_{u,v}</math> между двумя вершинами <math>u,v</math> в графе). Это показывает нам, в среднем, число шагов, которые нужно сделать от одного узла сети до другого. Поведение математического ожидания средней длины кратчайшего пути как функции числа вершин <math>N</math> модели случайной сети определяет, отражает ли модель эффект малого мира. Если она ведёт себя как <math>O(\ln N)</math>, модель генерирует модель сетей малого мира. При росте большем логарифмического модель не даёт «малый мир». Специальный случай роста <math>O(\ln\ln N)</math> известен как эффект ультрамалого мира.

Диаметр сети

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

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

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

Коэффициент кластеризации <math>i</math>-ого узла равен

<math>C_i={2e_i\over k_i{(k_i - 1)}}\,,</math>

где <math>k_i</math> равно числу соседей <math>i</math>-го узла, а <math>e_i</math> равно числу связей между этими соседями. Максимальное число возможных связей между соседями равно, тогда,

<math>{\binom {k}{2}}={{k(k-1)}\over 2}\,.</math>

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

Связанность

Способ, каким сеть связана, играет большую роль в анализе и интерпретации сети. Сети классифицируются на четыре категории:

  • Клика/Полный Граф — полностью связанная сеть, в которой каждый узел связан с каждым другим узлом. Эти сети симметричны, поскольку все узлы имеют входящие соединения от всех других узлов и исходящие соединения во все остальные узлы.
  • Гигантская компонента — одна связная компонента содержит большинство узлов сети.
  • Слабо связанная компонента — набор узлов, в котором существует путь из любого узла в любой другой без учёта направления рёбер.
  • Сильно связанная компонента — набор узлов, в котором существует ориентированный путь из любого узла в любой другой узел.

Центральность узла

Шаблон:Основная статья Показатели центральности порождают ранжирование, которое пытается выявить наиболее важные узлы в модели сети. Различные показатели центральности кодируют различные контексты слова «важность». Степень посредничества, например, считает узел сильно важным, если он образует мосты между многими другими узлами. Степень влиятельности, в качестве контраста, считает узел сильно важным, если много других сильно важных узлов связаны с ним. Сотни таких мир было предложено в литературе.

Признаки центральности аккуратны только для выявления наиболее центральных узлов. Эти меры редко имеют смысл, если вообще имеют, для остальных узлов сетиШаблон:SfnШаблон:Sfn. Также показатели аккуратны, только когда они используются в контексте важности узлов и стремятся «стать ошибочными» в других контекстахШаблон:Sfn. Например, представим два сообщества, которые соединяются только ребром между наиболее юными членами каждого сообщества. Поскольку переход из одного сообщества в другое должно идти через это ребро, два младших члена будут иметь высокую степень посредничества. Но, поскольку они молоды (по всей видимости), они имеют мало связей с «важными» узлами в собственном сообществе, это означает, что их степень влиятельности будет достаточно низкой.

Концепция центральности в контексте статических сетей были расширены на основе эмпирических и теоретических исследований до динамической центральностиШаблон:Sfn в контексте зависимых от времени и скоротечных сетейШаблон:SfnШаблон:SfnШаблон:Sfn.

Влияние вершин

Шаблон:Основная статья Ограничения мер центральности привели к развитию более общих мер. Двумя примерами являются достижимость, которая использует разброс длины случайных маршрутов для измерения, насколько достижим остаток сети от выбранного начального узлаШаблон:Sfn, и ожидаемая сила, производная от ожидаемого значения Шаблон:Не переведено 5, порождённой узломШаблон:Sfn. Обе эти меры могут быть содержательно вычислены лишь из структуры сети.

Сетевые модели

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

Модель случайного графа Эрдёша — Реньи

Файл:ER model.svg
Модель Эрдёша — Реньи, сгенерированная с <math>N = </math> узлами. Для каждого ребра в полном графе, образованном всеми Шаблон:Mvar узлами, генерится случайное число и сравнивается с заданным значением вероятности. Если случайное число меньше Шаблон:Mvar, образуется ребро.

Модель Эрдёша — Реньи, названная именами Пала Эрдёша и Альфреда Реньи, используется для генерации случайных графов, в которых рёбра образуются между узлами с одинаковыми вероятностями. Модель может быть использована в вероятностном методе для доказательства существования графов с различными свойствами или для обеспечения строгого определения, какие свойства выполняются почти для всех графов.

Для генерации модели Эрдёша — Реньи <math>G(n, p)</math> должны быть заданы два параметра — общее число узлов Шаблон:Mvar и вероятность Шаблон:Mvar, с которой произвольная пара узлов имеет связывающее ребро.

Поскольку модель генерируется без пристрастия к определённым узлам, распределение узлов по числу связей биномиально — для случайно выбранного узла <math>v</math>,

<math>P(\deg(v)=k)={n-1\choose k} p^k (1-p)^{n-1-k}.</math>

В этой модели коэффициент кластеризации равен Шаблон:Math почти наверняка. Поведение <math>G(n, p)</math> можно разбить на три области.

Субкритическая <math>n p < 1</math>: Все компоненты простые и очень маленькие, наибольшая компонента имеет размер <math>|C_1|= O(\log n)</math>;

Критическая <math>n p=1</math>: <math>|C_1|= O(n^\frac{2}{3})</math>;

Суперкритическая <math>n p >1</math>:<math>|C_1|\approx yn</math>, где <math>y=y(n p)</math> является положительным решением уравнения <math>e^{-p n y }=1-y</math>.

Наибольшая связная компонента имеет высокую сложность. Все другие компоненты просты и малы <math>|C_2|= O(\log n)</math>.

Конфигурационная модель

Для конфигурационной модели выбирается последовательность степеней вершинШаблон:SfnШаблон:Sfn или распределение степеней вершинШаблон:SfnШаблон:Sfn (которое затем используется для генерации последовательности вершин) в качестве входа и создаётся случайно связанный граф с сохранением всех степеней вершин последовательности. Это означает, что для данного выбора последовательности степеней граф выбирается однородно из множества всех графов, которые имеют такую последовательность степеней вершин. Степень <math>k</math> случайно выбранной вершины является независимой и одинаково распределённой случайной переменной с целыми значениями. При <math display="inline">\mathbb E [k^2] - 2 \mathbb E [k]>0</math> конфигурационный граф содержит гигантскую связную компоненту, которая имеет неограниченный размерШаблон:Sfn. Остальные компоненты имеют конечные размеры, которые могут быть выражены количественно с помощью распределения размера. Вероятность <math>w(n)</math>, что случайно отобранный узел связан с компонентой размера <math>n</math> задаётся Шаблон:Не переведено 5 распределения степенейШаблон:Sfn

<math display="block">w(n)=\begin{cases}

\frac{\mathbb E [k]}{n-1} u_1^{*n}(n-2),& n>1, \\ u(0) & n=1, \end{cases}</math> где <math>u(k)</math> означает распределение узлов по числу связей и <math>u_1(k)=\frac{(k+1)u(k+1)}{\mathbb E[k]}</math>. Гигантская компонента может быть разрушена путём случайного удаления критичной доли <math>p_c</math> всех вершин. Этот процесс называется перколяцией (просачиванием) на случайных сетях. Если второй момент степени распределения конечен, то есть <math display="inline">\mathbb E [k^2]<\infty</math>, эта критическая доля рёбер задаётся равенствомШаблон:Sfn

<math>p_c=1-\frac{\mathbb E[k]}{ \mathbb E [k^2] - \mathbb E[k]}</math>

и Шаблон:Не переведено 5 <math>l</math> в гигантской компоненте логарифмически пропорционально полному размеру сети <math>l=O(\log N) </math>Шаблон:Sfn.

В модели ориентированной конфигурации степень узла задаётся двумя числами, полустепенью входа <math>k_\text{in}</math> и полустепенью исхода <math>k_\text{out}</math>, и, соответственно, распределения степеней вершин будут двувариантными. Ожидаемое число входящих рёбер и исходящих рёбер совпадает, так что <math display="inline">\mathbb E [k_\text{in}]=\mathbb E [k_\text{out}]</math>. Ориентированная конфигурационная модель содержит гигантскую компоненту тогда и только тогда, когдаШаблон:Sfn

<math display="block">2\mathbb{E}[k_\text{in}]

\mathbb{E}[k_\text{in}k_\text{out}] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{out}^2] - \mathbb{E}[k_\text{in}] \mathbb{E}[k_\text{in}^2] +\mathbb{E}[k_\text{in}^2] \mathbb{E}[k_\text{out}^2] 

- \mathbb{E}[k_\text{in} k_\text{out}]^2 >0.</math>

Заметим, что <math display="inline">\mathbb E [k_\text{in}]</math> и <math display="inline">\mathbb E [k_\text{out}]</math> равны, а потому взаимозаменяемы в последнем неравенстве. Вероятность, что случайно выбранная вершина принадлежит компоненте размера <math>n</math>, задаётся формулойШаблон:Sfn

<math display="block">h_\text{in}(n)=\frac{\mathbb E[k_{in}]}{n-1} \tilde u_\text{in}^{*n}(n-2), \;n>1, \; \tilde u_\text{in}=\frac{k_\text{in}+1}{\mathbb E[k_\text{in}]}\sum\limits_{k_\text{out}\geq 0}u(k_\text{in}+1,k_\text{out}),</math>

для входящих компонент, и

<math>h_\text{out}(n)=\frac{\mathbb E[k_\text{out}]}{n-1} \tilde u_\text{out}^{*n}(n-2), \;n>1, \;\tilde u_\text{out}=\frac{k_\text{out}+1}{\mathbb E[k_\text{out}]}\sum\limits_{k_\text{in}\geq0}u(k_\text{in},k_\text{out}+1),</math>

для исходящих компонент.

Модель тесного мира Уаттса — Строгаца

Файл:Watts-Strogatz-rewire.png
Шаблон:Не переведено 5 использует концепцию перемонтажа для получения структуры модели. Генератор модели итерирует через все рёбра в исходной структуре решётки. Ребро может изменить связанные с ним вершины с заданной вероятностью перемонтажа. В данном примере, <math>\langle k\rangle=4</math>.

Шаблон:Не переведено 5 является моделью генерации случайного графа, которая даёт графы со свойствами «мир тесен».

Для генерации модели Уаттса — Строгаца используется начальная структура решётки. Каждый узел в сети первоначально связан с <math>\langle k\rangle</math> ближайшими соседями. Другой параметр задаёт вероятность перемонтажа. Каждое ребро имеет вероятность <math>p</math>, что оно будет перемонтировано в граф как случайное ребро. Ожидаемое число перемонтированных соединений в модели равно <math>pE=pN\langle k\rangle/2</math>.

Так как модель Уаттса — Строгаца начинается как неслучайная решёточная структура, она имеет очень высокий коэффициент кластеризации вместе с высокой средней длиной пути. Каждый перемонтаж с большой вероятностью создаёт сокращённый путь между сильно связанными кластерами. При увеличении вероятности перемонтажа коэффициент кластеризации уменьшается медленнее, чем средняя длина пути. В результате это позволяет средней длине пути сети уменьшаться существенно при слабом уменьшении коэффициента кластеризации. Высокие значения p приводит к большему числу перемонтажа рёбер, что в результате делает модель Уаттса — Строгаца случайной сетью.

Модель Барабаши — Альберт предпочтительных присоединений

Модель Барабаши — Альберт является моделью случайной сети, используемой для демонстрации предпочтительных присоединений или эффекта «богатый становится богаче». В этой модели ребро наиболее вероятно соединяется с узлами с наибольшими степенями. Сеть начинается с сети с m0 узлами, где <math>m_0 \geqslant 2</math>, а степень каждого узла в начальной сети должна быть по меньшей мере 1, в противном случае узел навсегда останется отсоединённым от остальной части сети.

В модели Барабаши — Альберта новые узлы добавляются в сеть по одному. Каждый новый узел соединяется с <math>m</math> существующими узлами с вероятностью, которая пропорциональна числу уже существующих узлов. Формально, вероятность <math>p_i</math>, что новый узел связен с узлом i, равенШаблон:Sfn

<math>p_i=\frac{k_i}{\sum_j k_j},</math>

где ki является степенью узла i. Наиболее связанные узлы («хабы») стремятся быстро аккумулировать даже больше соединений, в то время как узлы с меньшим числом соединений вряд ли будут выбраны в качестве нового соединения. Новые узлы имеют «преимущество» присоединиться к уже наиболее сильно связанным узлам.

Файл:Barabasi-albert model degree distribution.svg
Распределение узлов по числу связей модели Барабаши BA, которая следует степенному закону. При масштабировании с помощью loglog функции степенного закона получаем прямуюШаблон:Sfn.

Распределение узлов по числу связей, получаемое из BA модели, масштабно инвариантно, в частности, это степенной закон вида

<math>P(k)\sim k^{-3} \, </math>

Хабы показывают высокую степень посредничества, позволяя существованию коротких путей между узлами. В результате модель BA стремится иметь очень короткую среднюю длину путей. Коэффициент кластеризации этой модели также стремится к 0. В то время как диаметр D многих моделей, включая модель случайного графа Эрдёша —Реньи и некоторых сетей «тесного мира», пропорционален log N, модель BA показывает D~loglogN (ультратесный мир)Шаблон:Sfn.

Модель присоединения с помощью посредника

В Шаблон:Не переведено 5 (Шаблон:Lang-en, MDA) новый узел приходит с <math>m</math> рёбрами, для чего выбирается случайным образом существующий связанный узел и новый узел соединяется не только с этим случайно выбранным узлом, но и также с <math>m</math> его соседями, выбранными также случайно. Вероятность <math>\Pi(i)</math>, что соседний узел <math>i</math> существующего узла выбирается, равна

<math> \Pi(i)=\frac{k_i} N \frac{ \sum_{j=1}^{k_i} \frac 1 {k_j} }{k_i}.</math>

Множитель <math>\frac{\sum_{j=1}^{k_i}{\frac{1}{k_j}}}{k_i}</math> равен обратной величине среднего гармонического (ОСГ) степеней <math>k_i</math> соседей узла <math>i</math>. Обширное численное исследование позволяет предположить, что при <math>m > 14</math> среднее значение ОСГ при больших <math>N</math> стремится к константе, это означает, что <math>\Pi(i) \propto k_i</math>. Из этого следует, что чем больше связей (степень) узел имеет, тем выше шанс получить более связей, поскольку они могут быть получены большим числом способов через посредников, что, по существу, воплощает интуитивную идею «богатые становятся богаче» (или правило предпочтительного присоединения модели Барабаши — Альберт). Поэтому сети MDA, как можно понять, подчиняются правилу PA, но в неявном видеШаблон:Sfn.

Однако при <math>m=1</math> получаем механизм «победитель забирает всё», поскольку почти <math>99\%</math> общего числа узлов имеют степень единица, а один узел становится супербогатым. По мере увеличения значения <math>m</math> диспропорция между сверхбогатыми и бедными сокращается и при <math>m>14</math> мы наблюдаем переход механизма от «богатый становится супербогатым» к механизму «богатый становится богаче».

Модель соответствия

Другую модель, в которой ключевым ингредиентом является природа вершины, предложил Калдарелли с соавторамиШаблон:Sfn. Здесь связь создаётся между двумя вершинами <math>i,j</math> с вероятностью, задаваемой функцией связи <math>f(\eta_i,\eta_j)</math> Шаблон:Не переведено 5 вовлечённых вершин. Степень вершины i задаётся формулойШаблон:Sfn

<math>k(\eta_i)=N\int_0^\infty f(\eta_i,\eta_j) \rho(\eta_j) \, d\eta_j </math>

Если <math>k(\eta_i)</math> является обратимой возрастающей функцией от <math>\eta_i</math>, то распределение вероятности <math>P(k)</math> задаётся формулой

<math>P(k)=\rho(\eta(k)) \cdot \eta'(k)</math>

Как результат, если соответствие <math>\eta</math> распределено по степенному закону, то так же распределены и степени узлов.

Менее очевидно при быстро убывающем распределении вероятностей <math>\rho(\eta)=e^{-\eta}</math> вместе со связывающей функцией вида

<math> f(\eta_i,\eta_j)=\Theta(\eta_i+\eta_j-Z)</math>

с константой <math>Z</math> и функцией Хевисайда <math>\Theta</math>, что мы получаем масштабно-инвариантные сети.

Такая модель была успешно применена для описания торговли между нациями с помощью ВВП как меры соответствия для различных узлов <math>i,j</math> и связывающей функцией видаШаблон:SfnШаблон:Sfn

<math> \frac{\delta \eta_i\eta_j}{1+ \delta \eta_i\eta_j}.</math>

Анализ сети

Анализ социальных сетей

Анализ социальной сети исследует структуру связей между общественными субъектамиШаблон:Sfn. Эти субъекты являются часто людьми, но могут быть также и группами, организациями, национальными государствами, сайтами, научными публикациями.

C 1970-х годов эмпирическое изучение сетей играет центральную роль в социальной науке и много математических и статистических средств, используемых для изучения сетей, были разработаны в социологииШаблон:Sfn. Среди многих других приложений анализ социальной сети используется для понимания диффузии инноваций, новостей и слухов. Аналогично, оно может быть использовано как для исследования распространения болезней, так и связанного со здоровьем поведения. Оно также применялось для изучению рынка, где использовалось для проверки роли доверия в товарно-денежных отношениях и социальных механизмов в формировании цен. Аналогично оно использовалось для изучения вовлечения в Шаблон:Не переведено 5 и социальные организации. Использовалось оно также для осмысления научных разногласий и академической репутации. Недавно сетевой анализ (и его ближайший родственник, Шаблон:Не переведено 5) начали интенсивно использоваться в военной разведке для раскрытия социальных сетей сопротивления, имеющих как иерархическую, так и безлидерную природуШаблон:R.

Динамический анализ сети

Шаблон:Не переведено 5 исследует изменение структуры связей среди различных классов объектов в сложных социо-технических системах и отражает социальную стабильность и изменения, такие как появление новых групп, дискуссий и лидеровШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Динамический анализ сети фокусируется метасетях, составленных из узлов многих различных видов (объектов) и Шаблон:Не переведено 5. Эти объекты могут сильно варьироватьсяШаблон:Sfn. В качестве примеров могут быть люди, организации, темы, ресурсы, задачи, события, места расположения и веры (воззрения).

Техники динамической сети особенно удобны для оценки трендов в сети со временем, выделения появляющихся лидеров и исследование коэволюции людей и идей.

Анализ биологических сетей

При взрывном увеличении в недавнем времени публично доступных биологических данных анализ молекулярных сетей получил значительный интерес. Анализ в этих условиях тесно связан с анализом социальной сети, но часто фокусируется на локальные закономерности в сети. Например, сетевые мотивы — это маленькие подграфы, которые чрезмерно представлены в сети. Мотивы активности подобны чрезмерно представленным закономерностям в свойствах узлов и рёбер в сети, которые чрезмерно представлены в сетевой структуре. Анализ биологических сетей привёл к развитию Шаблон:Не переведено 5, которая рассматривает эффект болезней в интерактомеШаблон:Sfn.

Анализ связей

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

Устойчивость сети

Структурная устойчивость сетейШаблон:Sfn изучается с помощью теории перколяции. Когда критическая доля узлов удаляется из сети, сеть распадается на мелкие кластеры. Этот феномен называется перколяциейШаблон:Sfn и представляет тип фазового перехода «порядок-беспорядок» с критическим индексом.

Анализ пандемии

Шаблон:Не переведено 5 является одной из наиболее известных алгоритмов предсказания распространения глобальных пандемий в инфицированной популяции.

От состояния восприимчивости к заражению
<math>S=\beta\left(\frac 1 N \right)</math>

Формула выше описывает «силу» инфекции для каждой восприимчивой единицы в заражённой популяции, где <math>\beta</math> эквивалентно скорости распространения болезни.

Для отслеживания изменений этой восприимчивой единицы в заражённой популяции:

<math>\Delta S=\beta \times S {1\over N} \, \Delta t</math>
От заражения к выздоровлению
<math>\Delta I=\mu I \, \Delta t</math>

Со временем число таких заражений зависит от заданной скорости выздоровления, представленной числом <math>\mu</math>, но за средний период заражения <math>{1\over \tau}</math>, от числа заражённых лиц <math>I</math> и от числа изменений за время <math>\Delta t</math>.

Контагиозный период

Поражена ли популяция пандемией, с позиции SIR-модели, зависит от значения <math>R_0</math> или «среднего числа заражённых людей от других людей».

<math>R_0=\beta\tau={\beta\over\mu}</math>

Анализ Web-ссылок

Некоторые алгоритмы ранжирования поисковых систем используют основанные на ссылках меры центральности, включая (в порядке появления) алгоритмы Шаблон:Не переведено 5 Шаблон:Не переведено 5, PageRank компании Google, Алгоритм HITS Клейнберга, Шаблон:Не переведено 5 и Шаблон:Не переведено 5. Анализ связей может осуществляться в теории информации, чтобы понять и выделить информацию из набора веб-страниц. Например, это может быть анализ связей между сайтами или блогами политиков.

PageRank

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

Каждый узел <math>x_i</math> имеет PageRank, определённый как сумма для страниц <math>j</math> обратных величин числа страниц, связанных с узлом <math>i</math> исходящими дугами, или «полустепень исхода» узла <math>j</math> на «важность» или PageRank узла <math>j</math>.

<math>x_i=\sum_{j\rightarrow i}{1\over N_j}x_j^{(k)}</math>
Случайные переходы

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

Улучшение вышеприведённой формулы для определения PageRank включает компоненты этих случайных переходов. Без случайных переходов некоторые страницы получат PageRank, равный 0, что не есть хорошо.

Первой компонентой является <math>\alpha</math>, или вероятность, что случайный переход случится. Противоположным является «коэффициент затухания», или <math>1 - \alpha</math>.

<math>R{(p)}={\alpha\over N} + (1 - \alpha) \sum_{j\rightarrow i} {1\over N_j} x_j^{(k)}</math>

Другой угол зрения на это:

<math>R(A)=\sum {R_B\over B_\text{(outlinks)}} + \cdots + {R_n \over n_\text{(outlinks)}}</math>

Меры центральности

Информация об относительной важности узлов и рёбер в графах может быть получена через меры центральности, широко используемые в дисциплинах, таких как социология. Меры центральности необходимы, когда сетевой анализ не имеет ответа на вопросы, такие как: «Какие узлы в сети следует задействовать, чтобы обеспечить, чтобы сообщение или информация распространялась на все или большинстве узлов сети?» или, наоборот, «На какие узлы следует воздействовать, чтобы остановить распространение болезни?». Формально определёнными мерами центральности являются степень связности, степень близости, степень посредничества, степень влиятельности и центральность по Кацу. Цель анализа сети обычно предопределяет используемый тип мер(ы) центральностиШаблон:Sfn.

  • Степень связности узла сети — это число связей (вершин), инцидентных узлу.
  • Степень близости определяет, насколько «близок» узел сети другим узлам путём суммирования кратчайших расстояний (геодезических путей) между этим узлом и остальными узлами сети.
  • Степень посредничества определяет относительную важность узла путём измерения величины потока, протекающего через этот узел к другим узлам в сети. Это делается путём измерения доли путей, соединяющих все пары узлов и содержащих рассматриваемый узел. Групповая степень посредничества измеряет величину потока, протекающего через группу узловШаблон:Sfn.
  • Степень влиятельности является более сложной версией степени центральности, когда центральность узла не только зависит от числа связей, инцидентных узлу, но и от качества этих связей. Этот множитель качества определяется собственными векторами матрицы смежности сети.
  • Центральность по Кацу узла измеряется путём суммирования геодезических (то есть кратчайших) путей между этим узлом и всеми (достижимыми) узлами сети. Эти пути взвешены, пути, соединяющие узел с его непосредственными соседями, имеют более тяжёлые веса, чем узлы, которые связаны с более удалёнными узлами.

Распространение контента в сетях

Контент в сложной сети может распространяться двумя главными способами: сохраняющееся распространение и несохраняющееся распространениеШаблон:Sfn. При сохраняющемся распространении общее количество контента, входящего в сложные сети, остаётся постоянной при проходе через сеть. Модель сохраняющегося распространения может быть лучше всего представлена кувшином, содержащим определённое количество воды, которая выливается в ряд стоков, соединённых трубами. Здесь кувшин представляет источник, а вода представляет распространяемый контент. Ёмкости и соединяющие трубы представляют узлы и связи узлов соответственно. При переходе воды от одной ёмкости в другую вода исчезает из ёмкости-источника. В несохраняющемся распространении количество контента меняется по мере прохождения через сложные сети. Модель несохраняющегося распространения лучше всего можно представить непрерывной струёй из водопроводного крана, растекающейся по стокам, соединённых трубами. Здесь количество воды из начального источника не ограничено. Также любой сток, до которого вода дошла, продолжает получать воду, даже если она проходит к другим стокам. Несохраняющиеся модели наиболее пригодны для объяснения передачи большинства инфекций.

SIR-модель

В 1927 году В. О. Кермак и А. Г. Маккендрик создали модель, в которой они рассматривают фиксированную популяцию всего с тремя состояниями — восприимчив, <math>S(t)</math>, заражён, <math>I(t)</math>, и вылечен, <math>R(t)</math>. Категории, используемые в этой модели, состоят из трёх классов:

  • <math>S(t)</math> используется для представления числа лиц, ещё не заражённых болезнью в момент времени t (восприимчивых к болезни)
  • <math>I(t)</math> означает число заражённых лиц, которые способны передавать болезнь лицам, находящимися в категории «восприимчивые»
  • <math>R(t)</math> является категорией лиц, перенёсших болезнь и вылечившихся. Лица этой категории, не способные заразиться повторно или передать инфекцию другим лицам.

Течение этой модели можно рассматривать следующим образом:

<math>\mathcal{S} \rightarrow \mathcal{I} \rightarrow \mathcal{R} </math>

Используя фиксированную популяцию, <math>N=S(t) + I(t) + R(t)</math>, Кермак и Маккендрик вывели следующие уравнения:

<math>

\begin{align} \frac{dS}{dt} &=- \beta S I \\[8pt] \frac{dI}{dt} &=\beta S I - \gamma I \\[8pt] \frac{dR}{dt} &=\gamma I \end{align} </math>

Для формулирования этих уравнений были сделаны некоторые предположения. Для первого уравнения отдельный представитель популяции должен рассматриваться как имеющий такую же вероятность заражения, как и любой другой представитель, со скоростью <math>\beta</math>, которая рассматривается как скорость распространения инфекции или болезни. Поэтому, когда заражённый представитель вступает в контакт и способен к передаче болезни <math>\beta N</math> другим представителям за единицу времени и доля контактов заражённых представителей с восприимчивыми равна <math>S/N</math>. Число новых инфекций за единицу времени на одного заражённого тогда равно <math>\beta N (S/N)</math>, что задаёт скорость новых заражений s (или тех, кто покидает категорию восприимчивых) как <math>\beta N (S/N)I=\beta SI</math>Шаблон:Sfn. Для второго и третьего уравнений считается, что популяция покидает класс восприимчивых с той же скоростью, что и входит в класс заражённых. Однако число равно доле (<math>\gamma</math> представляет среднюю скорость выздоровления, а <math>1/\gamma</math> представляет среднее время болезни) заражённых, покидающих этот класс в единицу времени и переходящих в класс выздоровевших. Об этих происходящих одновременно процессах говорят как о законе действующих масс, широко распространённая идея, что скорость контактов между двумя группами в популяции пропорциональна размеру каждой из двух рассматриваемых группШаблон:Sfn. Наконец, предполагается, что скорость заражения и выздоровления много больше, чем рождение и умирание, а потому эти факторы в модели не учитываются.

Больше об этой модели можно прочесть на странице Шаблон:Не переведено 5.

Метод основного уравнения

Основное уравнение может выразить поведение неориентированной растущей сети, в которой на каждом шаге добавляется новый узел, соединённый со старым узлом (случайно выбранным и без преференций). Начальную сеть составляют два узла и две связи между ними в момент <math>t=2</math>. Такая конфигурация необходима только для упрощения дальнейших вычислений, так что в момент времени <math>t=n</math> сеть имеет <math>n</math> узлов и <math>n</math> связей.

Основное кинетическое уравнение для этой сети

<math>p(k,s,t+1)=\frac 1 t p(k-1,s,t) + \left(1 - \frac 1 t \right)p(k,s,t),</math>

где <math>p(k,s,t)</math> равно вероятности иметь узел <math>s</math> со степенью <math>k</math> в момент времени <math>t+1</math>, а <math>s</math> является временем, когда узел был добавлен в сеть. Заметим, что имеется только два способа для старого узла <math>s</math> иметь <math>k</math> соединений в момент <math>t+1</math>:

  • Узел <math>s</math> имеет степень <math>k-1</math> в момент <math>t</math> и будет связан с новым узлом с вероятностью <math>1/t</math>
  • Уже имеет степень <math>k</math> в момент <math>t</math> и не будет соединён с новым узлом.

После упрощения этой модели распределение узлов по числу связей будет равно <math>P(k)=2^{-k}</math>Шаблон:Sfn.

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

<math>p_r(k,s,t)=r_t \frac 1 t p_r(k-1,s,t) + \left(1 - \frac 1 t \right) p_r(k,s,t),</math>

где <math>r_t</math> определяет заражение (<math>r_t=1</math>) или отсутствие заражения (<math>r_t=0</math>). После решения этого основного уравнения получаем следующее решение: <math>\tilde{P}_r(k)=\left(\frac r 2 \right)^k. </math>Шаблон:Sfn.

Взаимозависимые сети

Шаблон:Основная статья Взаимозависимая сеть — это система связанных сетей, в которых узлы одной или более сетей зависят от узлов других сетей. Такие зависимости расширены разработками в современных технологиях. Зависимости могут привести к каскадным повреждениям между сетями и относительно малые повреждения могут привести к катастрофичным разрушениям системы. Отключения электричества являются восхитительной демонстрацией важности роли, которую играют связи сетей. Недавно была развита концепция изучения каскадных нарушений в системе взаимозависимых сетейШаблон:SfnШаблон:Sfn.

Многослойные сети

Шаблон:Основная статья

Многослойные сети — это сети с несколькими видами связейШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Возрастающие изощрённые попытки смоделировать системы реального мира как многосвязные сети дали ценные знания в области анализа социальной сетиШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn, экономике, историиШаблон:Sfn, городском и международном транспортеШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn, экологииШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn, психологииШаблон:Sfn, медицине, биологииШаблон:Sfn, коммерции, климатологии, физикеШаблон:SfnШаблон:Sfn, нейроинформатикеШаблон:Sfn Шаблон:SfnШаблон:Sfn, управлении операциями с финансах.

Оптимизация сети

Сетевые задачи, которые используют поиск оптимального пути в каких-либо целях, изучаются под названием комбинаторной оптимизации. Примеры включают потоки в сети, задачу о кратчайшем пути, транспортную задачу, Шаблон:Не переведено 5, задачу о размещении объектов, задачу о паросочетаниях, задачу о назначениях, задачу упаковки, задачу маршрутизации, метод критического пути и PERT (метод оценки и анализа проектов).


Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Литература для дальнейшего чтения

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Книга Шаблон:Wayback
  2. ↑ Шаблон:Статья
  3. ↑ Шаблон:Cite news
  4. ↑ http://psycnet.apa.org/journals/prs/9/4/172/
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Наука_о_сетях&oldid=10446658