Graph Partitioning and its Applications

Graph is an abstract idea of representing any objects which are connected to each other in a form of relation. Here, the object is called as a node and their relation denotes as an edge. Graph partitioning is a technique to distribute the whole graph data as a disjoint subset to a different device. The need of distributing huge graph data set is to process data efficiently and faster process of any graph related applications. A good graph partitioning algorithm always aims to reduce the communication between machine in their distributed environment and distribute vertices roughly equal to all the machines. Graph partitioning has been studying in the discipline between computer science and applied mathematics.

Distribution of huge unprecedented data always handy in order process any data-intensive application. Graph data partitioning is not unlike them. However, one additional challenge in graph data distributing unlike traditional data distribution is graph data is connected to each other. Consequently, if two connected nodes are distributed to a different machine it does need to maintain the relationship.

Graph partitioning is essential and applicable to following real-world applications:
1) Complex Networks:
The major complex networks are included: biological networks, social networks, transportation networks.
Social Networks: Social networks are very important and widely used network in this era of technology. The prominent social networks are Facebook, Twitter, and LinkedIn. All of this applications are maintaining and making use of graph theory. They use graph partitioning technology in order to process user query efficiently, as replying a query in a distributed manner is very handy and effective.
Biological Networks: Most of the biological network can be represented by using the graph abstraction. They are protein-protein interaction, metabolic networks, and gene co-expression network. This kind of network is structured by using biological entities (for example protein and genes) and their interactions among them.in this structure biological entities are vertices and their interaction with each other is the edge. This graph-structured network is playing a pivotal role in solving biological interaction problem in a huge a biological network.

Transportation Networks: Planning a trip and route is very common from transportation network by using a GPS (Global Positioning System) tool in the digital era. Graph partitioning can speed up and could be effective in planning a route by leveraging a good graph partitioning algorithm. In this network, the node is an intersection and edge is a path between two intersections. A number of algorithms have been proposed for reducing search space, reducing processing time, and accuracy as well.
2) PageRank:
PageRank is an application compute the rank of web rank from web network. PageRank denotes the rank or how important the web page is than others. Finding a rank and importance of a web page from web-graph would be effective by partitioning the whole graph into several distributed machine.

3) VLSI Design:
Very large-scale integration (VLSI) system is one of the graph partitioning problems in order reduce the connection between circuits in designing VLSI. The main objective of this partitioning is to reduce the VLSI design complexity by splitting them into a smaller component. Another goal of a good partitioning is to reduce the number of connection among those circuit components. Here, vertices are the cells of and edges are the wires between them.

4) Image processing:
Image segmentation is a most fundamental problem in image processing of any applications. Graph partitioning is one of the most attractive tools to split into several components of a picture. Pixels are denoting as a vertex and if there are similarities between pixel are represented as an edge.