Skip to main content
Article
Graph Partitioning in Parallelization of Large Scale Networks
Proceedings of the IEEE 41st Conference on Local Computer Networks (2016, Dubai, United Arab Emirates)
  • Sima Das
  • Jennifer Leopold, Missouri University of Science and Technology
  • Susmita Ghosh
  • Sajal K. Das, Missouri University of Science and Technology
Abstract

Real world large scale networks exhibit intrinsic community structure, with dense intra-community connectivity and sparse inter-community connectivity. Leveraging their community structure for parallelization of computational tasks and applications, is a significant step towards computational efficiency and application effectiveness. We propose a weighted depth-first-search graph partitioning algorithm for community formation that preserves the needed community dependency without any cycles. To comply with heterogeneity in community structure and size of the real world networks, we use a flexible limiting value for them. Further, our algorithm is a diversion from the existing modularity based algorithms. We evaluate our algorithm as the quality of the generated partitions, measured in terms of number of graph cuts.

Meeting Name
IEEE 41st Conference on Local Computer Networks, LCN 2016 (2016: Nov. 7-10, Dubai, United Arab Emirates)
Department(s)
Computer Science
Research Center/Lab(s)
Intelligent Systems Center
Keywords and Phrases
  • Graphic methods,
  • Community structures,
  • Computational task,
  • Graph Partitioning,
  • Large-scale network,
  • Parallelizations,
  • Partitioning algorithms,
  • Real-world,
  • Real-world networks,
  • Computer networks
International Standard Book Number (ISBN)
978-1-5090-2054-6
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2016 Sima Das. Under license to IEEE., All rights reserved.
Publication Date
11-1-2016
Disciplines
Citation Information
Sima Das, Jennifer Leopold, Susmita Ghosh and Sajal K. Das. "Graph Partitioning in Parallelization of Large Scale Networks" Proceedings of the IEEE 41st Conference on Local Computer Networks (2016, Dubai, United Arab Emirates) (2016) p. 176 - 179
Available at: http://works.bepress.com/sajal-das/66/