Обзор динамической реконструкции сети

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

Эта статья представляет собой реорганизацию статьи «От данных к структуре — динамическая реконструкция сети». В исходном тексте содержится более 70 математических формул, в этой статье будут даны ключевые формулы и связанные с ними ссылки, а также сделана попытка объяснить идеи статьи с точки зрения реального физического смысла. Если вы хотите узнать более подробный процесс вывода формулы, рекомендуется прочитать исходный текст.

оригинал:От данных к структуре — динамическая реконструкция сети

Jizhi Academy также имеет интерпретацию видео в этой статье. Если вам нравится смотреть на видео обучение, вы можете щелкнуть информацию об интерпретации оригинала ? выше или перейти непосредственно, чтобы посмотреть его.От данных к структуре - динамическая реконструкция сети | Книжный клуб автоматического моделирования сложных систем № 3. Логика интерпретации Учителя Чжан Бо (Бай Чу) ясна и проста.

Если вы предпочитаете текстовую версию, вы можете перейти к следующей ?

Предыстория и знакомство с полями

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

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

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

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

Коллективная динамика сетей «маленького мира»

Emergence of scaling in random networks

Exploring complex networks.

А предмет изучения структуры сети по динамике в сети называется动力学网络重构. Некоторые результаты исследований в этом направлении за последние годы перечислены ниже.

Обнаружение причинно-следственных связей в сложных системах: в этой статье используется метод CCM (конвергентное перекрестное сопоставление), в надежде найти «причинно-следственные связи CCM» между переменными.

Detecting Causality in Complex Ecosystems

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

Wisdom of crowds for robust gene network inference

Идентификация и прогнозирование нелинейных сложных динамических систем на основе данных: эта статья посвящена реконструкции сети с использованием сжатого зондирования.

Data based identification and prediction of nonlinear and complex dynamical systems

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

Model-free inference of direct network interactions from nonlinear collective dynamics

Сети физического взаимодействия, выявленные коллективной статистикой динамики

Revealing physical interaction networks from statistics of collective dynamics

Для получения дополнительной литературы, связанной с динамической реконструкцией, вы можете обратиться к книге, написанной г-ном Чжан Цзяном.Литература по реконструкции сложных сетевых динамических системНа этом пути статья раскрывает общий контекст области реконструкции динамических систем, а также содержит большое количество литературы.

Значение

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

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

Кроме того, изучение динамической реконфигурации имеет и важное теоретическое значение, поскольку изучение реконфигурации на самом деле сталкивается со многими трудностями:

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

Это алгоритм реконструкции в условиях небольшого объема данных и разреженной сети.

Reconstructing the topology of sparsely connected dynamical networks

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

A synthetic oscillatory network of transcriptional regulators

Scaling of noisy fluctuations in complex networks and applications to network prediction

Noise bridges dynamical correlation and topology in coupled oscillator networks

Нелинейность сетевой динамики. Перед лицом линейных систем мы можем справиться с ними с помощью существующих математических и статистических методов, но если кинетика нелинейна, это значительно увеличивает сложность задач.
отсутствующие данные. Будут некоторые данные, которые трудно получить (скрытые узлы), и эти узлы так же важны, как и измеримые узлы во всей сети.

Ниже приведены некоторые соответствующие литературные источники, в которых изучается проблема недостающих данных.Inferring topologies of complex networks with hidden variables

Detecting hidden nodes in complex networks from time series

Uncovering hidden nodes in complex networks in the presence of noise

В этой статье представлен набор общих решений вышеупомянутых четырех общих теоретических проблем.

Проблема динамической реконфигурации сети

В статье описывается множество практических систем со следующей динамической сетью (уравнение 1 будет неоднократно появляться ниже, обратите внимание):

公式1：\frac{dx(t)}{dt} = F(x(t)) + \Gamma(t)

в x(t) Это состояние узла в разное время, которое может быть вектором (один узел) или матрица (n узлов)

F(x(t)) динамика, описывающая себя и взаимодействия

F(x(t)) = (F_1(x(t)), F_2(x(t)), · · · , F_N(x(t)))

$\Gamma(t)$ шумовое воздействие каждого узла (в этой статье рассматривается простой аддитивный белый шум)

\Gamma(t) = (\Gamma_1(t), \Gamma_2(t), · · · , \Gamma_N (t))

Проблема реконфигурации сети заключается в том,При условии знания выходных данных некоторых узлов постарайтесь как можно больше раскрыть скрытую структурную информацию внутри неизвестной сети.. известен $x(t)^M = (x_{i1} (t), x_{i2} (t), · · · , x_iM (t)), M \ll N$ , решать $F_i(x(t)),Q_{ij}$ в $i, j = 1, 2, \dotsm , M$

Как мы упоминали выше, общие трудности в задачах реконструкции сети можно отразить в уравнении 1:

Размер сети может быть большим, т.е. $N\gg1$ , взаимодействие между узлами будет очень сложным.
шум вездесущ и $\Gamma_i(t)$ скорее всего, неизвестны даже его статистические характеристики $\hat{Q}$ Также часто неизвестно
$F_i(x(t)) обычно нелинейна и неизвестна
Фактические данные обычно отсутствуют, т.е. $M\ll N$

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

Несмотря на то что公式1Он содержит много трудностей, которые являются общими при реконструкции сети и играют важную роль, однако обсуждение в этой статье все еще основано на многих предположениях, и не охвачены другие не менее важные трудности, такие как:

Предположение о шуме слишком упрощенно, просто аддитивный белый шум (шум с очень коротким временем ассоциации). Если внешний шум должен быть описан цветным шумом (время корреляции не мало по сравнению с динамическим масштабом времени), то приведенная выше формула уже не выполняется.

Depicting network structures from variable data produced by unknown colored-noise driven dynamics

Ситуация, когда функции узла не равны, не рассматривается, но на практике иногда функция узла задерживается

Обсуждение задержки обсуждается в следующей статье и не будет рассматриваться в этой статье.Reverse engineering of complex dynamical networks in the presence of time-delayed interactions based on noisy time series

Reconstruction of ensembles of coupled time-delay systems from time series

Recovery of couplings and parameters of elements in networks of time-delay systems from time series

Реконструкция линейной сети

Математические принципы

Сначала изучается простейший случай уравнения 1. в этой формулеКак отразить результаты сети?

Левая половина приведенной выше формулы представляет собой дифференциальное уравнение, а простейшее линейное приближение справа можно рассматривать какпроизведение постоянной матрицы и последовательности переменных состояния

公式2: \dot{x(t_k)} = \hat{A} x(t) + \Gamma(t'_k),

Свойства уравнения 2 широко обсуждались и обсуждались как фундаментальная проблема статистической физики, и формула, непосредственно связанная с проблемой реконструкции в этой статье, имеет вид $\hat{A}\hat{C} + \hat{C}\hat{A^T} =−\hat{Q},$ , из следующей статьи, которая $\hat{C}$ представляет собой корреляционную матрицу между шумом и структурой сети

Fokker-planck equation

Умножьте эту формулу на 2 вправо x(t)^T , для узла это означает, что собираются характеристики состояния других узлов в текущий момент, и окончательно это уравнение сети можно преобразовать в такую формулу:

公式3:\hat{B} = \hat{A}\hat{C} + <\Gamma(t')x(t)^T>

в формуле $\hat{B}$ и $\hat{C}$ можно рассчитать по наблюдаемым данным с помощью некоторых статистических корреляций, мы можем понять, что $\hat{B}$ и $\hat{C}$ Все можно получить из данных, в статье пойдет речь о том, как восстанавливать в случае шумов $\hat{A}$ . Что касается второго элемента справа, так как предполагается простой шум, его масштаб намного меньше, чем колебания внутри сети, поэтому сигнал не имеет отношения к шумовой статистике в текущий момент,Тогда это долгосрочное среднее наблюдение должно быть 0. эквивалентно $\hat{B} = \hat{A}\hat{C}$ , то можно получить $\hat{A}$ :

Затем мы добавляем состояние эволюции во времени, на этот раз обратно к уравнению 2, за которым следует последнее правильное умножение. x（t_k)^T Разные, на этот раз мы умножаем на право $x(t_{k+1})^T$ , чтобы получить эту формулу.

公式5: \hat{B^+} = \hat{A}\hat{C^+} + <\Gamma(t')x^+(t)^T>

такой же $\hat{B^+}$ и $\hat{C^+}$ можно считать наблюдаемым, и шум здесь $<\Gamma(t')x^+(t)^T>$ ,- это шум текущего сигнала и предыдущего момента, эти два значения не имеют значения, а ожидаемое долгосрочное статистическое значение равно $\hat{Q}$ , то есть уравнение 5 можно записать так:

还是公式5: \hat{B^+} = \hat{A}\hat{C^+} + \hat{Q}

Тот $\hat{A}$ Это только что было получено в уравнении 4, здесь $\hat{Q}$ Мы также можем вычислить его через матрицу:

公式6：\hat{Q} = \hat{B^+} - \hat{A}\hat{C^+} - \hat{B} - \hat{A}\hat{C} = \hat{B^+} - \hat{B}

резюме

Подведите итоги этого модуля. Для простой линейной сети это эквивалентно наличию только ряда наблюдений. X(t) , мы можем рассчитать структуру сети A и статистику шума, влияющую на структуру сети $\hat{Q}$ . должны знать о том,В случае шума различные статистические корреляционные матрицы являются ядром реконструкции сети по измеримым данным, и выбор подходящей корреляционной матрицы является ключом к ключу.

Экспериментальные результаты линейных сетей

На следующем рисунке показан результат эксперимента по моделированию линейной сети с учетом двух групп случайных линейных сетей с количеством узлов N=100. 5% положительных взаимодействий и 5% отрицательных взаимодействий, также принимая во внимание фиксированные силы связи и равномерно распределенные силы связи.

(a) и (c) — проекции двух групп узлов сети на фазовую плоскость.
(б) и (г) используются公式4(попрошайничество $\hat{A}$ ) соответственно восстановить результаты (a) и (c)
(глаза公式6(попрошайничество $\hat{Q}$ ) предполагаемый шум против наземной истины
(е) и (ж) — проекции (е) и результаты реконструкции (ж) узловых данных на фазовую плоскость для сети (в) с 10-кратным увеличением шума
(f) две сетиТочность реконструкции D

D = \sqrt{\frac{\sum_{i=1}^{N}\sum_{j=1}^{N}{(A_{ij} - A'_{ij})}^2}{N^2}}

Эксперименты, цитируемые из литературы

Solving the inverse problem of noise-driven dynamic networks[J]

нелинейная сеть

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

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

Математические принципы

Сначала вернемся公式1

В математической физике и нелинейной науке мы давно знакомы с:Произвольные нелинейные функции могут быть линейно расширены с использованием базисных функций.. Здесь мы можем поставить F_i(x) Эта нелинейная функция линейно разлагается, т. е.

F_i(x) = \displaystyle\sum_{ \mu=1}^{\infty} \hat{\Re}Y(x(t_k))

в Y(x(t_k)) представляет собой набор нелинейных базисных функций (выберите соответствующие базисные функции в соответствии с конкретными знаниями предметной области)

$\hat{\Re}$ является линейной матрицей, которая, конечно, обычно бесконечна, т.е.

Затем снова мы делаем дифференциальную аппроксимацию дискретных измерений слева и получаем уравнение 7.

公式7：\dot{x(t_k)} = \displaystyle\sum_{ \mu=1}^{\infty} \hat{\Re}Y(x(t_k))+ \Gamma(t'_k)

Приведенная выше формула выглядит сложной, но она говорит только об одном: мы выбираем подходящую базисную функцию, основываясь на знании предметной области или других методах, чтобы преобразовать нелинейную динамическую сеть в нелинейную динамическую сеть.线性矩阵и一组线性基函数форма умножения. Тогда мы следующий, просто решить это线性矩阵 $\hat{\Re}$ , что эквивалентно получению структуры сети.

Идея решения аналогична линейной сети в уравнении 7.умножить вправоСостояние узла в текущий момент x(t_k) , тот же член шума равен 0, и, наконец, можно получить следующую формулу:

в $\hat{B}$ и $\hat{C}$ Все элементы в могут быть вычислены из данных в явном виде, но в отличие от линейной сети, здесь все они бесконечномерны, поэтому в процессе работы необходимо принять аппроксимацию усечения, как выполнять усечение, в статье не приводится унифицированная В теории необходимо выбрать усечение, достаточно маленькое, но отвечающее требованиям реконструкции в соответствии с практическими проблемами и опытом.

После усеченного приближения уравнение 8 разрешимо:

На данный момент процесс реконструкции нелинейной сети завершен.

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

Эксперименты, цитируемые из литературы

Reconstruction of noise-driven nonlinear networks from node outputs by using high-order correlations

Отсутствующие данные

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

Однако на практике многие ситуации не так идеальны, и часто бывают случаи, когда данные отсутствуют. Так можем ли мы восстановить структуру сети в условиях отсутствия данных?

可能存在未知节点：x(t)^M = (x_{i_1}(t), x_{i_2}(t), \dots, x_{i_M}(t)); M \leq N

В этой проблемной статье также дается решение:空间不够，时间来补

Математические принципы

существуетНомер временного ряда узлаНа самом деле он содержит огромное количество информации.

x_i(t_1) =x_i(t_1),x_i(t_2),\dots,x_i(t_L); N;i = 1, 2, \dots,N;L\gg 1

Мы можем пройти через эти временные ряды,Дополнить данные.

Эту идею можно сформулировать в следующих ключевых положениях:

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

x_{i_\mu}^{(\gamma)}(t_k) = \frac{x_{i_\mu}^{(\gamma - 1)}(t_{k+1}) - x_{i_\mu}^{(\gamma - 1)}(t_{k-1})}{\Delta t}

здесь $\gamma$ порядок вывода, здесь предполагается, что он принят до тех пор, покашаг, $\mu$ представляет текущий узел, предполагая, что есть M известных узлов.

2. Мы считаем, что исходные данные и производные данные каждого заказа содержат независимую информацию.. Таким образом, это означает, что у нас будет больше «известных данных».Первоначально были данные только M узлов, но теперь есть данные vM. В этом случае просто убедитесь vM > N , то уравнение можно решить.

\begin{cases} (x_{i_1}(t), x_{i_2}(t), \dots, x_{i_M}(t))\\ (x_{i_1}^{(1)}(t), x_{i_2}^{(1)}(t), \dots, x_{i_M}^{(1)}(t))\\ \vdots\\ (x_{i_1}^{(\gamma)}(t), x_{i_2}^{(\gamma)}(t), \dots, x_{i_M}^{(\gamma)}(t))\\ \vdots\\ (x_{i_1}^{(v)}(t), x_{i_2}^{(v)}(t), \dots, x_{i_M}^{(v)}(t)) \end{cases}

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

Конечно, это также имеет свою цену.Если вы напрямую используете приведенную выше формулу для ее решения, вы на самом деле обнаружите, что окончательный результат реконструкции не очень хорош, потому что, когда мы выполняем дифференцирование высокого порядка, шум данных также автор здесь представил простой метод, где D(t) да $\Omega$ Данные измерений в окне, благодаря этому методу совместного сглаживания, реконструкция, наконец, достигает желаемого эффекта.

\bar{D}(t_k) = \frac{1}{\Omega}\sum_{l=1}^{\Omega}D(t_{k+l-1})

Результаты эксперимента с отсутствующими данными

(a) - временной ряд одного узла в сети
(б) и (в) — эффекты реконструкции без сглаживания и после сглаживания
(d) — эффект реконструкции после увеличения количества узлов

Эксперименты, приведенные в литературе:Reconstruction of noise-driven nonlinear dynamic networks with some hidden nodes[J]

«Локальная реконструкция» с использованием шума

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

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

Частичная реконструкция на самом деле довольно сложна, особенно когда сетевая система закрыта.

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

(c) На рисунке показано, что если к узлу A применить определенный внешний привод, то влияние A на другие узлы может быть выделено среди многих неизвестных эффектов.
(d) Если управляющее воздействие узла А значительно усиливает влияние А на В, что проявляется во многих скрытых эффектах, в этом случае можно сделать вывод о влиянии А на В, только получив данные двух узлов. , А и Б. эффект.

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

В исходном тексте есть длинный список формул, доказывающих осуществимость этой идеи. Здесь он подробно не указан.

Полный текст резюме

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

Следует подчеркнуть три основных момента:

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

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