A New Approach to Community Graph Partition Using Graph Mining Techniques

Graph Partitions

When a graph is divided into two sets of nodes by removing the edges that connect nodes in different sets should be minimized. While cutting the graph into two sets of nodes so that both the sets contain approximately equal number of nodes or vertices proposed by the authors (Rajaraman & Ullman, 2012).

In Figure 1 graph G₁ has seven nodes {V₁, V₂, V₃, V₄, V₅, V₆, V₇}. After cutting into two parts approximately equal in size, the first partition has nodes {V₁, V₂, V₃, V₄} and the second partition has nodes {V₅, V₆, V₇}. The cut consists of only the edge (V₃, V₅) and the size of edge is 1.

Figure 1.

Graph G₁ with seven nodes