Анализ графика мощности - Power graph analysis
В вычислительной биологии , анализ мощности графика представляет собой метод анализа и представление сложных сетей . Анализ графа мощности - это вычисление, анализ и визуальное представление графа мощности из графа ( сетей ).
Анализ графика мощности можно рассматривать как алгоритм сжатия без потерь для графиков. Он расширяет синтаксис графа представлениями клик , бикликов и звезд . Уровни сжатия до 95% были получены для сложных биологических сетей .
Гиперграфы - это обобщение графов, в которых ребра представляют собой не просто пары узлов, а произвольные наборы из n элементов . Графы степеней не являются еще одним обобщением графов, но вместо этого представляют собой новое представление графов, которое предлагает переход от языка «узел и ребро» к языку с использованием клик, бикликов и звезд в качестве примитивов.
Графики мощности
Графическое представление
Графики нарисованы с кругами или точками, которые представляют узлы, и линиями, соединяющими пары узлов, которые представляют ребра . Графы мощности расширяют синтаксис графов с помощью узлов мощности , которые нарисованы в виде круга, охватывающего узлы или другие узлы мощности , и ребер мощности , которые являются линиями между узлами мощности.
Биклики - это два набора узлов с ребром между каждым членом одного набора и каждым членом другого набора. В графе мощности биклика представлена как ребро между двумя узлами мощности.
Клики - это набор узлов с ребром между каждой парой узлов. В графе мощности клика представлена узлом мощности с петлей .
Звезды - это набор узлов с гранью между каждым членом этого набора и одним узлом вне набора. В графе мощности звезда представлена границей мощности между обычным узлом и узлом мощности.
Формальное определение
Учитывая график , где есть множество узлов , и это множество ребер, А мощности график представляет собой график , определенный на множестве мощности в узлах питания , соединенных друг с другом посредством силовых ребер : . Следовательно, степенные графы определены на множестве степеней узлов, а также на множестве степеней ребер графа .
Семантика графов мощности следующая: если два узла мощности соединены ребром мощности, это означает, что все узлы первого узла мощности подключены ко всем узлам второго узла мощности. Точно так же, если силовой узел соединен сам с собой посредством ребра мощности, это означает, что все узлы в силовом узле соединены друг с другом ребрами.
Требуются следующие два условия:
- Условие иерархии силовых узлов: любые два силовых узла либо не пересекаются, либо один включен в другой.
- Условие непересекаемости степенных ребер: существует наложение ребер исходного графа на степенные ребра.
Аналогия с анализом Фурье
Анализ Фурье функции можно рассматривать как переписывание функции в терминах гармонических функций вместо пар. Это преобразование меняет точку зрения с временной области на частотную и открывает множество интересных приложений для анализа сигналов , сжатия данных и фильтрации. Точно так же Power Graph Analysis - это переписывание или разложение сети с использованием бикликов, клик и звезд в качестве примитивных элементов (точно так же, как гармонические функции для анализа Фурье). Его можно использовать для анализа, сжатия и фильтрации сетей. Однако есть несколько ключевых отличий. Во-первых, в анализе Фурье два пространства (временная и частотная области) являются одним и тем же функциональным пространством, но строго говоря, графики мощности не являются графиками. Во-вторых, не существует уникального графа мощности, представляющего данный граф. Тем не менее, очень интересным классом графов мощности являются графы минимальной мощности, которые имеют наименьшее количество ребер мощности и узлов мощности, необходимых для представления данного графа.
Графики минимальной мощности
В общем, не существует единственного графа минимальной мощности для данного графа. В этом примере (справа) граф из четырех узлов и пяти ребер допускает два графа минимальной мощности, по два ребра мощности в каждом. Основное различие между этими двумя графами минимальной мощности заключается в более высоком уровне вложенности второго графа мощности, а также в потере симметрии относительно нижележащего графа. Потеря симметрии - проблема только в маленьких игрушечных примерах, поскольку сложные сети вообще редко демонстрируют такую симметрию. Кроме того, можно минимизировать уровень вложенности, но даже тогда, как правило, не существует уникального графа минимальной мощности для минимального уровня вложенности.
Жадный алгоритм графика мощности
Жадный алгоритм степенного графа использует два простых шага для выполнения разложения:
На первом этапе идентифицируются возможные узлы мощности посредством иерархической кластеризации узлов в сети на основе сходства их соседних узлов. Сходство двух наборов соседей принимается за индекс Жаккара этих двух наборов.
На втором этапе выполняется жадный поиск возможных фронтов мощности между узлами-кандидатами. Степенные ребра, абстрагирующие большинство ребер в исходной сети, сначала добавляются к графу мощности. Таким образом, биклики, клики и звезды постепенно заменяются степенными ребрами, пока не будут добавлены все оставшиеся одиночные ребра. Узлы-кандидаты мощности, которые не являются конечной точкой какого-либо фронта мощности, игнорируются.
Модульная декомпозиция
Модульная декомпозиция может использоваться для вычисления графа мощности с помощью сильных модулей модульной декомпозиции. Модули в модульной декомпозиции - это группы узлов в графе, которые имеют идентичных соседей. Сильный модуль - это модуль, который не перекрывается с другим модулем. Однако в сложных сетях сильные модули являются скорее исключением, чем правилом. Следовательно, графики мощности, полученные с помощью модульной декомпозиции, далеки от минимальности. Основное различие между модульной декомпозицией и анализом степенного графа заключается в том, что анализ степенного графа акцентируется на декомпозиции графов не только с использованием модулей узлов, но и модулей ребер (клик, бикликов). Действительно, анализ степенного графа можно рассматривать как одновременную кластеризацию без потерь как узлов, так и ребер.
Приложения
Биологические сети
Было показано, что анализ графика мощности полезен для анализа нескольких типов биологических сетей, таких как сети белок-белкового взаимодействия , мотивы связывания домен-пептид, регуляторные сети генов и сети гомологии / паралогии. Также недавно была визуализирована и проанализирована сеть значимых пар болезнь-признак с помощью Power Graphs.
Сжатие сети, новый показатель, полученный из Power Graphs, был предложен в качестве меры качества для сетей взаимодействия белков.
Репозиционирование препарата
Power Graphs также применялись для анализа сетей лекарство-мишень-болезнь для репозиционирования лекарств .
Социальные сети
Power Graphs применялись к крупномасштабным данным в социальных сетях, для анализа сообществ или моделирования типов авторов.