Efficient Framework for Partitioning Positive Hypergraph into Dense Subgraph

Ms. Akanksha J. Kulkarni, Prof. S. A. Bhavsar

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.

Full Text:

PDF

References


Akanksha J. Kulkarni, Swati A. Bhavsar, ”A Survey on Hypergraph

Partitioning Techniques,” International Journal of Trend in Research and

Development (IJTRD), ISSN: 2394-9333, Volume-4 — Issue-1 , February

B. Kernighan and S. Lin, ”An efficient heuristic procedure for partitioning

graphs,” Bell Syst. Tech. J., vol. 49, pp. 291-307, 1970.

D.-H. Huang and A. B. Kahng, ”When clusters meet partitions: New

density-based methods for circuit decomposition,” in Proc. Eur. Conf.

Des. Test,1995, pp. 60-64.

I. Dhillon, Y. Guan, and B. Kulis, ”Kernel k-means: spectral clustering

and normalized cuts,” in Proc. ACM Int. Conf. Knowl. Discov. Data Min.,

, pp. 551-556.

P. F. Felzenszwalb and D. P. Huttenlocher, ”Efficient graph-based Image

segmentation,” Int. J. Comput. Vis., vol. 59, no. 2, pp. 167-181, 2004

J. H. Kappes, M. Speth, B. Andres, G. Reinelt, and C. Schn, ”Globally

optimal image partitioning by multicuts,” in Proc. Energy Minim.

Methods Comput. Vis. Pattern Recognit., 2011, pp. 31-44.

C. Fiduccia and R. Mattheyses, ”A linear-time heuristic for improving

network partitions,” in Proc. 19th Conf. Des. Autom., 1982, pp. 175-181.

G. Karypis and V. Kumar, ”A fast and high quality multilevel scheme for

partitioning irregular graphs,” SIAM J. Sci. Comput., vol. 20, no. 1, pp.

-392, 1998.

N. Bansal, A. Blum, and S. Chawla, ”Correlation clustering,” Mach.

Learn., no. 1-3, vol. 56, pp. 89-113, 2004.

S. Kim, S. Nowozin, P. Kohli, and C. D. Yoo, ”Higher-order correlation

clustering for image segmentation,” in Proc. Adv. Neural Inf. Process.

Syst.,2011, pp. 1530-1538.

http://glaros.dtc.umn.edu/gkhome/views/metis/index.html

http://www.labri.u-bordeaux.fr/perso/pelegrin/scotch/

http://staffweb.cms.gre.ac.uk/ c.walshaw/jostle/


Refbacks

  • There are currently no refbacks.


 

Copyright © IJETT, International Journal on Emerging Trends in Technology