Наука о сетях — научная область, которая изучает комплексные сети, такие как коммуникационные, компьютерные, биологические, когнитивные и семантические сети, а также социальные сети, и рассматривает различные элементы или участников процесса, представленных узлами (или вершинами), и связи между элементами или участниками, представленные связями (или рёбрами). Эта научная область заимствует теории и методы из теории графов, статистической механики, интеллектуального анализа данных и визуализации информации из информатики, моделирование логического вывода из статистики и социальную структуру из социологии. определяет науку о сетях как «изучение сетевых представлений физических, биологических и социальных явлений, ведущее к прогнозирующим моделям этих явлений».
Предпосылки и история
С изучением сетей сталкивались в различных дисциплинах и использовали эту модель как средство анализа сложных и связанных данных. Наиболее ранняя статья из этой области — знаменитая статья о семи кёнигсбергских мостах, написанная Леонардом Эйлером в 1736 году. Математическое описание вершин и рёбер Эйлером стало основой теории графов — области математики, которая изучает свойства попарных связей в сетевой структуре. Теория графов развивалась и нашла применение в химии.
Денеш Кёниг, венгерский профессор математики, написал в 1936 году первую книгу по теории графов, озаглавленную «Теория конечных и бесконечных графов». В 1930-х годах Якоб Леви Морено, психолог, работающий в традициях гештальтпсихологии, прибыл в США. Он разработал социограмму и представил её публике в апреле 1933 года на съезде студентов-медиков. Морено утверждал, что «до изобретения социометрии никто не знал, как выглядит в точности межличностная структура группы». Социограмма была представлением социальной структуры группы учеников начальной школы. Мальчишки дружили с мальчишками, а девочки — с другими девочками, лишь с одним исключением: один из мальчиков сказал, что ему нравится одна девочка, но чувство не было обоюдным. Сетевое представление социальной структуры произвело такое сильное впечатление, что о нем написали в газете The New York Times. Социограмме нашли множество применений, на ее основе сформулировали подходы к анализу социальных сетей.
Применение теории вероятности в науке о сетях развивалось как ответвление теории графов в виде восьми знаменитых статей Пала Эрдёша и Альфреда Реньи о случайных графах. Для социальных сетей или p* является замечательной основой, используемой для представления пространства вероятностных связей, появляющихся в социальной сети. Альтернативным подходом к вероятностным сетевым структурам является , которая моделирует вероятность рёбер, возникающих в сети, основываясь на историческом присутствии или отсутствии ребра в возникающих сетях.
В 1998 Дэвид Крэкхард и Кэтлин Карли представили идею метасети с моделью PCANS. Они предположили, что «все организации структурированы в трёх направлениях, Физические лица, Задачи и Ресурсы». Их статья ввела концепцию, что сети возникают по различным направлениям, а потому они взаимосвязаны. Эта область выросла в другую подобласть науки о сетях, которая называется .
Позднее другие научные усилия были сфокусированы на математическом описании различных сетевых топологий. Дункан Ваттс совместил данные на сетях с математическим представлением, описывающим граф «Мир тесен». Альберт-Ласло Барабаши и разработали масштабно-инвариантую сеть, которая в общих чертах определяет сетевую топологию, которая содержит узловые вершины (хабы) со множеством соединений, количество которых растёт, сохраняя постоянное отношение числа соединений по отношению к числу всех узлов. Хотя многие сети, такие как интернет, оказываются сохраняющими это отношение, другие сети имеют длинные хвосты распределения узлов, которые лишь приближённо сохраняют масштабную инвариантность.
Инициативы Министерства обороны
Военные силы США первыми (в 1996 году) заинтересовались в сетецентрической войне как концепции военных действий, основанных на науке о сетях. Джон А. Парментола, руководитель научно-исследовательского центра и лабораторий армии США (), провозгласил на армейском совете по науке и технике () 1 декабря 2003 года, что наука о сетях становится новой областью исследований в армии. BAST, отдел инженерно-технических и физических наук () Национального совета по исследованиям () государственной академии наук, наделена полномочиями организации обсуждений научных и технологических актуальных вопросов для армии и осуществления надзора за независимыми связанными с армией изучениями, проводимыми академией наук. BAST проводит изучение, может ли помочь определение рамок и финансирование новой области, науки о сетях, закрыть разрыв между потребностями осуществления сетецентрических операций и текущим примитивным состоянием фундаментальных знаний о сетях.
Как результат BAST выпустил в 2005 исследовательскую работу NRC, озаглавленную «Наука о сетях», в которой определяется новая область основных исследований в науке о сетях для армии. Основываясь на полученных в этой работе результатах и рекомендациях и на последующем отчёте NRC 2007 года, озаглавленном «Стратегия для армейских центров науки о сетях, технологии и экспериментов», основные армейские исследовательские ресурсы были перенаправлены на инициализацию новых главных исследовательских программ в науке о сетях. Чтобы построить новые теоретические основы для комплексных сетей, поддерживаются некоторые новые ключевые моменты исследования науки о сетях, адресованные армейским лабораториям:
Математические модели поведения сетей для предсказания производительности по размеру, сложности сети и окружению. Оптимизированная производительность людей, требуемая для сетевой войны. Организация сетей в экосистемах и в ячейках на молекулярном уровне.
С подачи в 2004 году Фредерика И. Моксли и при поддержке Дэвида С. Альбертса Министерства обороны помогло создать первый Центр Науки о сетях () совместно с военной академией () армии США. Под руководством Моксли и сотрудников USMA были созданы междисциплинарные студенческие курсы науки о сетях для курсантов Вест-Пойнт. Для лучшего внедрения основных положений науки о сетях среди будущих лидеров USMA основали также курс из пяти дисциплин.
В 2006 году армия США и Великобритания (UK) сформировали () по Сетевой и Информационной Науке (), совместное партнёрство Армейской Исследовательской лаборатории, Министерства Обороны Великобритании и консорциум индустрии и университетов в США и Великобритании. Целью альянса является осуществление исследований в поддержке сетецентрических операций в интересах обеих наций.
В 2009 году армия США сформировала , альянс по совместным исследованиям , и консорциума 30 промышленных исследовательских центров США. Целью альянса является разработка глубокого понимания общих черт переплетающихся социальных/когнитивных, информационных и коммуникационных сетей, а как результат, улучшение нашей возможности анализировать, предсказывать, разрабатывать и влиять на сложные переплетающиеся системы сетей многих видов.
Затем, как результат этих усилий, министерство обороны США спонсировал многочисленные исследовательские проекты, поддерживающие науку о сетях.
Свойства сетей Часто сети имеют некоторые атрибуты, которые могут быть вычислены для анализа свойств и характеристик сети. Поведение этих свойств сетей часто определяют сетевые модели и они могут быть использованы для анализа, чем отличаются одни модели от других. Многие определения для других терминов, используемых в науке о сетях, можно найти в статье «Глоссарий теории графов».
Размер Под размером сети может пониматься число узлов или, реже, число рёбер , которое (для связных графов без кратных рёбер) может меняться от (дерево) до (полный граф). В случае простого графа (сеть, в которой существует максимум одно (неориентированное) ребро между любой парой вершин и в которой ни одна из вершин не соединена сама с собой), мы имеем . Для ориентированных графов (без петель) . Для ориентированных графов с разрешёнными петлями . Для случая графа, в котором разрешены кратные рёбра между парой вершин .
Плотность Плотность сети с узлами определяется как отношение числа рёбер к числу возможных рёбер в сети и задаётся (в случае простых графов) биномиальным коэффициентом , что даёт
Другое возможное уравнение — где связи неориентированныhttp://psycnet.apa.org/journals/prs/9/4/172/. Это даёт лучшее понимание плотности сети, поскольку неориентированные связи могут быть измерены.
Планарная сетевая плотность Плотность сети , в которой нет пересечений рёбер, определяется как отношение числа рёбер к числу максимальному числу рёбер в сети с узлами без пересекающихся рёбер , что даёт
Средняя степень узла Степень узла — это число рёбер, связанных с ним. Тесно связана с плотностью сети средняя плотность, (или, в случае ориентированных графов, . Множитель 2 в предыдущем равенстве возникает из того, что каждое ребро в неориентированном графе делает вклад в степени двух различных вершин). В модели случайного графа Эрдёша — Реньи () мы можем вычислить ожидаемое значение (равно ожидаемому значению произвольной вершины) — случайная вершина имеет возможных других вершин с вероятностью соединения . Тогда .
Средняя длина кратчайшего пути (или характеристика длины пути) Средняя длина кратчайшего пути вычисляется путём нахождения кратчайшего пути между всеми парами узлов и вычисления средней длины по всем путям (длиной является число рёбер, содержащихся в пути, то есть расстояние между двумя вершинами в графе). Это показывает нам, в среднем, число шагов, которые нужно сделать от одного узла сети до другого. Поведение математического ожидания средней длины кратчайшего пути как функции числа вершин модели случайной сети определяет, отражает ли модель эффект малого мира. Если она ведёт себя как , модель генерирует модель сетей малого мира. При росте большем логарифмического модель не даёт «малый мир». Специальный случай роста известен как эффект ультрамалого мира.
Диаметр сети Как другое средство измерения сетевых графов мы можем определить диаметр сети как самый длинный из вычисленных кратчайших путей в сети. Это кратчайшее расстояние между двумя наиболее удалёнными друг от друга узлами сети. Другими словами, после того, как вычислена длина кратчайшего пути из каждого узла во все другие узлы, диаметр является самым длинным из всех вычисленных длин путей. Диаметр является представлением линейного размера сети.
Коэффициент кластеризации Коэффициент кластеризации является мерой свойства «все мои друзья знают друг друга». Это иногда описывается как «друзья моего друга — мои друзья». Более точно, коэффициент кластеризации узла равен отношению существующих связей, соединяющих соседей узла друг с другом, к максимальному числу таких связей. Коэффициент кластеризации всей сети равен среднему коэффициентов кластеризации всех узлов. Высокий коэффициент кластеризации для сети является другим признаком тесного мира.
Коэффициент кластеризации -ого узла равен
где равно числу соседей -го узла, а равно числу связей между этими соседями. Максимальное число возможных связей между соседями равно, тогда,
С точки зрения теории вероятности ожидаемый локальный коэффициент кластеризации равен вероятности существования связи между двумя произвольно выбранными соседями одного узла.
Связанность Способ, каким сеть связана, играет большую роль в анализе и интерпретации сети. Сети классифицируются на четыре категории: Клика/Полный Граф — полностью связанная сеть, в которой каждый узел связан с каждым другим узлом. Эти сети симметричны, поскольку все узлы имеют входящие соединения от всех других узлов и исходящие соединения во все остальные узлы. Гигантская компонента — одна связная компонента содержит большинство узлов сети. Слабо связанная компонента — набор узлов, в котором существует путь из любого узла в любой другой без учёта направления рёбер.