Фрактальное измерение в сетях - Fractal dimension on networks

Сетевая наука
Теория
График Комплексная сеть Заражение Маленький мир Без накипи Структура сообщества Перколяция Эволюция Управляемость Рисование графика Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Предпочтительная привязанность Теория баланса Сетевой эффект Влияние общества
Типы сетей
Информационная (вычислительная) Телекоммуникации Транспорт Социальное Научное сотрудничество Биологические Искусственный нейрон Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Дорожка Вершина Список смежности  / матрица Список заболеваемости  / матрица Типы Двудольный Полный Режиссер Гипер Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Близость Близость PageRank Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдеш – Реньи Барабаши – Альберт Фитнес модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Максимальная энтропия Мягкая конфигурация Тест LFR Динамика Логическая сеть агент на основе Эпидемия /СЭР
Списки Категории
Темы Программного обеспечения Сетевые ученые Категория: Теория сетей Категория: Теория графов

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

Самоподобие сложных сетей

Многие реальные сети обладают двумя фундаментальными свойствами: безмасштабный собственность и маленький мир свойство. Если распределение степеней сети следует за сила закона, сеть немасштабируемая; если любые два произвольных узла в сети могут быть соединены за очень небольшое количество шагов, сеть называется малым миром.

Свойства маленького мира могут быть математически выражены медленным увеличением среднего диаметр сети, с общим количеством узлов ${ displaystyle N}$,

${ displaystyle left langle l right rangle sim ln {N}}$

куда ${ displaystyle l}$ - кратчайшее расстояние между двумя узлами.

Эквивалентно получаем:

${ displaystyle N sim e ^ { left langle l right rangle / l_ {0}}}$

куда ${ displaystyle l_ {0}}$ - характерная длина.

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

Однако анализ множества реальных сложных сетей показывает, что они самоподобны во всех масштабах длины, вывод, полученный в результате измерения степенной зависимости между количеством ящиков, необходимых для покрытия сети, и размером ящика, так называемого фрактал масштабирование.^[1]

Самоподобие было обнаружено на доступных для растворителя участках поверхности белки.^[2][3] Поскольку белки образуют глобулярные сложенный цепочки, это открытие имеет важное значение для эволюция белка и динамика белка, поскольку его можно использовать для установления характерных динамических масштабов длины для функциональности белка.^[4]

Методы расчета размерности

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

Рисунок 1) Подсчет коробок метод.

Рис. (2) Кластерный метод выращивания.

Метод подсчета коробок

Позволять ${ displaystyle N_ {B}}$ быть количеством ящиков линейного размера ${ displaystyle l_ {B}}$, необходимых для покрытия данной сети. В фрактальная размерность ${ displaystyle d_ {B}}$ тогда дается

${ displaystyle N_ {B} sim l_ {B} ^ {- d_ {B}}}$

Это означает, что среднее количество вершин ${ displaystyle left langle M_ {B} left (l_ {B} right) right rangle}$ в коробке размера ${ displaystyle l_ {B}}$

${ displaystyle left langle M_ {B} left (l_ {B} right) right rangle sim l_ {B} ^ {d_ {B}}}$

Измеряя распределение ${ displaystyle N}$ для коробок разных размеров или путем измерения распределения ${ displaystyle left langle M_ {B} left (l_ {B} right) right rangle}$ для коробок разных размеров фрактальная размерность ${ displaystyle d_ {B}}$ может быть получен степенной аппроксимацией распределения.

Кластерный метод выращивания

Один начальный узел выбирается случайным образом. Если минимальное расстояние ${ displaystyle l}$ задан кластер узлов, разделенных не более чем на ${ displaystyle l}$ из семенного узла могут быть сформированы. Процедура повторяется, выбирая множество начальных чисел, пока кластеры не охватят всю сеть. Тогда размер ${ displaystyle d_ {f}}$ можно рассчитать по

${ displaystyle left langle M_ {C} right rangle sim l ^ {d_ {f}}}$

куда ${ displaystyle left langle M_ {C} right rangle}$ - средняя масса кластеров, определяемая как среднее количество узлов в кластере.

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

Фрактальное масштабирование в безмасштабных сетях

Подсчет ящиков и перенормировка

Рис. (3) а, Демонстрация подсчет коробок и метод перенормировки для различных ${ displaystyle l_ {B}}$ в образцовой сети. б, Три этапа в схеме перенормировки, применяемой к реальным сетевым данным (WWW).^[1]

Исследовать самоподобие в сетях мы используем подсчет коробок метод и перенормировка. На рис. (3a) показана эта процедура с использованием сети, состоящей из 8 узлов.

Для каждого размера л_B, блоки выбираются случайным образом (как в методе роста кластера) до тех пор, пока сеть не будет покрыта. Блок состоит из узлов, все разделенных расстоянием л < л_B, то есть каждая пара узлов в коробке должна быть разделена минимальными путями не более л_B ссылки. Затем каждый ящик заменяется узлом (перенормировка). Перенормированные узлы соединяются, если между неперенормированными блоками есть хотя бы одна связь. Эта процедура повторяется до тех пор, пока сеть не свернется к одному узлу. Каждый из этих прямоугольников имеет эффективную массу (количество узлов в нем), которую можно использовать, как показано выше, для измерения фрактальной размерности сети. На рис. (3b) перенормировка применяется к сети WWW в три этапа для л_B = 3.

На рис. (5) показана инвариантность распределения степеней п(k) при перенормировке, выполненной как функция размера бокса во всемирной паутине. Сети также инвариантны относительно многократных перенормировок, применяемых для фиксированного размера бокса. л_B. Эта инвариантность предполагает, что сети самоподобный на нескольких масштабах длины.

Рис. (4) Каркас сети.^[5]

Скелет и фрактальное масштабирование

В фрактал Свойства сети можно увидеть в ее базовой древовидной структуре. В этом представлении сеть состоит из скелета и ярлыков. Каркас - это особый тип остовного дерева, состоящий из ребер, имеющих наивысший промежуточные центральности, а остальные ребра в сети являются сокращениями. Если исходная сеть не имеет масштабов, то ее скелет также следует степенному распределению степеней, где степень может отличаться от степени исходной сети. Для фрактал сети после фрактального масштабирования, каждый каркас показывает фрактальное масштабирование, аналогичное исходной сети. Количество ящиков, покрывающих каркас, почти такое же, как количество, необходимое для покрытия сети.^[5]

Реальные фрактальные сети

Рис. (5) Инвариантность распределения степеней WWW при перенормировке для различных размеров ящика.^[1]

Рис. (6) Анализ фрактального масштабирования сети WWW. Красный - исходная сеть, синий - скелет, а оранжевый - случайное остовное дерево.^[6]

Поскольку фрактальные сети и их скелеты подчиняются соотношению

${ displaystyle left langle M_ {B} left (l_ {B} right) right rangle sim l_ {B} ^ {d_ {B}}}$,

мы можем исследовать, является ли сеть фрактал и что такое фрактальная размерность сети. Например, WWW, человеческий мозг, метаболическая сеть, сеть взаимодействия белков (PIN) ЧАС. sapiensи PIN-код S. cerevisiaeрассматриваются как фрактальные сети. Кроме того, измеренные фрактальные размерности ${ displaystyle d_ {B} = 4.1, { mbox {}} 3.7, { mbox {}} 3.4, { mbox {}} 2.0, { mbox {и}} 1.8}$ для сетей соответственно. С другой стороны, Интернет, сеть акторов и искусственные модели (например, модель BA) не показывают фрактальные свойства.^{[6] [7]}

Другие определения размеров сети

Лучшее определение размера для сложная сеть или же график зависит от приложения. Например, метрический параметр определяется в терминах разрешающего множества для графа. Определения, основанные на свойстве масштабирования "массы", как определено выше, с расстоянием,^[8]или на основе комплексная сетевая дзета-функция^[9] также были изучены.

Для сетей, встроенных в реальное пространство, можно определить размерность, которая характеризует количество узлов, которые могут быть достигнуты при среднем евклидовом расстоянии.^[10]

Рекомендации