Введение

Изучение графов как представление отношений между дискретными объектами

В математике, информатике и сетевой науке теория сетей является частью теории графов. Она определяет сети как графы, в которых вершины или рёбра обладают атрибутами. Теория сетей анализирует эти сети, рассматривая симметричные или асимметричные отношения между их (дискретными) компонентами. Теория сетей находит применение во многих областях, включая статистическую физику, физику частиц, информатику, электротехнику, археологию, лингвистику, экономику, финансы, исследования операций, климатологию, экологию, здравоохранение, социологию, психологию и нейробиологию. ]]Анализ социальных сетей изучает структуру взаимосвязей между социальными сущностями. Эти сущности часто являются отдельными людьми, но могут также представлять собой группы, организации, национальные государства, веб-сайты или научные публикации. Начиная с 1970-х годов, эмпирическое изучение сетей играет центральную роль в социальных науках, и многие математические и статистические инструменты, используемые для изучения сетей, были впервые разработаны в социологии. Среди множества других применений, анализ социальных сетей использовался для понимания распространения инноваций, новостей и слухов. Аналогично, он применялся для изучения распространения как заболеваний, так и моделей поведения, связанных со здоровьем. Он также используется в изучении рынков, где позволяет исследовать роль доверия в обменных отношениях и социальных механизмов в ценообразовании. Он применялся для изучения вербовки в политические движения, вооруженные группировки и другие социальные организации. Он также использовался для концептуализации научных разногласий и академического авторитета. В последнее время анализ сетей (и его тесно связанная область – анализ трафика) получил широкое распространение в военной разведке для выявления сетей повстанцев как иерархического, так и бесструктурного типа.

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

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

Анализ повествовательной сети

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

Анализ веб-ссылок

Несколько алгоритмов ранжирования веб-поиска используют метрики центральности на основе ссылок, включая PageRank от Google, алгоритм HITS Клейнберга, алгоритмы CheiRank и TrustRank. Анализ ссылок также применяется в информатике и науке о коммуникациях для понимания и извлечения информации из структуры коллекций веб-страниц. Например, такой анализ может проводиться для изучения взаимосвязей между веб-сайтами или блогами политиков. Другая область применения – классификация страниц на основе упоминаний в других страницах.

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

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

Сети повторного использования

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

Пространственные сети

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

Распространение

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

Иммунизация сети

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