A New Approach to Community Graph Partition Using Graph Mining Techniques

A New Approach to Community Graph Partition Using Graph Mining Techniques

Bapuji Rao (BPUT, Rourkela, India) and Sarojananda Mishra (Department of CSE and Applications, IGIT, Sarang, India)
Copyright: © 2017 |Pages: 20
DOI: 10.4018/IJRSDA.2017010105


Knowledge extraction is very much possible from the community graph using graph mining techniques. The authors have studied the related definitions of graph partition in terms of both mathematical as well as computational aspects. To derive knowledge from a particular sub-community graph of a large community graph, the authors start partitioning the large community graph into smaller sub-community graphs. Thus, the knowledge extraction from the sub-community graph becomes easier and faster. The proposed approach of partition is done by detection of edges among the community members of dissimilar community. By studying existing techniques followed by different researchers, the authors propose a new and simple algorithm for partitioning the community graph into sub-community graphs using graph mining techniques. Finally, the authors have considered a benchmark dataset as example which verifies the strength and easiness of the proposed algorithm.
Article Preview

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 G1 has seven nodes {V1, V2, V3, V4, V5, V6, V7}. After cutting into two parts approximately equal in size, the first partition has nodes {V1, V2, V3, V4} and the second partition has nodes {V5, V6, V7}. The cut consists of only the edge (V3, V5) and the size of edge is 1.

Figure 1.

Graph G1 with seven nodes

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 6: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 5: 4 Issues (2018)
Volume 4: 4 Issues (2017)
Volume 3: 4 Issues (2016)
Volume 2: 2 Issues (2015)
Volume 1: 2 Issues (2014)
View Complete Journal Contents Listing