Graph

Some basic concepts about graph

Graph A graph $\mathcal G$ has nodes $\mathcal V$ and edges $\mathcal E$, $$ \mathcal G = ( \mathcal …

Local Statistics Node Degree Node Degree Node degree of a node $u$ $$ d_u = \sum_{v\in \mathcal V} …

Some basic concepts about graph and traditional algorithms

The Ratio Cut Graph Cuts Cut For a subset of nodes $\mathcal A\subset \mathcal V$, with the rest of …

Node Classification Given graph that has incomplete attribute labeling of the nodes, predict the …

mind the data structure: here comes the graph

The Katz index is $$ \mathbf S_{\text{Katz}}[u,v] = \sum_{i=1}^\infty \beta^i \mathbf A^i[u, v], $$ …

From Katz Index to LHN Index Katz Index Graph Global Overlap Measure: Katz Index The Katz index is …

Random Walk Construct a stochastic transfer matrix $P$ by normalizing the adjacency matrix $\mathbf …

For two graphs, $\mathcal G$ and $\mathcal H$, the two graphs are isomorphism on the following …

The Adamic Adar (AA) index is1 $$ \mathbf S_{\text{AA}}[v_1,v_2] = \sum_{u\in\mathcal N(u) \cap …

The Resource Allocation (RA) index is $$ \mathbf S_{\text{RA}}[v_1,v_2] = \sum_{u\in\mathcal N(u) …

The Salton index is $$ \mathbf S_{\text{Salton}}[u,v] = \frac{ 2\lvert \mathcal N (u) \cap \mathcal …

The Sorensen index is $$ \mathbf S_{\text{Sorensen}}[u,v] = \frac{ 2\lvert \mathcal N (u) \cap …

Betweenness centrality of a node $v$ is measurement of how likely the shortest path between two …

Given a graph with adjacency matrix $\mathbf A$, the eigenvector centrality is $$ \mathbf e_u = …

A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. Multiplication of …

Cut For a subset of nodes $\mathcal A\subset \mathcal V$, with the rest of nodes $\bar {\mathcal A} …

Laplacian is a useful representation of graphs. The unnormalized Laplacian is $$ \mathbf L = \mathbf …