Геометрия данных 1. Симплексы и графы

2017-09-29 в 15:16, admin, рубрики: граф, Дистанционная матрица, лапласиан, математика, метрический тензор, симплекс

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

Геометрия данных 1. Симплексы и графы - 1

Введение

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

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

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

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

Покажем преобразования ди- и би-координат — изменение базиса. В дистанционных координатах смена базовых вершин одновременно означает определение новых дистанций между точками пространства. Такой процесс имеет прикладное значение, например, в задачах локализации сенсоров (определения их координат на основе некоторых базисных).

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

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

Поехали!

Дистанционная матрица

Пусть у нас есть множество, состоящее из n элементов. Элементами могут быть геометрическая точка в пространстве, узел графа, буква, слово, документ, человек и т.д., — практически любой объект. Допустим далее, что известна степень близости элементов набора. Для точек в пространстве степенью близости является квадрат расстояния между ними. Для электрической цепи сопротивлений степень близости равна эффективному сопротивлению между узлами сети. В физике мера близости между двумя событиями именуется интервалом. Мы объединим все эти термины под общим названием — дистанция, которую обозначим как $d(A,B)$ — это дистанция между элементами $A$ и $B$ .

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

$d(A,B)=d_{AB}=d^{1}_{AB}+d^{2}_{AB}+...quad(1.1)$

Верхним индексом обозначен номер компоненты.

Набор точек с известными дистанциями между ними будем называть симплексом. На рисунке показан прямоугольный треугольник (2-мерный симплекс) с катетами 3, 4 и гипотенузой 5. Его дистанционная матрица имеет вид:
begin{array}{c | c c c}
D_{ABC} & A & B & C \
hline
A & 0 & 9 & 16 \
B & 9 & 0 & 25 \
C & 16 & 25 & 0 \
end{array}
Точно такая же матрица будет описывать сопротивление между узлами электрической цепи из двух последовательно соединенных резисторов (показаны на рисунке). В теории графов ее принято называть матрицей сопротивлений (resistance distance matrix).

Очевидно, что симплекс в трехмерном пространстве определяется 4-мя вершинами (тетраэдр), в двумерном — 3-мя и т.д., — мерность пространства симплекса на 1 меньше количества его вершин.

Векторное окаймление матриц

Дистанционная матрица симплекса $D$ не подходит для роли метрического тензора хотя бы потому, что ее определитель не связан с объемом симплекса (в примере — с площадью треугольника). Однако еще в 19-м веке A.Cayley (Кэли) обнаружил, что если расширить (окаймить) дистанционную матрицу вектором из единиц, то определитель полученной матрицы будет пропорционален квадрату объема симплекса. Полученную таким образом матрицу называют матрицей Кэли-Менгера.

Определим операцию окаймления $Edge$ симметричных матриц $M$ вектором $vec{v}$ и скаляром $c$ :

$Edge(M,vec{v},c)=begin{pmatrix} c&v'\ 'v&M\ end{pmatrix}quad(1.2)$

Об обозначении векторов штрихами

Здесь и далее мы используем штрих справа от вектора для обозначения вектора-строки $v'$

и слева от вектора для обозначения вектора-столбца $'v$

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

Скалярное произведение векторов (результат — скаляр) — это два внутренних штриха ( $a' 'b$ ), внешнее произведение (результат — матрица, диада) — два внешних штриха ( $'a b'$ ), точечное произведение (результат — вектор) — оба штриха с одной стороны ( $'a 'b$ или $a' b'$ ).

Если матрица $A=Edge(B,..)$ является окаймлением матрицы $B$ , то $B$ является подматрицей $A$ и называется главным (угловым) минором $A$ .

Дистанционный метрический тензор (ДМТ)

Математики (J.C.Gower) также заметили, что удобнее оперировать не с самими дистанциями между точками, а с отрицательными полудистанциями $d2$ :

$d2_{AB}=-d_{AB}/2, space D2=-D/2quad(1.3)$

Знак минус нужен, чтобы избавиться в выражениях от множителей типа $(-1)^n$ , а множитель «1/2» позволяет избавиться от степеней двойки.

Дистанционный метрический тензор $Dm$ определяется как окаймление вектором из единиц полудистанционной матрицы $D2$ :

$Dm=Edge(D,vec{1},0)=begin{pmatrix} 0&1'\ '1&D2\ end{pmatrix}quad(1.4)$

Для нашего симплекса из трех точек (прямоугольного треугольника) дистанционный метрический тензор будет иметь вид:
begin{array}{c | c c c c}
Dm & * & A & B & C \
hline
* & 0 & 1 & 1 & 1 \
A & 1 & 0 & -4.5 & -8 \
B & 1 & -4.5 & 0 & -12.5 \
C & 1 & -8 & -12.5 & 0 \
end{array}
В тензорной форме записи дистанционный тензор будем обозначать нижними индексами:

$g_{ij} equiv Dmquad(1.5)$

Мы используем ту же букву ( $g_{ij}$ ), которой принято обозначать обычный (векторный) метрический тензор (с точкой начала координат и базисными векторами), чтобы продемонстрировать их аналогию. Но следует иметь ввиду, что размерность дистанционного тензора на два больше размерности векторного при описании пространства одной и той же мерности.

О тензорной и матричной формах записей

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

При матричном способе записи индексами обычно обозначают точки пространства, значения элементов. $M_{ij}$ — это значение матрицы M в i-й строке и j-м столбце, $v_p$ — значение вектора $v$ в точке p.

В тензорной форме назначение индексов — это прежде всего определение типа (и ранга) тензора. Обозначение $v^i$ говорит о том, что речь идет о контравариантных координатах вектора $v$ . При этом буква может означать конкретную точку пространства.

Геометрические свойства ДМТ

Как отмечено выше, определитель метрического тензора $Dm$ связан с объемом симплекса $vol$ . Точная формула:

$(l! space vol)^2=-det(Dm)quad(1.6)$

где $l=n-1$ — мерность пространства, задаваемого симплексом из $n$ вершин.
Вычислим площадь нашего треугольника. Имеем $l=2, det(Dm_{ABC})=-144$ . Тогда $2 space vol=sqrt{144}=12$ , откуда $vol=6$ . Конечно, данную площадь можно было получить и просто перемножением длин катетов $vol=3*4/2$ .

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

$rs=det(D2)/det(Dm)quad(1.7)$

В нашем треугольнике радиус сферы будет равен: $rs=-900/-144=6.25$ .

Лапласовский метрический тензор (ЛМТ)

Известно, что метрические тензоры ходят парами. То есть для заданной метрики всегда есть взаимная, а метрические тензоры взаимных метрик обратны по отношению к друг другу. Обращение дистанционного метрического тензора дает лапласовский метрический тензор (ЛМТ): $Lm equiv g^{ij}$ . Связь тензоров:

в матричной форме $Lm cdot Dm=Equad(1.8)$

и в тензорной $g^{ik} g_{kj}=delta^i_jquad(1.8')$

Почему обратный дистанционный метрический тензор стал лапласовским? Потому что его главным угловым минором (подматрицей) является лапласиан $L$ . Та самая матрица, которой описывают узлы и связи в графе, ее называют также матрицей Кирхгофа. Формула (1.8) связывает свойства симплексов и графов. Можно утверждать, что каждому невырожденному симплексу соответствует какой-либо граф и наоборот. Такая взаимность позволяет сопоставлять геометрические характеристики симплексов с инвариантами графов.

Структура ЛМТ

Важно то, что лапласовский метрический тензор — это не просто лапласиан, а его векторное окаймление. В структуру ЛМТ входят скаляр и вектор — характеристики описанной сферы вокруг вершин симплекса:

$Lm=Edge(L,vec{s},rs)=begin{pmatrix} rs&s'\ 's&L\ end{pmatrix}quad(1.9)$

Здесь скаляр $rs$ — это квадрат радиуса описанной сферы, про который уже упоминалось. Вектор $vec{s}$ — барицентрические координаты центра описанной сферы симплекса.

Барицентрические координаты — это весовые координаты точки относительно базовых (реперов). Базовыми здесь служат вершины симплекса (или графа). Сумма весов равна единице — условие нормировки барицентрических векторов.

Барицентрические координаты центра описанной окружности прямоугольного треугольника всегда одинаковы

И равны $vec{s}=[s_A, s_B, s_C]=[0, 0.5, 0.5]$ .

Это означает, что центр O уравновешивается равными массами в точках B и C.

Вообще говоря для любого графа, представляющего собой цепочку последовательно соединенных звеньев, координаты вектора центра сферы будут отличны от нуля только на крайних узлах и равны 0.5.
Геометрия данных 1. Симплексы и графы - 56

Связь параметров ДМТ и ЛМТ

Раскрывая умножение метрических тензоров (8) по правилам произведения блочных матриц, получаем свойства их составляющих.

$begin{pmatrix} 0&1'\'1&D2end{pmatrix} cdot begin{pmatrix} rs&s'\ 's&Lend{pmatrix}=begin{pmatrix} 1' space 's & 1' space L\ '1 space rs + D2 space 's & '1 s' + D2 space Lend{pmatrix}=begin{pmatrix} 1&0'\ '0 & Eend{pmatrix} quad(1.10)$

Здесь $D2=-D/2$ — полудистанционная матрица, $E$ — единичная матрица. Пришли к 4-м основным тождествам.

Сумма компонент барицентрического вектора центра сферы равна 1:

$ 1' space 's=s' space '1=1 quad(1.10.1)$

Сумма строк (и столбцов) лапласиана равна 0. Или более абстрактно — вектор единиц ( $ vec{1} $ ) является для лапласиана нулевым:

$ 1' space L=0', L space '1='0 quad(1.10.2)$ :

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

$ D2 space 's=-'1 space rs $ , откуда $ s' space D2 space 's=-rs quad(1.10.3)$

Связь полудистанционной матрицы и лапласиана через $vec{s}$ -вектор:

$ D2 space L=E - '1 s' quad(1.10.4)$

Построение дистанционной матрицы по лапласиану

Если мы имеем дело с графом, то для построения дистанционной матрицы на основании матрицы смежности $C$ можно использовать следующий алгоритм. Для матрицы смежности считаем лапласиан:

$L=Diag(C space '1) - C quad(1.11.1)$

.
Здесь $Diag()$ — оператор преобразования вектора в диагональную матрицу.
Определитель лапласиана равен нулю, поэтом его нельзя просто обратить. Надо либо удалить из него какой-то узел, либо дополнить (окаймить) каким-либо вектором.
Здесь рассмотрим второй способ — окаймляем лапласиан вектором из единиц и обращаем полученную матрицу. Главным минором (подматрицей) результата обращения будет матрица Грина $G$ .

$begin{pmatrix} 0&1'\'1&Lend{pmatrix}^{-1}=begin{pmatrix} 0&/n'\ '/n&Gend{pmatrix} quad(1.11.2)$

Матрица Грина относится к грамианам $Gm$ . Из любого грамиана можно построить дистанционную матрицу по формуле (преобразование дистанции):

$D='d_g 1' + '1 d_g' - 2 Gm quad(1.11.3)$

где вектор $vec{d_g}$ — это диагональ грамиана $d_g=diag(Gm)$ .

Геометрия лапласиана

Сопоставим геометрические параметры симплекса с инвариантами и характеристиками графа.

Объем симплекса и потенциал лапласиана

Матричная теорема о деревьях связывает количество остовных деревьев графа с определителем минора лапласиана. В предыдущих статьях мы называли данную величину скалярным потенциалом лапласиана $u$ :

$u(L)=det'(L)=-det(Lm)=-det(Dm)^{-1}=(l! space vol)^{-2}quad(1.12)$

Здесь через $det'(L)$ обозначен псевдодетерминант, то есть детерминант от минора лапласиана (поскольку сам лапласиан — вырожденная матрица).

Видим, что чем меньше количество остовных деревьев графа (проще его структура), тем больше объем соответствующего ему симплекса.

Элементы лапласиана

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

Приведем вид лапласиана для нашего примера:

$L_{ABC}={1 over 144} begin{pmatrix} 25&-16&-9\ -16&16&0\ -9&0&9\ end{pmatrix}.$

Здесь проводимость (вес связи) между узлами A и B равна 16/144, между узлами A и C 9/144, а между узлами B и C связи вообще нет.

Теперь посмотрим на лапласиан симплекса. Каждой вершине симплекса можно сопоставить соответствующую противоположную грань. Под противоположной понимается грань симплекса, которая не касается заданного узла. Очевидно, что в общем случае такая грань является n-мерной. В нашем треугольнике — это сторона (отрезок), противоположная вершине. В тетраэдре — треугольник. Опуская из заданной вершины перпендикуляр на противоположную грань, получаем высоту вершины симплекса. Значение высоты вершины $h_i$ выражается через площадь грани $f_i$ , противоположной вершине, объем симплекса $vol$ и мерность его пространства $l=n-1$ :

$h_i=l space vol space /space f_i quad(1.13)$

Здесь $f_i$ — площадь грани, противоположной i-ой вершине симплекса. Элементы лапласиана симплекса можно теперь выразить через высоты вершин. Диагональные элементы лапласиана обратно пропорциональны высотам вершин:

$L_{ii}=1 / h_i^2 quad(1.14.1)$

Чем больше высота вершины симплекса — тем меньше проводимость соответствующего узла графа. Недиагональные элементы пропорциональны косинусу угла между гранями симплекса $cos_{ij}$ :

$L_{ij}=-cos_{ij} / (h_i h_j) quad(1.14.2)$

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

Описанная сфера и связность графа

Радиус описанной сферы $rs$ является естественной характеристикой симплекса. Соответственно, данный параметр должен иметь отражение в инвариантах графа.

Величина, обратная радиусу сферы симплекса $rs$ — является подходящей характеристикой общей связности графа. Назовем данную связность геометрической и обозначим как $chi$ . Тогда

$chi=1/rs quad(1.15)$

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

Значения геометрической связности в различных топологиях графа

Для полного графа (все узлы связаны со всеми) с одной и той же силой связи $c$

выражение для связности в зависимости от количества узлов графа $n$

имеет следующий вид:

$chi_{max}(n)=c (n + frac{1}{n-2}) quad(1.16.1)$

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

Формула (1.16.1) выражает максимальное значение связности для заданного количества узлов. Минимальной является связность разомкнутой цепочки или звезды — граф с одной компонентой связности. Выражение для минимальной связности имеет вид:

$chi_{min}(n)=frac{4c}{n-1} quad(1.16.2)$

Для сравнения приведем также связность замкнутой цепи:

$chi_c(n)=frac{12 n c} {n^2-1} quad(1.16.3)$

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

Если радиус описанной сферы симплекса характеризует связность графа, то барицентрические координаты центра сферы показывают относительную удаленность узлов графа. Величина удаленности узла обратно пропорциональна его связности. Чем менее связан с остальным графом — тем больше значение его удаленности. Поэтому барицентрические координаты центра сферы $vec{s}$ будем также называть вектором удаленности.

Индекс симметричности

Еще один интересный параметр, которым можно характеризовать граф (и симплекс) — это индекс симметричности. Его можно также сформулировать в геометрической терминологии — отношение средней дистанции $ra$ симплекса к радиусу его сферы $rs$ :

$ is=ra/rs=ra cdot chi quad(1.17)$

где $ra=-overline{D2}=-1' space D2 space '1 space/n^2$ .

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

Индекс симметричности можно выразить через дистанцию от центроида симплекса до центра сферы $d_{cs}$ :

$is=1 - d_{cs}/rs quad(1.17')$

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

Пример расчета параметров

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

Геометрия данных 1. Симплексы и графы - 106

Данный граф эквивалентен 6-вершинному симплексу в 5-мерном пространстве. Кружки с цифрами — это пронумерованные узлы графа. Силу связи между узлами (значение веса ребер) принимаем за единицу.

Геометрическая связность данного графа равна 1.663 — это средняя связность на один узел. Можно сравнить ее с максимальной (6.25) и минимальной (0.8) связностью для графа из 6 узлов. Индекс симметричности — 0.773.

Вектор удаленности узлов (барицентрический вектор центра сферы): [0.364, 0.045, 0.273, -0.227, 0.045, 0.500]. Видим, что чем больше узел имеет связей, тем меньше значение его удаленности и наоборот. Интересно отрицательное значение удаленности 4-го узла. Это единственной узел графа, при удалении которого граф распадается на две несвязанные компоненты. Возможно, что отрицательную удаленность имеют ключевые узлы графа.

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

Автор: dmagin

Источник

Информация