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

No comments:

Post a Comment