Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Лапласиан графтың екінші ең кіші өзіндік мәні Алгебралық байланыстық (Мирослав Фидлердің есімімен Фидлер өзіндік мәні деп те аталады) – G графтың Лапласиан матрицасының екінші ең кіші өзіндік мәні (қайталама өзіндік мәндер жеке-жеке есептеледі). Бұл өзіндік мән 0-ден үлкен немесе тең болады, егер және тек қана G байланысқан граф болса. Бұл фактінің салдары ретінде, Лапласианның өзіндік мәні ретінде 0 қанша рет пайда болса, графикте де сонша байланысқан компонент болады. Бұл мәннің мөлшері графтың жалпы байланыстылығын көрсетеді. Ол желілердің тұрақтылығы мен синхрондалу қабілетін талдау үшін қолданылған.
Second smallest eigenvalue of a graph Laplacian
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph G is the second smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is. It has been used in analyzing the robustness and synchronizability of networks.
Қасиеттері
Негативті емес салмақтары бар бағытталмаған графтардың алгебралық байланысы, теңсіздік тек қана G байланысқан болса ғана қатаң болады. Дегенмен, алгебралық байланыс жалпы бағытталған графтар үшін теріс болуы мүмкін, тіпті G байланысқан граф болса да. Сонымен қатар, алгебралық байланыстың мәні графтың дәстүрлі (түйін) байланысымен шектеледі. Егер жағымсыз жиек салмақтары бар бағытталған байланысты графтың түйіндерінің саны n және диаметрі D болса, алгебралық байланыстың төменгі шегі , ал шын мәнінде (Брендан Маккейдің нәтижесі бойынша) 6 түйіннен тұратын жоғарыда көрсетілген граф үшін (n=6, D=3) бұл шектер мынадай: 4/18 = 0.222 ≤ алгебралық байланыс ≤ 0.722 ≤ байланыс 1. Дәстүрлі байланыстан өзгеше, алгебралық байланыс түйіндердің санына, сондай-ақ түйіндердің байланысу тәсіліне де байланысты. Кездейсоқ графтарда алгебралық байланыс түйіндердің санымен азаяды және орташа дәрежесімен артады. Алгебралық байланыстың нақты анықтамасы қолданылатын Лапласиан түріне байланысты. Фан Чунг Лапласианның масштабталған нұсқасын пайдалана отырып, кең теорияны жасады, бұл түйіндер санына тәуелділікті жояды, сондықтан шектеулер сәл өзгеше. Курамото моделі сияқты желілердегі синхронизация модельдерінде Лаплас матрицасы табиғи түрде пайда болады, сондықтан алгебралық байланыс желінің синхронизацияға қаншалықты оңай болатынын көрсетеді. Басқа өлшемдер, мысалы орташа қашықтық (сипаттамалық жол ұзындығы) да қолданылуы мүмкін, және шын мәнінде алгебралық байланыс орташа қашықтықтың (кері шамасымен) тығыз байланысты.
The algebraic connectivity of undirected graphs with nonnegative weights, with the inequality being strict if and only if G is connected. However, the algebraic connectivity can be negative for general directed graphs, even if G is a connected graph. Furthermore, the value of the algebraic connectivity is bounded above by the traditional (vertex) connectivity of the graph, If the number of vertices of an undirected connected graph with nonnegative edge weights is n and the diameter is D, the algebraic connectivity is also known to be bounded below by , and in fact (in a result due to Brendan McKay) by For the graph with 6 nodes show above (n=6,D=3) these bound means, 4/18 = 0.222 ≤ algebraic connectivity 0.722 ≤ connectivity 1. Unlike the traditional connectivity, the algebraic connectivity is dependent on the number of vertices, as well as the way in which vertices are connected. In random graphs, the algebraic connectivity decreases with the number of vertices, and increases with the average degree. The exact definition of the algebraic connectivity depends on the type of Laplacian used. Fan Chung has developed an extensive theory using a rescaled version of the Laplacian, eliminating the dependence on the number of vertices, so that the bounds are somewhat different. In models of synchronization on networks, such as the Kuramoto model, the Laplacian matrix arises naturally, so the algebraic connectivity gives an indication of how easily the network will synchronize. Other measures, such as the average distance (characteristic path length) can also be used, and in fact the algebraic connectivity is closely related to the (reciprocal of the) average distance.
Фидлер векторы
Алгебралық байланысқа қатысты алғашқы теорияны Мирослав Фидлер жасады. Оның құрметіне алгебралық байланысқа сәйкес келетін жеке вектор Фидлер векторы деп аталды. Фидлер векторы графты бөлу үшін қолданылады.
The original theory related to algebraic connectivity was produced by Miroslav Fiedler. In his honor the eigenvector associated with the algebraic connectivity has been named the Fiedler vector. The Fiedler vector can be used to partition a graph.
Фидлер векторы арқылы графикті бөлу
Кіріспе бөлімдегі мысал граф үшін Фидлер векторы мынадай: Теріс мәндер нашар байланысқан 6-шы төбе және оның көршілес бөліну нүктесі, 4-ші төбемен байланысты, ал оң мәндер қалған төбелермен байланысты. Сондықтан Фидлер векторындағы мәндердің таңбаларын осы графты екі компонентке бөлу үшін пайдалануға болады: Әлтернативті түрде, 0,069 мәні (нөлге жақын болғандықтан) жеке класына қойылып, графты үш компонентке бөлуге болады: немесе суретте көрсетілгендей, басқа бөлімге көшіруге болады. Фидлер векторының компоненттерінің квадраттары, вектор нормаланғандықтан бірегейге тең болатындықтан, сәйкес деректер нүктелерінің таңбаға негізделген бөлімге тағайындалу ықтималдығы ретінде қарастырылуы мүмкін.
For the example graph in the introductory section, the Fiedler vector is The negative values are associated with the poorly connected vertex 6, and the neighbouring articulation point, vertex 4; while the positive values are associated with the other vertices. The signs of the values in the Fiedler vector can therefore be used to partition this graph into two components: Alternatively, the value of 0.069 (which is close to zero) can be placed in a class of its own, partitioning the graph into three components: or moved to the other partition , as pictured. The squared values of the components of the Fiedler vector, summing up to one since the vector is normalized, can be interpreted as probabilities of the corresponding data points to be assigned to the sign based partition.