# Graph theory

## 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