Анализ графика мощности - Power graph analysis

В вычислительная биология, анализ графика мощности это метод анализа и представления сложные сети. Анализ графика мощности - это вычисление, анализ и визуальное представление графика мощности от график (сети ).

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

Гиперграфы являются обобщением графов, в которых края не просто пары узлы но произвольно n-кортежи. Графы степеней не являются еще одним обобщением графов, но вместо этого представляют собой новое представление графов, которое предлагает переход от языка «узел и ребро» к языку с использованием клик, бикликов и звезд в качестве примитивов.

Графики мощности

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

Графическое представление

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

Биклики представляют собой два набора узлов с ребром между каждым членом одного набора и каждым членом другого набора. В графе мощности биклика представлена ​​как ребро между двумя узлами мощности.

Клики представляют собой набор узлов с ребром между каждой парой узлов. В графе мощности клика представлена ​​узлом мощности с петля.

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

Формальное определение

Учитывая график ${displaystyle G = {igl (} {V, E} {igr)}}$ куда ${displaystyle V = {igl {} v_ {0}, точки, v_ {n} {igr}}}$ это набор узлов и ${displaystyle Esubseteq V imes V}$ - множество ребер, a график мощности ${displaystyle G '= {igl (} {V', E '} {igr)}}$ это граф, определенный на множестве мощностей ${displaystyle V'subseteq {mathcal {P}} {igl (} V {igr)}}$ из силовые узлы связаны друг с другом край мощности: ${displaystyle E'subseteq V 'imes V'}$. Следовательно, степенные графы определены на набор мощности узлов, а также на набор мощности ребер графа ${displaystyle G}$.

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

Требуются следующие два условия:

• Условие иерархии силовых узлов: любые два силовых узла либо не пересекаются, либо один включен в другой.
• Условие дизъюнкции степенного фронта: существует на отображение от ребер исходного графа к степенным ребрам.^{[нужна цитата ]}

Аналогия с анализом Фурье

В Анализ Фурье функции можно рассматривать как переписывание функции в терминах гармонических функций вместо${displaystyle tmapsto x}$ пары. Это преобразование меняет точку зрения с область временик частотная область и позволяет использовать множество интересных приложений в анализ сигналов, Сжатие данных Аналогично, Power Graph Analysis - это переписывание или разложение сети с использованием бикликов, клик и звезд в качестве примитивных элементов (точно так же, как гармонические функции для анализа Фурье). Его можно использовать для анализа, сжатия и фильтрации сетей, однако есть несколько ключевых отличий. Во-первых, в анализе Фурье два пространства (временная и частотная области) представляют собой одно и то же функциональное пространство, но строго говоря, графики мощности не являются графиками. Во-вторых, не существует уникального графика мощности, представляющего данный граф. Тем не менее, очень интересный класс графиков мощности графики минимальной мощности которые имеют наименьшее количество степенных ребер и мощных узлов, необходимых для представления данного графа.

Графики минимальной мощности

Два разных графика мощности, которые представляют один и тот же график.

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

Жадный алгоритм графика мощности

Жадный алгоритм степенного графа основан на двух простых шагах для выполнения разложения:

В первый шаг определяет возможные узлы мощности через иерархическая кластеризация узлов в сети на основе сходства их соседних узлов. Сходство двух наборов соседей принимается за Индекс Жаккара из двух наборов.

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

Модульная декомпозиция

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

Приложения

Биологические сети

Было показано, что Power Graph Analysis полезен для анализа нескольких типов биологических сетей, таких как Белково-белковое взаимодействие сети,^[2] мотивы, связывающие домен-пептид, Сети регуляции генов^[3] и сети гомологии / паралогии. Также сеть значимых пар болезнь-признак^[4] были недавно визуализированы и проанализированы с помощью Power Graphs.

Сжатие сети, новый показатель, полученный из Power Graphs, был предложен в качестве меры качества для сетей взаимодействия белков.^[5]

Репозиционирование препарата

Power Graphs также применялись для анализа сетей лекарство-мишень-болезнь.^[6] за Репозиционирование препарата.

Социальные сети

Power Graphs были применены к крупномасштабным данным в социальных сетях для майнинга сообществ.^[7] или для моделирования авторских типов.^[8]

Смотрите также

• Вычислительная биология
• Сети /График
• Сложные сети
• Модульная декомпозиция

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

внешняя ссылка

• [1] Инструменты Power Graph Analysis (CyOog v2.8.2) и примеры приложений
• [2] Анализ графика мощности с помощью CyOog v2.6