Анализ графика мощности

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

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

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

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

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

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

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

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

Клики — это набор узлов с ребром между каждой парой узлов. В степенном графе клика представлена ​​степенным узлом с циклом .

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

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

Учитывая график $G={\bigl (}{V,E}{\bigr )}$ где $V={\bigl \{}v_{0},\dots ,v_{n}{\bigr \}}$ представляет собой набор узлов и $E\subseteq V\times V$ это набор ребер, степенной граф $G'={\bigl (}{V',E'}{\bigr )}$ это график, определенный на наборе мощности $V'\subseteq {\mathcal {P}}{\bigl (}V{\bigr )}$ силовых узлов, соединенных друг с другом силовыми ребрами : $E'\subseteq V'\times V'$. Следовательно, степенные графы определяются на множестве степеней узлов, а также на множестве степеней ребер графа. $G$.

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

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

• Условие иерархии силовых узлов: Любые два силовых узла либо не пересекаются, либо один входит в другой.
• Условие непересекаемости степенного ребра: существует онто -преобразование ребер исходного графа в степенные ребра.

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

Анализ Фурье функцииможно рассматривать как переписывание функции в терминах гармонических функций вместо $t\mapsto x$ пары. Это преобразование меняет точку зрения во временной области. в частотную область и позволяет реализовать множество интересных приложений в области анализа сигналов , сжатия данных , и фильтрация.Точно так же анализ графа мощности — это переписывание или разложение сети с использованием биклик, клик и звезд.как примитивные элементы (так же, как гармонические функции для анализа Фурье). Его можно использовать для анализа, сжатия и фильтрации сетей.Однако есть несколько ключевых отличий. Во-первых, в анализе Фурье два пространства (временная и частотная области)являются одним и тем же функциональным пространством, но в строгом смысле степенные графики не являются графиками.Во-вторых, не существует уникального степенного графа, представляющего данный граф. И все же очень интересный класс степенных графов. — это минимальные степенные графы , которые имеют наименьшее количество степенных ребер и степенных узлов, необходимых для представления данного графа.

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

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

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

Жадный алгоритм степенного графа

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

На первом этапе идентифицируются кандидаты на энергетические узлы посредством иерархической кластеризации узлов в сети. на основе сходства соседних узлов. Сходство двух наборов соседей принимается за индекс Жаккара. из двух наборов.

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

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

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

Приложения

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

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

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

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

Графики мощности также применялись для анализа сетей «лекарство-мишень-заболевание». для репозиционирования наркотиков .

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

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

См. также

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

Внешние ссылки

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