+Graphs

Intro

Graph G=(V,E)
E annotated with weights. If G unweighted, all weights are 1.

Vertex properties

Degree of v: $deg(i)=\sum _j{e}_{i,j}$. Neighbors of v: $\mathrm{\Gamma }(v)$.

Measure size of $A\left\{V\right\}$: $|A|$ or $vol(A)=\sum _{i\in A}deg(i)$.

Associated objects

Special vertex sets

Node cover of G=(V,E): subset of V which touches all e in E.

Proper vertex coloring; chromatic number.

Independent set of verteces: don’t share edge: a clique in $\overline{G}$.

Walks

A sequence of edges $(e_i)$ such that $e_i$ shares an end-point with $e_{i+1}$.

A walk may have a cycle. If it does not have a cycle, you have a path.

Also see random walks.

Alternating walks are defined and studied in combinatorial optimization problems over graphs; in these sequences even and odd edges are colored differently.

Cut

k-way cut: $cut((V_i))$ is a partitioning of V into k parts. Cutsets is a set of edges which, when removed from G, divides V into k partitions.

Weight of a cut

Weight of a cut is the sum of weights of edges in the cutset.

Minimum 2-way cut is a cut with the minimum weight. This is useful in partitioning nodes in a graph.

Subgraphs

A general subgraph: G’=(V’, E’). Subgraph induced by $A\left\{V\right\}$. Connected components of a graph. Clique: a complete subgraph.

Spanning trees

Spannning tree. MST spanning a certain node set N: Aka Steiner tree. MST spanning with support over node set N: Aka Group Steiner tree.

Subtypes

Multigraphs: multiple edges allowed.

Tree

G sans cycle. Forest F: set of trees.

Biconnected graph

2 paths between any node pair.

Based on degree

d-regular G: $\mathrm{\forall }v:|N(v)|=d$. Complete graph $K_n$.

Perfect graph G

Chromatic number = size of the largest clique in G.

A graph is perfect iff its complement is perfect.

Bipartite graph

E = cutset. Complete bipartite graph: All v in A has edge to all u in B. Complete bipartite graph $K_{i,j}$. Can have A vs B adj matrix M. Thence get usual adj matrix for G: $\left[\begin{array}{ccc}0& M{\text{M}}^T& 0\end{array}\right]$.

Chordal graph G

Aka triangulated graph. Every cycle in G has a chord. G has a junction tree iff it is chordal.

Planar graphs

(Kuratowski) G planar iff $K_5$ and $K_{3,3}$ are in G.

Directred graph, networks

Digraph or directed graph. Networks: digraph with edge weights.

Directed acyclic graphs (DAG)

Very useful in designing algorithms: can do recursion easily.

Topological numbering t of nodes

Number nodes so that if there is a path from u to v, then $p(u)<p(v)$. Cyclic graphs don’t have a topological numbering.

Singly connected directed graph

Useful in probabilistic graphical models.

A tree underlies the graph: only 1 undirected path between any node pair.

Generalizations

Hypergraphs

Edges connect k-sets of verices, not just pairs.

Properties

Hop plot

For h, let g(h) be number of node pairs with path $\le h$. Hop plot plots this.

Diameter

Diameter of G. q effective diameter: q fraction of $V\times V$ have path length $\le d$.

Single source (s) shortest paths

Consider a weighted graph with weight $e(a,b)$ between two nodes. Suppose that you want to find the shortest path to every vertex $v\in V$ from $s$.

One can use a bottom-up programming approach. (Dijkstra) Start with current node $c=s$. Initially set $d(s)=0$ and, $\mathrm{\forall }v\ne s:d(v)=\mathrm{\infty }$.

Define $f(c)$: For every $v\in \mathrm{\Gamma }(c)$, do the update: $d_{t+1}(v):=min(d_t(c)+e(c,v),d_t(v))$. Also, simultaneously update the ‘backpointer’ to point to $c$ (representing the optimal subsolution) if necessary.

Do $f(c)\mathrm{\forall }v\ne s$ .

Time: $O(n^2)$ in case of a complete graph.

Associated matreces

Edge incidence matrix J ($m\times n$); for weighted G: edge $e_{i,j}$ terminii (i, j) are marked $\pm \sqrt{e_{i,j}}$.

Vertex incidence/ adjacency matrix W: presence of edge $e_{i,j}$ indicated by weight at $W_{i,j},W_{j,i}$.

Connectivity matrix $A^{\mathrm{\infty }}$.

Degree matrix: D = diag(deg(i)).

Graph Laplacian of no-self-loop undirected graph

L = (D-W). $L=J{J}^T$. As L is $|V|\ast |V|$, it is an operator on the functions with domain V.

+ve semidefiniteness

L is symmetric, +ve semidefinite: $x^{T}Lx=x^{T}J{J}^{T}x$. So $\lambda \ge 0$.

Smoothness of vectors from quadratic form

$x^{T}Lx=x^{T}Dx-x^{T}Wx=\sum _{i,j}{W}_{i,j}(x_i^2-x_j{x}_i)=2^{-1}\sum _{i,j}{W}_{i,j}(x_i-x_j{)}^2=\sum _{e_{i,j}\in E}{e}_{i,j}(x_i-x_j{)}^2$. This is a measure of the degree of oscillations/ smoothness among x, where edges occur.

Eigenvectors

$L1=01,\therefore {\lambda }_1(L)=0$; so L singular.

If G has c connected components: ${\lambda }_1=..{\lambda }_c=0$: construct ev with 1 in the appropriate spots!

Smoothness of ev

Take ev x. Then $x^{T}Lx=\sum _{e_{i,j}\in E}{e}_{i,j}(x_i-x_j{)}^2$ measures smoothness of x where edges occur in the graph. But, ew are stationary points of $R(x)=x^{T}Lx/(x^{T}x)$. So, ev corresponding to lower ew tend to be smoother.

Smoothening functions

Consider the subspace spanned by the p bottom (smooth) ev. Any function on V, ie a $|V|$-dim vector can be projected on to this subspace in order to smoothen it according to the graph structure. Labelling of nodes is an example of such a function.

Applications

This property is useful when using ev x for classification of nodes - one doesn’t want neighboring nodes to have disparate values in x. This is useful in both spectral clustering and label propogation in semisupervised learning.

Normalized graph Laplacian

Take $N=I-D^{-1/2}W{D}^{-1/2}$ : this is the normalized version, $D^{-1/2}L{D}^{-1/2}$ of L, using the normalized adjacency matrix $D^{-1/2}W{D}^{-1/2}$.

$N⪰0$ as $L⪰0$, ie $x^{T}Dx-x^{T}Wx\ge 0\mathrm{\forall }x$: taking $D^{1/2}x=y$, see that $\mathrm{\forall }y:y^{T}Ny\ge 0$.

Normalized adjacency matrix has norm 1.

As $$y^{T}y-y^T{D}^{-1/2}W{D}^{-1/2}y\ge 0\text{(},seethat\text{)}1\ge {\parallel D^{-1/2}W{D}^{-1/2}\parallel }_2\text{(};Also,using\text{)}y=D^{1/2}1$$, get \ ${\parallel D^{-1/2}W{D}^{-1/2}\parallel }_2=1$.

Another way to see this: $D^{-1/2}W{D}^{-1/2}$ is obtained by a similarity transformation to $D^{-1}W$, which has ew in the range [-1, 1] due to Gerschgorin thm, and which has ${\sigma }_{m}ax=|{\lambda }_{m}ax|=1$ using the ev 1.

Quadratic form: Normalized smoothness measure

$$y^{T}Ny=y^T{D}^{-1/2}L{D}^{-1/2}y=\sum _{(i,j)\in E}{W}_{ij}(\frac{y_i}{\sqrt{d_{ii}}}-\frac{y_j}{\sqrt{d_{jj}}}{)}^2\text{(}:fromtheform\text{)}{x}^{T}Lx\text{(}beingasmoothnessmeasure.Punishesdeviationbetween\text{)}\left\{y_i\right\}$$ corresponding to edges emanating from high degree vertices less.

Expanders

A sparse graph with high connectivity properties. Connectivity quantified as edge expansion or vertex expansion. Let $E^{\prime }(S)$: edges with exactly one end point in S.

Edge expansion of G

Aka isoparametric number. \ $h(G)=\underset{1\le |S|\le n/2}{min}\frac{|E^{\prime }(S)|}{|S|}$.

$\alpha$ vertex expansion of G

$g_{\alpha }(G)=\underset{1\le |S|\le n\alpha }{min}\frac{|\mathrm{\Gamma }(S)|}{|S|}$.

Other Examples

Most graphs are expanders. $K_n$ has good expansion properties, but it is not sparse.

Random graphs

Common Varieties: $G_{n,p},G_{n,|E|}$

G(n,p)

A static model: every edge is present or absent independent of other edges. p controls edge density. As $n\to \mathrm{\infty }diam(G)\to 2$. Size of the largest cluster is $O(\log n)$.