# Graph theory

Jump to navigation
Jump to search

## Basics

- A graph is a collection of
**nodes**or**vertices**and a set of**edges**that connect pairs of nodes. - Edges may be
**undirected**or**directed**or have**loops** - In undirected networks, the
**node degree**of node*n*is the number of edges linked to*n*and the**node degree distribution**is the distribution of nodes with degree*k*, i.e. how many nodes have 1, 2, 3, ..., n edges - In directed networks, the
**in-degree**of a node*n*is the number of incoming edges and the**out-degree**is the number of outgoing edges - Disconnected nodes and edges form individual components
- The
**neighbourhood**of node*v*is the induced subgraph consisting of all nodes adjacent to*v* - The
**connectivity**of a node is the number of neighbours; the**neighbourhood connectivity**of a node*n*is defined as the average connectivity of all neighbours on*n* **Cliques**are subset of nodes where each pair is joined by an edge; https://en.wikipedia.org/wiki/Clique_(graph_theory)- An
**e-Near Clique**are a subset of nodes such that a fraction of e pairs of nodes have an edge between them - A
**co-clique**are a subset of nodes where no two are joined by an edge

## Network perturbation

- Node deletion - delete a node and all of its edges
- Node separation set - a subset of nodes whose deletion causes the number of components in the graph to increase
- Edge deletion - delete an edge
- Cut set - delete edges to increase the number of components
- Network robustness - how hard is it to break the network? Delete a random node or edge and see if nodes are still connected

## NetworkAnalyzer

- For every node in a network, NetworkAnalyzer computes its degree (in- and out-degrees for directed networks), its clustering coefficient, the number of self-loops, and a variety of other parameters.
- For node
*u*of degree*k*, where there are*e*edges between neighbours of*u*, the cluster coefficient is =**e / [k(k-1)/2]**

## Search algorithms

- Breadth-First Search: closest neighbours first
- Depth-First Search: last in first out (LIFO)
- Bellman-Ford Algorithm: find shortest path by calculating all costs and updating until no further modifications
- Dijkstra's Algorithm: same as Bellman-Ford but only calculates paths that have the least cost
- A* Algorithm: advancement of Dijkstra's Algorithm

## Useful resources

- Network Analysis and Visualization with R and igraph - http://kateto.net/netscix2016
- Practical statistical network analysis - http://statmath.wu.ac.at/research/friday/resources_WS0708_SS08/igraph.pdf