Наука о сетях - это академическая область, изучающая сложные сети, такие как телекоммуникационные сети, компьютерные сети, биологические сети, когнитивные и семантические сети и социальные сети с учетом отдельных элементов или субъектов, представленных узлами (или вершины) и соединения между элементами или действующими лицами как связи (или ребра). Эта область основана на теориях и методах, включая теорию графов из математики, статистическую механику из физики, интеллектуальный анализ данных и визуализацию информации из компьютерных наук., логическое моделирование из статистики и социальная структура из социологии. Национальный исследовательский совет США определяет сетевую науку как «изучение сетевых представлений о физических, биологических и социальных явлениях, ведущее к прогнозным моделям этих явлений».
Изучение сетей возникло в различных дисциплинах как средство анализа сложных реляционных данных. Самая ранняя известная работа в этой области - знаменитые Семь мостов Кенигсберга, написанные Леонардом Эйлером в 1736 году. Математическое описание вершин и ребер Эйлера было основой теории графов, раздел математики, изучающий свойства парных отношений в сетевой структуре. Область теории графов продолжала развиваться и нашла применение в химии (Sylvester, 1878).
Денес Кениг, венгерский математик и профессор, написал первую книгу по теории графов, озаглавленную «Теория конечных и бесконечных графов», в 1936 году.
Социограмма Морено для учеников первого класса.В 1930-е годы Джейкоб Морено, психолог в гештальт-традиции, прибыл в Соединенные Штаты. Он разработал социограмму и представил ее общественности в апреле 1933 года на съезде ученых-медиков. Морено утверждал, что «до появления социометрии никто не знал, как« в точности »выглядела межличностная структура группы» (Морено, 1953). Социограмма представляла собой социальную структуру группы учеников начальной школы. Мальчики дружили с мальчиками, а девочки дружили с девочками, за исключением одного мальчика, который сказал, что ему нравится одинокая девочка. Чувство не было взаимным. Это сетевое представление социальной структуры было настолько интригующим, что было напечатано в The New York Times (3 апреля 1933 г., стр. 17). Социограмма нашла множество приложений и превратилась в область анализа социальных сетей.
Теория вероятностей в сетевой науке, разработанная как ответвление теории графов с Полом Эрдёшем и Восемь знаменитых работ Альфреда Реньи о случайных графах. Для социальных сетей модель экспоненциального случайного графа или p * представляет собой систему обозначений, используемую для представления вероятностного пространства связи, возникающей в социальной сети. Альтернативный подход к сетевым вероятностным структурам - это матрица сетевой вероятности, которая моделирует вероятность появления ребер в сети на основе исторического наличия или отсутствия ребра в выборке сетей.
В 1998 году Дэвид Кракхардт и Кэтлин Карли представили идею метасети с моделью PCANS. Они предполагают, что «все организации структурированы по этим трем доменам: отдельные лица, задачи и ресурсы». В их статье представлена концепция, согласно которой сети существуют в нескольких доменах и взаимосвязаны. Эта область превратилась в другую дисциплину сетевой науки, называемую динамическим сетевым анализом.
. В последнее время другие усилия сетевой науки были сосредоточены на математическом описании различных сетевых топологий. Дункан Уоттс согласовал эмпирические данные о сетях с математическим представлением, описав сеть малого мира. Альберт-Ласло Барабаши и Река Альберт разработали безмасштабируемую сеть, которая представляет собой слабо определенную топологию сети, которая содержит узловые вершины с множеством соединений, которые растут в способ поддерживать постоянное соотношение количества подключений по сравнению со всеми остальными узлами. Хотя многие сети, такие как Интернет, похоже, поддерживают этот аспект, другие сети имеют длиннохвостые распределения узлов, которые только приблизительно соответствуют свободному от масштаба соотношению.
Военные США впервые заинтересовались сетецентрической войной как оперативной концепцией, основанной на сетевой науке в 1996 году. Джон А. Парментола, Директор по исследованиям и управлению лабораториями армии США 1 декабря 2003 г. предложил Совету по науке и технологиям (BAST) армии США сделать сетевые науки новой областью научных исследований армии. BAST, Отдел инженерных и физических наук Национального исследовательского совета (NRC) национальных академий, служит органом, организующим обсуждение вопросов науки и технологий, важных для армии, и наблюдает за независимыми исследованиями, связанными с армией, проводимыми Национальные академии. BAST провел исследование, чтобы выяснить, может ли выявление и финансирование новой области фундаментальных исследований, сетевой науки, помочь преодолеть разрыв между тем, что необходимо для реализации сетевых операций, и текущим примитивным состоянием фундаментальных знаний о сетях.
В результате BAST в 2005 году опубликовал исследование NRC под названием Network Science (упомянутое выше), которое определило новую область фундаментальных исследований в Network Science для армии. На основании выводов и рекомендаций этого исследования и последующего отчета NRC 2007 года под названием «Стратегия армейского центра сетевых наук, технологий и экспериментов» ресурсы базовых исследований армии были перенаправлены на запуск новой программы фундаментальных исследований в области сетевых наук. Чтобы создать новую теоретическую основу для сложных сетей, некоторые из ключевых исследований в области сетевой науки, которые в настоящее время проводятся в армейских лабораториях, касаются:
По инициативе Фредерика И. Моксли в 2004 году при поддержке, которую он запросил у Дэвида С. Альбертса, Департамента of Defense совместно с Армией США при Военной академии США (USMA) помог создать первый Центр сетевых наук. Под руководством доктора Моксли и преподавателей USMA первые междисциплинарные курсы бакалавриата по сетевым наукам были проведены курсантам в Вест-Пойнте. Чтобы лучше привить принципы сетевой науки своим кадрам будущих лидеров, USMA также учредило пять курсов для студентов-бакалавров по сетевым наукам.
В 2006 году армия США и Соединенное Королевство (Великобритания) сформировали Международный технологический альянс и информационные технологии , совместное партнерство Лаборатории армейских исследований, Министерства обороны Великобритании и консорциум промышленных предприятий и университетов США и Великобритании. Целью альянса является проведение фундаментальных исследований в поддержку сетевых операций с учетом потребностей обеих стран.
В 2009 году армия США сформировала Network Science CTA, совместный исследовательский альянс между Армейской исследовательской лабораторией, CERDEC и консорциум из около 30 промышленных научно-исследовательских лабораторий и университетов в США.Цель альянса состоит в том, чтобы развить глубокое понимание общих черт взаимосвязанных социальных / когнитивных, информационных и коммуникационных сетей и, как результат, улучшить нашу способность анализировать, прогнозировать, проектировать и влиять на сложные системы, переплетая множество видов сетей.
Впоследствии, в результате этих усилий, Министерство обороны США спонсировало многочисленные исследовательские проекты в поддержку сетевой науки.
Часто сети имеют определенные атрибуты, которые можно вычислить для анализа свойств и характеристик сети. Поведение этих сетевых свойств часто определяет сетевые модели и может использоваться для анализа того, как определенные модели контрастируют друг с другом. Многие определения других терминов, используемых в сетевой науке, можно найти в Глоссарии теории графов.
Размер сети может относиться к количеству узлов или, реже, количество ребер , которое (для связанных графов без мультиребер) может варьироваться от (дерево) до (полный график). В случае простого графа (сеть, в которой не более одного (неориентированного) ребра существует между каждой парой вершин и в которой вершины не соединяются между собой), мы имеем ; для ориентированных графов (без самосвязанных узлов) ; для ориентированных графов с разрешенными самосоединениями . В случае графа, в котором между парой вершин может существовать несколько ребер, .
The density сети определяется как отношение количества ребер к количеству возможных ребер в сеть с узлами , заданными (в случае простых графиков) с помощью биномиального коэффициента , что дает Другое возможное уравнение: , тогда как связи являются однонаправленными (Wasserman Faust 1994). Это дает лучший обзор плотности сети, поскольку можно измерить однонаправленные отношения.
Плотность сети, в которой нет пересечения между краями, определяется как отношение количество ребер к количеству возможных ребер в сети с узлами, заданным графом без пересекающихся краев , что дает
Степень узла - это количество ребер, соединенных с ним. С плотностью сети тесно связана средняя степень, (или, в случае ориентированных графов, , первый множитель 2 возникает из каждое ребро в неориентированном графе вносит вклад в степень двух различных вершин). В модели случайного графа ER () мы можем вычислить математическое ожидание (равно ожидаемому значению произвольной вершины): случайная вершина имеет другие вершины в сети доступны и с вероятностью соединяется с каждой из них. Таким образом, .
Средняя длина кратчайшего пути вычисляется путем нахождения кратчайшего пути между всеми парами узлов и взятия среднего значения по всем путям его длина (длина - это количество промежуточных ребер, содержащихся в пути, т. е. расстояние между двумя вершинами внутри графика). Это показывает нам в среднем количество шагов, необходимых для перехода от одного участника сети к другому. Поведение ожидаемой средней длины кратчайшего пути (то есть среднего по ансамблю средней длины кратчайшего пути) в зависимости от количества вершин случайной сети модель определяет, проявляет ли эта модель эффект маленького мира; если он масштабируется как , модель генерирует сети малого мира. Для роста, превышающего логарифмический, модель не создает маленьких миров. Особый случай известен как эффект сверхмалого мира.
Когда ссылки или узлы взвешены, можно рассмотреть оптимальный путь между узлами.
В качестве другого средства Измеряя сетевые графы, мы можем определить диаметр сети как самый длинный из всех вычисленных кратчайших путей в сети. Это кратчайшее расстояние между двумя наиболее удаленными узлами сети. Другими словами, как только вычислена длина кратчайшего пути от каждого узла до всех других узлов, диаметр будет самым длинным из всех рассчитанных длин пути. Диаметр соответствует линейному размеру сети. Если узел ABCD подключен, то при переходе от A->D это будет диаметр 3 (3 участка, 3 связи).
Коэффициент кластеризации является мерой свойство "все мои друзья знают друг друга". Иногда это называют друзьями моих друзей. Точнее, коэффициент кластеризации узла - это отношение существующих связей, соединяющих соседей узла друг с другом, к максимально возможному количеству таких связей. Коэффициент кластеризации для всей сети - это среднее значение коэффициентов кластеризации всех узлов. Высокий коэффициент кластеризации для сети является еще одним признаком маленького мира.
. Коэффициент кластеризации узла равен
где - это количество соседей 'th node, и - количество соединений между этими соседями. Таким образом, максимально возможное количество соединений между соседями равно
С вероятностной точки зрения ожидаемый коэффициент локальной кластеризации - это вероятность ссылки существующий между двумя произвольными соседями одного и того же узла.
Способ подключения сети играет большую роль в том, как сети анализируются и интерпретируются. Сети классифицируются по четырем различным категориям:
Индексы центральности производят ранжирование, которое направлено на определение наиболее важных узлов в сетевой модели. Разные индексы центральности кодируют разные контексты слова «важность». Например, центральность по промежуточности считает узел очень важным, если он образует мосты между многими другими узлами. Центральность по собственным значениям, напротив, считает узел очень важным, если с ним связаны многие другие очень важные узлы. В литературе предложены сотни таких мер.
Индексы центральности точны только для идентификации самых центральных узлов. Эти меры редко, если вообще когда-либо, имеют смысл для остальных узлов сети. Кроме того, их указания точны только в рамках предполагаемого контекста важности и имеют тенденцию «ошибаться» в других контекстах. Например, представьте себе два отдельных сообщества, единственной связью которых является граница между самым младшим членом каждого сообщества. Поскольку любой переход от одного сообщества к другому должен происходить по этой ссылке, два младших члена будут иметь высокую промежуточную центральность. Но, поскольку они младшие (предположительно), у них мало связей с «важными» узлами в своем сообществе, а это означает, что их центральность по собственным значениям будет довольно низкой.
Концепция центральности в контексте статических сетей была расширена на основе эмпирических и теоретических исследований до динамической центральности в контексте временных и временных сетей.
Центральность узлов может быть оценивается методом k-оболочки. Метод k-shell был успешно применен к Интернету, идентифицируя центральный из различных узлов. Считается, что этот метод полезен для выявления влиятельных распространителей в сети.
Ограничения на меры централизации привели к разработке более общих показателей. Двумя примерами являются доступность, в которой используется разнообразие случайных блужданий для измерения доступности остальной части сети с данного начального узла, и ожидаемая сила, полученная из ожидаемого значение силы заражения, генерируемой узлом. Обе эти меры могут быть осмысленно вычислены только на основе структуры сети.
Сетевые модели служат основой для понимания взаимодействий внутри эмпирических сложных сетей. Различные модели генерации случайного графа создают сетевые структуры, которые можно использовать по сравнению с реальными сложными сетями.
Модель Эрдеш-Реньи, названная в честь Пола Эрдеша и Альфред Реньи, используется для создания случайных графов, в которых ребра устанавливаются между узлами с равными вероятностями. Его можно использовать в вероятностном методе для доказательства существования графов, удовлетворяющих различным свойствам, или для обеспечения строгого определения того, что означает выполнение свойства почти для всех графов.
Для создания модели Эрдеша – Реньи необходимо указать два параметра: общее количество узлов n и вероятность p того, что случайная пара узлов имеет ребро.
Поскольку модель генерируется без смещения к конкретным узлам, распределение степеней является биномиальным: для случайно выбранной вершины ,
В этой модели кластеризация коэффициент равен 0 как. Поведение можно разбить на три области.
Подкритический : Все компоненты простые и очень маленькие, самый большой компонент имеет размер ;
критический : ;
сверхкритический : , где - положительное решение уравнения .
Самый большой компонент связности имеет высокую сложность. Все остальные компоненты являются простой и маленький .
Модель конфигурации принимает последовательность степеней или распределение степеней (которое впоследствии используется для генерации последовательности степеней) в качестве входных данных и производит произвольно связанные графы во всех отношениях, кроме последовательности степеней. Это означает, что для данного выбора последовательности степеней выбирается граф равномерно случайным образом из множества всех графов, соответствующих этой последовательности степеней. Степень случайно выбранной вершины является независимой и одинаково распределенной случайной величиной с целыми значениями. Когда , граф конфигурации содержит гигантский компонент связности, имеющий бесконечный размер. Остальные компоненты имеют конечные размеры, которые можно количественно оценить с помощью понятия распределения размеров. Вероятность , что случайно выбранный узел подключен к компоненту размера задается мощностями свертки степени распределение:
где обозначает степень распределения, а . Гигантский компонент может быть уничтожен путем случайного удаления критической части всех ребер. Этот процесс называется перколяцией в случайных сетях. Когда второй момент распределения степеней конечен, , эта критическая доля края определяется как , а среднее расстояние вершина-вершина в гигантском компоненте логарифмически масштабируется с общим размером сети. .В модели направленной конфигурации степень узла задается двумя числами в градусах и степени выхода , и, следовательно,, распределение степеней двумерное. Ожидаемое количество внутренних и внешних ребер совпадает, так что . Модель направленной конфигурации содержит гигантский компонент iff
Обратите внимание, что и равны и, следовательно, взаимозаменяемы в последнем неравенстве. Вероятность того, что случайно выбранная вершина принадлежит компоненту размера , определяется как: для in-components идля компонентов out.
модель Уоттса и Строгаца - это модель генерации случайного графа, которая создает графы с свойствами маленького мира.
Начальная структура решетки используется для создания модели Уоттса – Строгаца. Каждый узел в сети изначально связан со своими ближайшими соседями. Другой параметр задается как вероятность перенаправления. Каждое ребро имеет вероятность , что оно будет преобразовано в граф как случайное ребро. Ожидаемое количество перепрограммированных звеньев в модели равно .
Поскольку модель Уоттса – Строгаца начинается как не- случайная структура решетки, она имеет очень высокий коэффициент кластеризации наряду с высокой средней длиной пути. Каждое повторное подключение может создать ярлык между кластерами с высокой степенью связи. По мере увеличения вероятности повторного подключения коэффициент кластеризации уменьшается медленнее, чем средняя длина пути. Фактически, это позволяет значительно уменьшить среднюю длину пути в сети с незначительным уменьшением коэффициента кластеризации. Более высокие значения p приводят к большему количеству перемонтированных ребер, что фактически делает модель Уоттса – Строгаца случайной сетью.
Модель Барабаши – Альберта - это случайная сетевая модель, используемая для демонстрации предпочтительной привязанности или «богатого-получающего» более богатый »эффект. В этой модели ребро, скорее всего, присоединится к узлам с более высокими степенями. Сеть начинается с начальной сети из m 0 узлов. m 0 ≥ 2, и степень каждого узла в исходной сети должна быть не менее 1, в противном случае он всегда будет оставаться отключенным от остальной сети.
В модели BA новые узлы добавляются в сеть по одному. Каждый новый узел подключается к существующим узлам с вероятностью, которая пропорциональна количеству ссылок, которые уже есть у существующих узлов. Формально вероятность p i того, что новый узел подключен к узлу i, равна
где k i - степень узла i. Сильно связанные узлы («концентраторы») имеют тенденцию быстро накапливать еще больше ссылок, в то время как узлы с небольшим количеством ссылок вряд ли будут выбраны в качестве места назначения для новой ссылки. Новые узлы имеют «предпочтение» присоединяться к уже сильно связанным узлам.
Распределение степеней модели BA, которое следует степенному закону. В логарифмическом масштабе функция степенного закона представляет собой прямую линию.Распределение степеней, полученное на основе модели BA, не масштабируется, в частности, это степенной закон вида:
Концентраторы обладают высокой центральностью между узлами, что позволяет существовать коротким путям между узлами. В результате модель BA имеет тенденцию к очень короткой средней длине пути. Коэффициент кластеризации этой модели также стремится к 0. В то время как диаметр D многих моделей, включая модель случайного графа Эрдеша Реньи и несколько сетей малых миров, пропорционален log N, модель BA показывает D ~ loglogN (ультрамалый мир). Обратите внимание, что средняя длина пути зависит от диаметра N.
В модели подключения, управляемого посредником (MDA), в которой новый узел идет с ребра выбирают существующий связанный узел случайным образом, а затем соединяются не с этим, а с из его соседей, выбранных также случайным образом. Вероятность того, что узел из существующего выбранного узла будет
Фактор - это величина, обратная гармоническому среднему (IHM) степеней соседи узла . Подробные численные исследования показывают, что для примерно среднее значение IHM в большом предельное значение 475 становится константой.>Π (i) ∝ ki {\ displaystyle \ Pi (i) \ propto k_ {i}}. Это означает, что чем выше звенья (степень) у узла, тем выше его шанс получить больше связей, поскольку они могут быть достигнуты большим количеством способов через посредников, что по сути воплощает интуитивную идею механизма обогащения богатых (или правило предпочтительной привязанности модели Барабаши-Альберта). Таким образом, можно видеть, что сеть MDA следует принципу Правило PA, но замаскировано.
Тем не менее, для оно описывает, как победитель получает весь механизм, поскольку мы находим, что почти из все узлы имеют степень один, а один супербогат по степени. По мере того как значение увеличивает неравенство между сверхбогатыми и бедными, уменьшается, и как мы находим переход от богатого к супер-богатому Механизм обогащения - обогащение.
Другая модель, в которой ключевым ингредиентом является природа вершины, была представлена Калдарелли и др. Здесь создается связь между двумя вершинами с вероятностью, заданной функцией связывания из приспособленности задействованных вершин. Степень вершины i определяется как
Если - обратимая и возрастающая функция от , тогда распределение вероятностей определяется выражением
В результате, если пригодности распределяются как степенной закон, то также степень узла.
Менее интуитивно с быстро убывающим распределением вероятностей, как вместе с функцией связывания типа
с константой и функцией Хевисайда., мы также получаем безмасштабные сети.
Такая модель успешно применялась для описания торговли между странами с использованием ВВП как пригодности для различных узлов и связывающей функции вида
Анализ социальных сетей исследует структуру отношений между социальными объектами. Эти организации часто являются людьми, но также могут быть группами, организациями, национальными государствами, веб-сайтами, научными публикациями.
С 1970-х годов эмпирическое исследование сетей играет центральную роль в социальных науках, и многие из математических и статистических инструментов, используемых для изучения сетей, были впервые разработаны в социология. Среди множества других приложений, анализ социальных сетей использовался для понимания распространения инноваций, новостей и слухов. Точно так же он использовался для изучения распространения как болезней, так и поведения, связанного со здоровьем. Он также применялся в исследовании рынков, где он использовался для изучения роли доверия в обменных отношениях и социальных механизмов в установлении цен. Точно так же он использовался для изучения вербовки в политические движения и социальные организации. Он также использовался для концептуализации научных разногласий, а также академического престижа. В последнее время сетевой анализ (и его близкий родственник анализ трафика ) получил широкое применение в военной разведке для выявления повстанческих сетей как иерархического, так и безлидерного характера. В криминологии он используется для выявления влиятельных участников преступных группировок, движений преступников, соучастия в преступлениях, прогнозирования преступной деятельности и разработки политики.
Динамический сетевой анализ исследует изменяющуюся структуру отношений между различными классами сущностей в сложных социотехнических системах, а также отражает социальную стабильность и изменения, такие как появление новых групп, тем и лидеров. Динамический сетевой анализ фокусируется на метасетях, состоящих из нескольких типов узлов (объектов) и нескольких типов ссылок. Эти сущности могут быть самыми разными. Примеры включают людей, организации, темы, ресурсы, задачи, события, места и убеждения.
Динамические сетевые методы особенно полезны для оценки тенденций и изменений в сетях с течением времени, выявления появляющихся лидеров и изучения совместной эволюции людей и идей.
В связи с недавним взрывом общедоступных высокопроизводительных биологических данных, анализ молекулярных сетей вызвал значительный интерес. Тип анализа в этом контенте тесно связан с анализом социальных сетей, но часто фокусируется на локальных моделях в сети. Например, сетевые мотивы - это небольшие подграфы, которые чрезмерно представлены в сети. представляют собой аналогичные избыточно представленные шаблоны в атрибутах узлов и ребер в сети, которые избыточно представлены с учетом сетевой структуры. Анализ биологических сетей привел к разработке сетевой медицины, которая рассматривает влияние болезней в интерактоме.
Анализ связей - это подмножество сетевого анализа, изучающего связи между объектами. Примером может быть проверка адресов подозреваемых и потерпевших, телефонных номеров, которые они набрали, и финансовых транзакций, в которых они участвовали в течение определенного периода времени, а также семейных отношений между этими субъектами в рамках полицейского расследования. Анализ связей здесь обеспечивает важные взаимосвязи и ассоциации между очень многими объектами разных типов, которые не очевидны из отдельных фрагментов информации. Компьютерный или полностью автоматический компьютерный анализ каналов все чаще используется банками и страховыми агентствами при обнаружении мошенничества операторами связи при анализе сетей электросвязи посредством медицинский сектор в эпидемиологии и фармакологии, в правоохранительных расследованиях, в поисковых системах для релевантности рейтинга (и и наоборот, спамерами для спамодексирования и владельцами бизнеса для поисковой оптимизации ), а также везде, где необходимо анализировать отношения между многими объектами.
Структурная устойчивость сетей изучается с помощью теории перколяции. Когда критическая часть узлов удаляется, сеть становится фрагментированной на небольшие кластеры. Это явление называется перколяцией и представляет собой фазовый переход типа порядок-беспорядок с критическими показателями.
Модель SIR является одной из наиболее известных алгоритмов прогнозирования распространения глобальных пандемий среди инфекционной популяции.
Формула выше описывает «сила» инфекции для каждой восприимчивой единицы в заразной популяции, где β эквивалентно скорости передачи указанного заболевания.
Чтобы отслеживать изменение восприимчивых в инфекционной популяции:
Со временем количество зараженных колеблется на : указанная скорость выздоровления, представленная как , но вычтенная до единицы за средний инфекционный период , номер инфекционных особей, , и изменение во времени, .
Будет ли население преодолено пандемией, с точки зрения модели SIR, зависит от значения или «средние люди, инфицированные инфицированным человеком».
Несколько Интернета поиск алгоритмы ранжирования используют метрики центральности на основе ссылок, включая (в порядке появления) Hyper Search, Google <582 Marchiori >PageRank, алгоритм Клейнберга HITS, алгоритмы CheiRank и TrustRank. Анализ ссылок также проводится в области информатики и коммуникаций, чтобы понять и извлечь информацию из структуры коллекций веб-страниц. Например, анализ может касаться взаимосвязи между веб-сайтами политиков или блогами.
PageRank работает путем случайного выбора «узлов» или веб-сайтов, а затем с определенной вероятностью «случайного перехода» к другим узлам. Путем случайного перехода к этим другим узлам он помогает PageRank полностью пройти по сети, поскольку некоторые веб-страницы существуют на периферии и их не так легко оценить.
Каждый узел, , имеет PageRank, определяемый суммой страниц эта ссылка на , умноженная на единицу по исходящим ссылкам, или «степень выхода» из , умноженная на «важность» или PageRank .
Как объяснено выше, PageRank включает случайные скачки в попытках присвоить PageRank каждому веб-сайту в Интернете. Эти случайные переходы позволяют находить веб-сайты, которые могут не быть найдены при использовании обычных методов поиска, таких как поиск в ширину и поиск в глубину.
. Улучшение по сравнению с вышеупомянутой формулой для определения PageRank включает добавление эти случайные компоненты скачка. Без случайных переходов некоторые страницы получили бы PageRank 0, что было бы плохо.
Первый - это , или вероятность того, что произойдет случайный скачок. Контраст - это «коэффициент затухания», или .
Другой способ взглянуть на это:
Информация об относительной важности узлов и ребер в графе можно получить с помощью мер центральности, широко используемых в таких дисциплинах, как социология. Меры централизации важны, когда сетевой анализ должен ответить на такие вопросы, как: «Какие узлы в сети должны быть нацелены, чтобы гарантировать распространение сообщения или информации на все или большинство узлов в сети?» или, наоборот, «Какие узлы следует задействовать, чтобы ограничить распространение болезни?». Формально установленные меры центральности: центральность по степени, центральность по близости, центральность по промежуточности, центральность по собственному вектору и центральность по кацу. Цель сетевого анализа обычно определяет тип используемых мер центральности.
Контент в комплексе сеть может распространяться двумя основными способами: с сохранением распространения и без сохранения распространения. При сохранении распространения общий объем контента, поступающего в сложную сеть, остается постоянным по мере прохождения. Модель консервированного распространения лучше всего можно представить в виде кувшина с фиксированным количеством воды, наливаемого в ряд воронок, соединенных трубками. Здесь кувшин представляет собой первоначальный источник, а вода - это распространяемое содержимое. Воронки и соединительные трубки представляют собой узлы и соединения между узлами соответственно. Когда вода переходит из одной воронки в другую, вода мгновенно исчезает из воронки, которая ранее была подвергнута воздействию воды. При несохраняемом распространении количество контента изменяется по мере того, как оно входит и проходит через сложную сеть. Модель несохраняемого спреда лучше всего можно представить в виде непрерывно работающего крана, проходящего через ряд воронок, соединенных трубками. Здесь количество воды из первоисточника бесконечно. Кроме того, любые воронки, подвергшиеся воздействию воды, продолжают воспринимать воду, даже когда она переходит в последовательные воронки. Неконсервативная модель является наиболее подходящей для объяснения передачи большинства инфекционных заболеваний.
В 1927 году В.О. Кермак и А.Г. Маккендрик создали модель, в которой они рассматривали фиксированную популяцию. только с тремя отсеками, восприимчивые: , заражены, и восстановлено, . Разделы, используемые для этой модели, состоят из трех классов:
Ход этой модели можно рассматривать следующим образом:
Используя фиксированную совокупность, , Кермак и МакКендрик вывели следующие уравнения:
При формулировке этих уравнений было сделано несколько предположений. Считается, что человек в популяции имеет такую же вероятность, как и любой другой человек, заразиться этим заболеванием со скоростью , что считается уровнем контакта или инфицирования болезнь. Следовательно, инфицированный человек вступает в контакт и может передавать болезнь с другими людьми в единицу времени, и доля контактов между инфицированным и восприимчивым человеком составляет . Таким образом, количество новых инфекций в единицу времени на одно инфекционное заболевание составляет , что дает частоту новых инфекций (или оставив уязвимую категорию) как (Brauer Castillo-Chavez, 2001). Применительно ко второму и третьему уравнениям считайте, что популяция, покидающая уязвимый класс, равна числу, попавшему в инфицированный класс. Однако инфекционные вирусы покидают этот класс в единицу времени, чтобы войти в восстановленный / удаленный класс со скоростью в единицу времени (где представляет собой среднюю скорость восстановления или средний период заражения). Эти процессы, которые происходят одновременно, называются Законом массового действия, широко распространенной идеей о том, что скорость контакта между двумя группами в популяции пропорциональна размеру каждой из заинтересованных групп (Daley Гани, 2005). Наконец, предполагается, что скорость инфицирования и выздоровления намного выше, чем временной масштаб рождений и смертей, и поэтому эти факторы в этой модели игнорируются.
Подробнее об этой модели можно прочитать на странице Модель эпидемии.
A главное уравнение может выразить поведение ненаправленной растущей сети, где на каждом временном шаге к сети добавляется новый узел, связанный со старым узлом (случайным образом выбрал и без преференций). Исходная сеть состоит из двух узлов и двух связей между ними в момент времени , эта конфигурация необходима только для упрощения дальнейших вычислений, поэтому во время сеть имеет узлов и ссылки.
Основное уравнение для этой сети:
где - вероятность иметь узел со степенью в момент времени , а - временной шаг, когда этот узел был добавлен в сеть. Обратите внимание, что у старого узла есть только два способа иметь ссылки в момент :
После упрощения этой модели распределение степеней будет
На основе этой растущей сети разрабатывается модель эпидемии, следуя простому правилу: каждый раз при добавлении нового узла и после выбора старого узла для связывания, принимается решение: будет ли этот новый узел заражен. Основное уравнение для этой модели эпидемии:
где представляет решение заразить () или нет (). Решая это основное уравнение, получают следующее решение:
Взаимозависимая сеть - это система связанных сетей, в которой узлы одной или нескольких сетей зависят от узлов в других сетях. Такие зависимости усиливаются развитием современных технологий. Зависимости могут привести к каскадным сбоям между сетями, а относительно небольшой сбой может привести к катастрофическому сбою системы. Блэкауты - это увлекательная демонстрация той важной роли, которую играют зависимости между сетями. Недавнее исследование разработало основу для изучения каскадных отказов во взаимозависимых сетевых системах с использованием теории перколяции. Дополнительное исследование, рассматривающее динамический процесс в сети, направлено на каскадные отказы нагрузки во взаимозависимых сетях. Взаимозависимые инфраструктуры, которые пространственно встроены, были смоделированы как взаимозависимые решетчатые сети, и их устойчивость была проанализирована.] Модель пространственного мультиплексирования была введена Данцигером и др. И была дополнительно проанализирована Вакнином и др.
Многослойные сети - это сети с несколькими видами отношений. Попытки смоделировать реальные системы как многомерные сети использовались в различных областях, таких как анализ социальных сетей, экономика, история, городской и международный транспорт, экология, психология, медицина, биология, коммерция, климатология, физика, вычислительная нейробиология, управление операциями., и финансы.
Сетевые проблемы, связанные с поиском оптимального способа выполнения чего-либо, изучаются под названием комбинаторной оптимизации. Примеры включают сетевой поток, проблему кратчайшего пути, транспортную проблему, проблему перегрузки, проблему местоположения, проблема сопоставления, проблема назначения, проблема упаковки, проблема маршрутизации, анализ критического пути и PERT (Методика оценки и анализа программ).