Graph theory

From Dave's wiki
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