Graphs can be represented using the adjacency matrix $ A \in {\rm I\!R} ^{|\mathcal{V}| \times  |\mathcal{V}| }$

Each node in the graph has a row and a column in the adjacency matrix.

The presence of edges is  represented as an entry in the matrix as  $ A[u,v] = 1 $ if $ (u,v) \in \mathcal{E}$ and $ A[u,v] = 0 $ otherwise


Representation of Graphs

 - If edges are undirected then the adjacency matrix is a symmetric matrix.
 - If edges are directed then the adjacency matrix need not be a symmetric matrix.
 - Some graphs have weighted edges, so the entries in the adjacency matrix are real values rather than 0 or 1.


Properties of Edges in a Graph Data-structure

A graph $\mathcal{G} = ( \mathcal{V},\mathcal{E})$ is a set of nodes and edges.
An edge going from node $u \in \mathcal{V}$ to node $v \in \mathcal{V}$  is denoted as $(u,v) \in \mathcal{E}$


San Jose State University

Graph is a general data structure  to represent complex data in complex systems. 
It is used to describe and analyze objects/entities with relations/interactions.
A graph is a collection of nodes( objects ) and edges (interactions)


Graph Data structure

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

 - Computer networks
 - Social networks data
 - Economic network data
 - Biomedical network
 - Communication networks
 - Internet
 - Network of neurons
 - Citation between different papers
 - Knowledge graphs



Examples of Data Represented in Graph Data-structure


Mathematical Representation of Graph Data

Multi relational graphs have different types of edges.
The edge notation can be rewritten as $(u, \tau,v) \in \mathcal{E}$
$ \tau $ - relation type

Adjacency matrix $ A_{\tau}$, has to be  defined for each edge type.

Entire graph is summarized by an adjacency tensor $ \mathcal{A} \in {\rm I\!R} ^{|\mathcal{V}| \times |\mathcal{R}| \times |\mathcal{V}| }$
$\mathcal{R}$ , set of relations

Two important subsets of multi relational graphs are
 - Heterogeneous graphs
 - Multiplex graphs


Learn Before

Related

Learn After