图论 Graph Theory
2022/7/7 6:20:18
本文主要是介绍图论 Graph Theory,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Graph Theory 图论
Laplacian matrix
Categories of graphs:
- directed/undirected.
- homogeneous/heterogeneous.
- static/dynamic. A dynamic graph is a graph whose topology varies with time.
It is a matrix representation of a graph.
It can be used:
(1) to construct low dimentional graph node embeddings.
(2) to find sparsest \(K\) subgraphs of a graph through the \(K\) smallest eigenvalue of its laplacian matrix.
(3) to calculate the number of spanning trees.
(4) ...
Given a simple graph \(G\) with vertices \(V\) , the Laplacian matrix \(L\in\R^{|V|\times |V|}\) of \(G\) is given by
\[L := D-A \], where \(D\) is the degree matrix, which is diagonal with entries \(D_{ii}\) the degree of node \(i\) , and \(A\) is the adjacency matrix. Since \(G\) is a simple graph, \(A\) only contains 1 or 0 and its diagonal elements are all 0s.
(Symmetric) normalized Laplacian matrix
\[L_{\rm sym} := D^{-\frac12}LD^{-\frac12} = I-D^{-\frac12}AD^{-\frac12} \]The elements of \(L_{\rm sym}\) are given by
\[L_{\rm sym}[i,j] := \begin{dcases} 1 & \text{ if } i=j \wedge \deg(i)\ne 0 \\ -\frac{1}{\sqrt{\deg(i)\deg(j)}}& \text{ if } i\ne j \text{ and i is adjacent to j} \\ 0 & \text{ otherwise} \end{dcases} \]Random Walk normalized Laplacian matrix
\[L_{\rm rw}[i,j] := D^{-1}L = I- D^{-1}A \]The elements of \(L_{\rm rw}\) are given by
\[L_{\rm rw}[i,j] := \begin{dcases} 1 & \text{ if } i=j \wedge \deg(i)\ne 0 \\ -\frac{1}{\deg(i)}& \text{ if } i\ne j \text{ and i is adjacent to j} \\ 0 & \text{ otherwise} \end{dcases} \]Properties of Laplacian matrix
- \(\forall \bm x\in \R^{|V|}: \bm x^T L \bm x=\sum_{i,j}^{|V|} A_{ij}\|x_i-x_j\|^2\)
- \(L\) is symmetric, positive semi-definite, diagonally dominant.
- \(L\) is a M-matrix (its off-diagonal entries are non-positive, and the eigenvalues are non-negative ( on real parts for complex numbers).
- The smallest eigenvalue is \(0\) , and the corresponding eigenvector is \(\bm 1\) (all elements are 1s).
- \(L\) has non-negative eigenvalues, \(0\le \lambda_1 \le \lambda_2 \le ... \le \lambda_n\) .
Considerations of Graph Representation Learning
- Permutation Invariance. Permutation invariance means that the function does not depend on the arbitary ordering of the row/columns vectors of the matrix.
where \(P\) is a permutation matrix.
2.
这篇关于图论 Graph Theory的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?