A graph $G=(V,E)$ is a tuple of two sets $V$ and $E$, where: - $V$ is a set of “nodes” or “vertices” - $E$ is a set of “edges” or “links”, representing the relationship between nodes $V$. >[!note:] >In an undirected graph each element of $E$ is a set $\{i,j\}$ as the order of both nodes does not matter. $\{i,j\}=\{j,i\} \in E$. However in a directed graph each element of $E$ is a tuple $(i,j)$. **Network Types:** | Name | Description | | ----------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | Simple network | Undirected network with at most 1 edge between any pair of nodes and no self-loops. | | Multigraph | Self-loops and multiple edges between the same node pair are possible. | | Directed network | The edge between $(i,j)$ can be different to the edge $(j,i)$. | | Weighted network | Edges have a weight attribute, representing the strength of relationship. | | Tree | A graph where no cycle exists. | | Acyclic network | A graph where no directed cycle exists. | | Bipartite network | There are different classes of nodes. Edges only exist between different node classes. E.g. the Netflix network has users and movies as node classes. Relationships only exist between users and movies. | | Hypergraph | Edges can describe the relationship between gt;2$ nodes (e.g. protein interaction networks). | ^d09159 **Network Definitions:** ^eb369e |Name|Description| |---|---| |Walk|A sequence of edges such that every edge $(e_i, e_{i+1})$ shares a node $v_i$. Also every pair of nodes $(v_{i-1}, v_i)$ is connected by the edge $e_i$.| |Trail|A walk where every edge is unique (i.e. only visited once).| |Path|A trail where every node is unique (i.e. only visited once).| |Cycle|A trail that starts and ends at the same node, such that all other nodes (besides the start/end node) in the sequence are unique.| ^7075f3 ![[network.jpeg|center|400]] **Adjacency Matrix:** A representation of the network as a matrix $A$ with size $n \times n$, where $n$ is the number of nodes $\vert V \vert$. ^daa3e3 $ A_{ij}= \begin{cases}1 & \text{if } (i,j) \in E\\ 0 & \text{otherwise} \end{cases} $ - In a weighted graph, $A_{ij}$ represents the weight if an edge exists between $(i,j)$. - An undirected graph has a symmetric adjacency matrix.