Спектральная раскладка

Спектральный рисунок случайной сети маленького мира .

Для сравнения построен тот же график, что и рисунок весеннего графика .

Спектральная компоновка — это класс алгоритма рисования графов . Макет использует собственные векторы матрицы, такие как матрица Лапласа графа, в качестве декартовых координат вершин графа.

Идея компоновки состоит в том, чтобы вычислить два крупнейших (или наименьших) собственных значения и соответствующие собственные векторы лапласовой матрицы графа, а затем использовать их для фактического размещения узлов.Обычно узлы размещаются в двухмерной плоскости. Вложение в большее количество измерений можно найти, используя больше собственных векторов.В двумерном случае для данного узла, соответствующего строке/столбцу $i$ в (симметричной) матрице Лапласа $L$ графика, $x$ и $y$-координаты – это $i$-ые элементы первого и второго собственных векторов $L$, соответственно.

Ссылки

• Бекман, Брайан (1994), Теория компоновки спектральных графов , Tech. Отчет MSR-TR-94-04, Microsoft Research .
• Корен, Иегуда (2005), «Построение графиков по собственным векторам: теория и практика», Computers & Mathematics with Applications , 49 (11–12): 1867–1888, doi : 10.1016/j.camwa.2004.08.015 , MR   2154691 .