Beyond algebraic connectivity of graphs – evaluation of topology, based on spectral clustering
Mircho Mirchev
This paper presents a method for graph topology evaluation based on the Spectral graph theory, which is based on the analysis of Eigen values and Eigen vectors of the graph matrices. When doing Spectral graph analysis, the first is to calculate the Eigen values and Eigen vectors of the Laplacian matrix of the graph, which gives the important value λ2 –the algebraic connectivity of a graph and the Fiedler vector. This vector has values for each node of the graph. On the base of this analysis, a variant of adding a new edge, which gives the highest gain in the algebraic connectivity, is made. Based on this works, a system for automated analysis of graphs and self-learning algorithm for graph analysis and optimization can be made.
В тази разработка е представен метод за оценка на топологията на графи посредством спектралната теория на графите. Тази теория се занимава с анализ на Айген стойностите и векторите на характеристичните матрици на графите. Спектралният анализ на един граф, включва изчисление Айген стойностите и Айген векторите на Лапласовата матрица на графа, откъдето се вижда значението на λ2 – алгебричната свързаност на графа, както и на вектора на Фидлер, като има съпоставка между неговите елементи и върховете на графа. На база на този анализ, може да се направи предположение за вариант за добавяне на ново ребро в граф, което да дава най-голямо повишение на алгебричната свързаност на графа. Въз основа на работата може да се автоматизира процеса на анализ, както и да се направи самообучаващ се алгоритъм за анализ и подобряване на свързаността на графите.
Cite this article as:
Mirchev M. J. Beyond algebraic connectivity of graphs – evaluation of topology, based on spectral clustering. Journal – Electrotechnica & Electronica (Е+Е), Vol. 51 (9-10), 2016, pp. 11-16, ISSN: 0861-4717 (Print), 2603-5421 (Online)
