Efficient Framework for Partitioning Positive Hypergraph into Dense Subgraph

Abstract

This work proposes a novel partition framework, which is dense subgraph partition (DSP), to decompose a positive hypergraph into dense subgraphs. Such Approach will partition Positive Hypergraph into Dense Subgraph automatically, precisely and efficiently. A positive hypergraph is a graph or hypergraph whose edges have positive weights except selfloops.hjhjhjh This work defines Dense Subgraph Partition on the top of core subgraph, conditional core subgraph, and disjoint partition of a conditional core subgraph. The result of DSP is an ordered list of dense subgraphs but having decreasing densities, which will uncover all underlying clusters, as well as outliers. To make a partition an algorithm called as min-partition evolution will be used.This algorithm is based on basic Divide and Conquer technique. DSP has one important property that, it is nonparametric partition and does not include any assumptions. Secondly, it gives exact solution by using Min Partition Evolution Algorithm. This work also gives the relationship between densest k subgraph problem , which is NP-Hard and does not have any precise solution. But DSP gives efficient solution to densest ksubgraph problem.