## Graph

A graph $\mathcal G$ has nodes $\mathcal V$ and edges $\mathcal E$,

$$\mathcal G = ( \mathcal V, \mathcal E).$$

Edges

Edges are relations between nodes. For $u\in \mathcal V$ and $v\in \mathcal V$, if there is an edge between them, then $(u, v)\in \mathcal E$.

## Representations of Graph

There are different representations of a graph.

A adjacency matrix of a graph represents the nodes using row and column indices and edges using elements of the matrix.

For simple graph, the adjacency matrix is rank two and dimension $\lvert \mathcal V \rvert \times \lvert \mathcal V \rvert$. For edge $(u, v)\in \mathcal E$, it is represented by the matrix element $\mathbf A[u,v]=1$.

See Sanchez-Lengeling, 2021 for an interactive example1.

A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$\begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$$ for the graph Public Domain, Link

### Laplacians

Laplacians are transformations of the adjacency matrix but provides a lot more convenience for analysis.

Graph Laplacians

Laplacian is a useful representation of graphs. The unnormalized Laplacian is

\mathbf L = \mathbf D - \mathbf A,

where $\mathbf A$ is the and $\mathbf D$ is the degree matrix, i.e., a diagonalized matrix with the diagonal elements being the degrees.

Normalized Laplacian

The symmetric normalized Laplacian is

\mathbf L_{\text{sym}} = \mathbf D^{-1/2} \mathbf A \mathbf D^{-1/2}.

The eigenvalues of normalized Laplacian is bounded ($$). The random walk Laplacian is \mathbf L_{\text{RW}} = \mathbf … ## Multi-Relational Graph A graph may have different types of edges, \tau\in \mathcal R, where R is a set of types of relations. A multi-relational graph is then$$ \begin{align} u &\in \mathcal V \\ v &\in \mathcal V \\ \tau &\in \mathcal R \\ (u, \tau, v) &\in \mathcal E. \end{align} $$Adjacency Matrix for Multi-relation Graph For multi-relational graph, it can have more ranks and the dimension can be \lvert \mathcal V \rvert \times \lvert \mathcal V \rvert \times \lvert \mathcal R\rvert, where \mathcal R represents the types of relations. typeadjacency matrix \tau=\tau_1$$A_{\tau=\tau_1}\tau=\tau_2$$A_{\tau=\tau_2} \cdots$$\cdots$Two popular examples: • heterogeneous • multipartite • multiplex ### Heterogeneous Nodes are subsets without intersections,$\mathcal V = \mathcal V_1\cup \mathcal V_2 \cdots \mathcal V_k$and$\mathcal V_i \cap \mathcal V_j = \emptyset$for$\forall i\neq j\$.

The famous multi-partite graph is an example of heterogeneous graph.

Movie and User Bi-partite Graph

For a website that hosts a movie database and a user database, the relation about which user watched which movie is a bi-partite graph.

### Mutiplex

The nodes can be viewed to exist in different layers and the edges in each layer are different.

Planted: by ;

L Ma (2021). 'What is Graph', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/wiki/graph/basics/what-is-graph/.