Этот пример показывает, как использовать Матрицу Лапласа графика, чтобы вычислить вектор Fiedler. Вектор Fiedler может использоваться, чтобы разделить график в два подграфа.
Загрузите набор данных barbellgraph.mat
, который содержит разреженную матрицу смежности и координаты узла графика штанги.
load barbellgraph.mat
Постройте график с помощью пользовательских координат узла xy
.
G = graph(A,'omitselfloops'); p = plot(G,'XData',xy(:,1),'YData',xy(:,2),'Marker','.'); axis equal
Вычислите Матрицу Лапласа графика. Затем вычислите два самых маленьких собственных значения значения и соответствующие собственные вектора с помощью eigs
.
L = laplacian(G);
[V,D] = eigs(L,2,'smallestabs');
Вектор Fiedler является собственным вектором, соответствующим второму самому маленькому собственному значению графика. Самое маленькое собственное значение является нулем, указывая, что график имеет соединенный компонент того. В этом случае второй столбец в V
соответствует второму самому маленькому собственному значению D(2,2)
.
D
D = 2×2
10-3 ×
0.0000 0
0 0.2873
w = V(:,2);
При нахождении вектора Fiedler, использование eigs
масштабируемо к большим графикам, поскольку вычисляется только подмножество собственных значений и собственных векторов, но для меньших графиков одинаково выполнимо преобразовать Матрицу Лапласа в полное устройство хранения данных и использовать eig(full(L))
.
Разделите график в два подграфа с помощью вектора Fiedler w
. Узел присвоен подграфу, если это имеет положительное значение в w
. В противном случае узел присвоен подграфу B. Эта практика называется сокращением знака или нулевым пороговым сокращением. Сокращение знака минимизирует вес сокращения согласно верхним и нижним границам на весе любого нетривиального сокращения графика.
Разделите график с помощью сокращения знака. Подсветите подграф узлов с w>=0
красного цвета и узлов с w<0
черного цвета цвета.
highlight(p,find(w>=0),'NodeColor','r') % subgraph A highlight(p,find(w<0),'NodeColor','k') % subgraph B
Для графика звонка панели этот раздел делит пополам график приятно в два равных набора узлов. Однако сокращение знака не всегда производит сбалансированное сокращение.
Всегда возможно разделить пополам график путем вычисления медианы w
и использования его в качестве порогового значения. Этот раздел называется средним сокращением, и это гарантирует равное количество узлов в каждом подграфе.
Можно использовать медиану, сокращенную первым сдвигом значений в w
медианой:
w_med = w - median(w);
Затем разделите график, входят в систему w_med
. Для графика звонка панели медиана w
близко к нулю, таким образом, два сокращения производят подобные деления пополам.
digraph
| graph
| laplacian
| subgraph