Сетевые структуры с нетривиальной топологией

Введение

Сеть с нетривиальными топологическими особенностями

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

Определение

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

Most social, biological, and technological networks display substantial non trivial topological features, with patterns of connection between their elements that are neither purely regular nor purely random. Such features include a heavy tail in the degree distribution, a high clustering coefficient, assortativity or disassortativity among vertices, community structure, and hierarchical structure. In the case of directed networks these features also include reciprocity, triad significance profile and other features. In contrast, many of the mathematical models of networks that have been studied in the past, such as lattices and random graphs, do not show these features. The most complex structures can be realized by networks with a medium number of interactions. This corresponds to the fact that the maximum information content (entropy) is obtained for medium probabilities. Two well known and much studied classes of complex networks are scale free networks and small world networks, whose discovery and definition are canonical case studies in the field. Both are characterized by specific structural features—power law degree distributions for the former and short path lengths and high clustering for the latter. However, as the study of complex networks has continued to grow in importance and popularity, many other aspects of network structures have attracted attention as well. The field continues to develop at a brisk pace, and has brought together researchers from many areas including mathematics, physics, electric power systems, biology, climate, computer science, sociology, epidemiology, and others. Ideas and tools from network science and engineering have been applied to the analysis of metabolic and genetic regulatory networks; the study of ecosystem stability and robustness; clinical science; the modeling and design of scalable communication networks such as the generation and visualization of complex wireless networks; and a broad range of other practical issues. Network science is the topic of many conferences in a variety of different fields, and has been the subject of numerous books both for the lay person and for the expert.

Сети без масштаба

Сеть называется безмасштабной, если ее распределение степеней, то есть вероятность того, что случайно выбранный узел имеет определенное количество связей (степень), подчиняется математической функции, называемой степенным законом. Степенной закон подразумевает, что распределение степеней в таких сетях не имеет характерного масштаба. В отличие от этого, сети с одним четко определенным масштабом в некоторой степени похожи на решетку, поскольку каждый узел имеет (приблизительно) одинаковую степень. Примеры сетей с одним масштабом включают случайный граф Эрдеша — Реньи (ER), случайные регулярные графы, регулярные решетки и гиперкубы. Некоторые модели растущих сетей, которые генерируют безмасштабные распределения степеней, — это модель Барабаши — Альберта и модель пригодности. В сети с безмасштабным распределением степеней некоторые вершины имеют степень, которая на порядки величины превышает среднюю; эти вершины часто называют «узлами» (хабами), хотя эта терминология вводит в заблуждение, поскольку по определению не существует присущего порога, выше которого узел можно считать хабом. Если бы такой порог существовал, сеть не была бы безмасштабной. Интерес к безмасштабным сетям возник в конце 1990-х годов после сообщений об обнаружении степенных законов распределения степеней в реальных сетях, таких как Всемирная паутина, сеть автономных систем (AS), некоторые сети интернет-маршрутизаторов, сети взаимодействия белков, сети электронной почты и т. д. Большинство из этих заявленных «степенных законов» не выдерживают строгой статистической проверки, но более общая идея о распределениях степеней с «тяжелым хвостом» — которые многие из этих сетей действительно демонстрируют (до проявления эффектов конечного размера) — сильно отличается от того, что можно было бы ожидать, если бы ребра существовали независимо и случайно (то есть подчинялись распределению Пуассона). Существует множество различных способов построить сеть со степенным законом распределения степеней. Процесс Юла является каноническим генеративным процессом для степенных законов и известен с 1925 года. Однако он известен под многими другими названиями из-за его частых переоткрытий, например, принцип Гибрата Герберта А. Саймона, эффект Мэтью, кумулятивное преимущество и преференциальное присоединение Барабаши и Альберта для распределений степеней по степенному закону. Недавно гиперболические геометрические графы были предложены как еще один способ построения безмасштабных сетей. Некоторые сети со степенным законом распределения степеней (и определенными другими типами структуры) могут быть очень устойчивы к случайному удалению вершин, то есть подавляющее большинство вершин остаются связанными вместе в гигантской компоненте. Такие сети также могут быть очень чувствительны к целенаправленным атакам, направленным на быстрое разрушение сети. Когда граф однородно случайен, за исключением распределения степеней, эти критические вершины — это вершины с наивысшей степенью, и они были вовлечены в распространение болезней (естественных и искусственных) в социальных и коммуникационных сетях, а также в распространение модных тенденций (оба из которых моделируются процессом просачивания или ветвления). В то время как случайные графы (ER) имеют среднее расстояние порядка log N.

A network is called scale free if its degree distribution, i. e., the probability that a node selected uniformly at random has a certain number of links (degree), follows a mathematical function called a power law. The power law implies that the degree distribution of these networks has no characteristic scale. In contrast, networks with a single well defined scale are somewhat similar to a lattice in that every node has (roughly) the same degree. Examples of networks with a single scale include the Erdős–Rényi (ER) random graph, random regular graphs, regular lattices, and hypercubes. Some models of growing networks that produce scale invariant degree distributions are the Barabási–Albert model and the fitness model. In a network with a scale free degree distribution, some vertices have a degree that is orders of magnitude larger than the average these vertices are often called "hubs", although this language is misleading as, by definition, there is no inherent threshold above which a node can be viewed as a hub. If there were such a threshold, the network would not be scale free. Interest in scale free networks began in the late 1990s with the reporting of discoveries of power law degree distributions in real world networks such as the World Wide Web, the network of Autonomous systems (ASs), some networks of Internet routers, protein interaction networks, email networks, etc. Most of these reported "power laws" fail when challenged with rigorous statistical testing, but the more general idea of heavy tailed degree distributions—which many of these networks do genuinely exhibit (before finite size effects occur) are very different from what one would expect if edges existed independently and at random (i. e., if they followed a Poisson distribution). There are many different ways to build a network with a power law degree distribution. The Yule process is a canonical generative process for power laws, and has been known since 1925. However, it is known by many other names due to its frequent reinvention, e. g., The Gibrat principle by Herbert A. Simon, the Matthew effect, cumulative advantage and, preferential attachment by Barabási and Albert for power law degree distributions. Recently, Hyperbolic Geometric Graphs have been suggested as yet another way of constructing scale free networks. Some networks with a power law degree distribution (and specific other types of structure) can be highly resistant to the random deletion of vertices—i. e., the vast majority of vertices remain connected together in a giant component. Such networks can also be quite sensitive to targeted attacks aimed at fracturing the network quickly. When the graph is uniformly random except for the degree distribution, these critical vertices are the ones with the highest degree, and have thus been implicated in the spread of disease (natural and artificial) in social and communication networks, and in the spread of fads (both of which are modeled by a percolation or branching process). While random graphs (ER) have an average distance of order log N

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

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