Graphs [Contraction Algorithm]

Graphs contain vertices and edges; can be directed or undirected.

Applications

1. Road networks: All softwares or web-apps store road networks in some form of graphical representation where the vertices correspond to intersections and the edges correspond to individual roads.
2. The Web: Vertices - individual web pages & Edges: hyperlinks. Eg: First vertex [tail] is going to be a page that contains a hyperlink and the second vertex [head] is going to be the page the hyperlink points to.
3. Social Networks: Vertices - individuals, Edges - relationships.

Cuts of Graphs

Grouping or partition of the vertices of the graph into two non-empty groups, A and B. 

When we talk about min-cut of a graph, we're mainly talking about the minimum number of crossing edges between these 2 groups.

Applications

1. Identify network bottlenecks/weaknesses. 
2. Community detection in social networks. - look for small regions that are tightly knit amongst themselves and weakly connected to the rest of the graph.
3. Image segmentation -
   Input: 2D array (graph) of pixels
   For two pixels that are immediately next to each other [left->right or top->bottom], you put an edge there. That gives us a Grid Graph. We also define edge weights i.e. how likely one expects two pixels to be coming from a common object [eg: perhaps, if they have the same colour map..etc].

Min-cut is then applied [a few times] on this grid graph with weighted edges to identify contiguous [major] objects in the picture.

 How many cuts does a graph with n vertices have? 

Ans: (2^n)-2

- Each vertex can either go into Set A or B - 2 choices! Therefore, we have 1 binary degree of      freedom for each vertex.

- Eg: a vertex can either go in A, B, none or both. The last 2 options are not possible, hence the '-2' .

Graph Implementations

[n: # of vertices, m: # of edges]

Adjacency Matrix

Represent G by a n*n (0 or 1 element) matrix A, where Ai,j =1 iff G has an i-j edge.

[In case of directed graphs, the value stored could be +1 or -1 depending on the direction the edge points in]

Space required: theta(n^2)

Adjacency List

Ingredients

• array (or list) of vertices - theta(n)
• array (or list) of edges - theta(m)
• each edge points to its end points - theta(m)
• each vertex points to edges incident on it - theta(m)

Space required: theta(m+n); after removing constants

Which is better? - depends on graph density and operations needed.

Adjacency lists are 

• good to represent massive networks
• good for performing graph searches
• doesn't take up as much space as Adj. Matrix.

Random Contraction Algorithm

While there are more than 2 vertices:

• pick a remaining edge (u,v) uniformly at random.
• merge (or contract) u and v into a single vertex
• remove self-loops

return cut represented by final 2 vertices. Each iteration is going to decrease the no. of vertices by 1.

The source code can be found here