معیاری جدید برای بخش‌بندی سیستم‌های پردازش گراف مبتنی بر بلوک
محورهای موضوعی : مهندسی برق و کامپیوتر
مسعود ساغریچیان
1
(دانشگاه الزهرا)
مرتضی علیپور لنگوری
2
(دانشگاه مکمستر)
کلید واژه: بخش‌بندی, مبتنی بر بلوک, گراف, قطر,
چکیده مقاله :
به واسطه قدرت و سادگی، سیستم‌های پردازش گراف مبتنی بر بلوک در سال‌های اخیر مورد توجه ویژه‌ای قرار گرفته‌اند. اغلب این سیستم‌ها از روش‌های بخش‌بندی عمومی و همه‌منظوره جهت تولید پارتیشن‌های مورد نیاز خود استفاده می‌کنند. همین امر منجر شده که کارایی این سیستم‌ها محدود شود. برای رفع این مشکل الگوریتم‌های خاص‌منظوره‌ای برای بخش‌بندی این دسته از سیستم‌ها ارائه شده است، اما مشکل این دسته از روش‌ها آن است که همچنان معیارهای سنتی نظیر تعداد یال برشی و تعادل بار به عنوان تابع هدف این روش‌ها مد نظر قرار گرفته است. این در حالی است که قدرت سیستم‌های پردازش گراف مبتنی بر بلوک به واسطه ویژگی‌های منحصر به فردی است که در طراحی این دسته از سیستم‌ها مد نظر قرار گرفته است. به همین جهت در این مقاله، ویژگی‌های ذاتی و اساسی این دسته از سیستم‌ها مورد توجه قرار گرفته و با توجه به این خواص، دو معیار جدید به عنوان معیار تابع هدف بخش‌بندی، معرفی شده است. بر اساس تحقیقات انجام‌گرفته، روش پیشنهادی اولین الگوریتم بخش‌بندی است که قطر گراف سطح بالا و اندازه گره‌های گراف سطح بالای حاصل از بخش‌بندی را به عنوان تابع هدف در نظر گرفته می‌گیرد. ارزیابی روش پیشنهادی بر روی مجموعه داده‌های واقعی نشان داد که روش پیشنهادی به طور مؤثری قادر به کاهش قطر گراف سطح بالای حاصل از بخش‌بندی نسبت به سایر الگوریتم‌های بخش‌بندی متداول می‌باشد. به علاوه، یال برشی حاصل از روش پیشنهادی بسیار نزدیک به یکی از معروف‌ترین روش‌های بخش‌بندی متمرکز، متیس می‌باشد. از آنجا که قطر گراف سطح بالا رابطه مستقیمی با تعداد سوپراستپ‌های مورد نیاز در سیستم‌های پردازش گراف بلوکی دارد، روش پیشنهادی با کاهش آن قادر به افزایش کارایی این دسته از روش‌ها خواهد شد.
Block-centric graph processing systems have received significant attention in recent years. To produce the required partitions, most of these systems use general-purpose partitioning methods. As a result, the performance of them has been limited. To face this problem, special partitioning algorithms have been proposed by researchers. However, these methods focused on traditional partitioning measures like the number of cutting-edges and the load-balance. In return, the power of block-centric graph processing systems is due to unique characteristics that are focused on the design of them. According to basic and important characteristics of these systems, in this paper two new measures are proposed as partitioning goals. To the best of our knowledge, the proposed method is the first work that considers the diameter and size of the high-level graph as optimization factors for partitioning purposes. The evaluation of the proposed method over real graphs showed that we could significantly reduce the diameter of the high-level graph. Moreover, the number of cutting-edges of the proposed method are very close to Metis, one of most popular centralized partitioning methods. Since the number of required supersteps in block-centric graph processing systems mainly depends on the diameter of the high-level graph, the proposed method can significantly improve the performance of these systems.
[1] M. Ulizko, E. Antonov, A. Artamonov, et al., "Graph visualization of the characteristics of complex objects on the example of the analysis of politicians," in Proc. 30th Int. Conf. on Computer Graphics and Machine Vision, 9 pp., St. Petersburg, Russia Federation, 22-25 Sept. 2020.
[2] J. S. Yeom, et al., "Overcoming the scalability challenges of epidemic simulations on blue waters," in Proc. IEEE 28th Int. Parallel and Distributed Processing Symp., pp. 755-764, Phoenix, AZ, USA, 19-23 May 2014.
[3] R. Hess, V. H. Visschers, and M. Siegrist, "Risk communication with pictographs: the role of numeracy and graph processing," Judgment and Decision Making, vol. 6, no. 3, pp. 263-274, Apr. 2011.
[4] V. Agarwal, F. Petrini, D. Pasetto, D. A. Bader, "Scalable graph exploration on multicore processors," in Proc. of the ACM/IEEE International Conf. for High Performance Computing, Networking, Storage and Analysis, 11 pp., New Orleans, LA, USA, 13-19 Nov. 2010.
[5] Y. Wang, Y. Shangdi, L. Dhulipala, Y. Gu, and J. Shun, "GeoGraph: a framework for graph processing on geometric data," ACM SIGOPS Operating Systems Review, vol. 55, no. 1, pp. 38-46, 2021.
[6] G. Malewicz, et al., "Pregel: a system for large-scale graph processing," in Proc. of the ACM SIGMOD Int. Conf. on Management of Datapp. 135-146, Indianapolis, IN, USA, 6-10 Jun. 2010.
[7] S. Salihoglu and J. Widom, "GPS: a graph processing system," in Proc. of the 25th Int. Conf. on Scientific and Statistical Database Management, Article No.: 22, 12 pp., Baltimore, MA, USA, 29-31 Jul. 2013.
[8] J. E. Gonzalez, et al., "Graphx: Graph processing in a distributed dataflow framework," in Proc. 11th USENIX Symp. on Operating Systems Design and Implementation, OSDI'14, pp. 599-613, Broomfield, CO, USA, 6-8 Oct. 2014.
[9] S. Hong, et al., "PGX.D: a fast distributed graph processing engine," in Proc. of the Int. Conf. for High Performance Computing, Networking, Storage and Analysis, 12 pp., Austin, TX, USA, 15-20 Nov. 2015.
[10] R. R. McCune, T. Weninger, and G. Madey, "Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing," ACM Computing Surveys, vol. 48, no. 2, Article No.: 25, 39 pp., Nov. 2015.
[11] D. Yan, J. Cheng, Y. Lu, and W. Ng, "Blogel: a block-centric framework for distributed computation on real-world graphs," Proc. of the VLDB Endowment, vol. 7, no. 14, pp. 1981-1992, Oct. 2014.
[12] M. Sagharichian, H. Naderi, and M. Haghjoo, "ExPregel: a new computational model for large‐scale graph processing," Concurrency and Computation: Practice and Experience, vol. 27, no. 17, pp. 4954-4969, Dec. 2015.
[13] S. Aridhi, A. Montresor, and Y. Velegrakis, "BLADYG: a novel block-centric framework for the analysis of large dynamic graphs," in Proc. of the ACM Workshop on High Performance Graph Processing, pp. 39-42, Kyoto, Japan, 31-31 May 2016.
[14] R. Dindokar, N. Choudhury, and Y. Simmhan, "A meta-graph approach to analyze subgraph-centric distributed programming models," in Proc. IEEE Int. Conf. on Big Data, pp. 37-47, Washington, DC, USA, 5-8 Dec. 2016.
[15] A. Quamar and A. Deshpande, "NScaleSpark: subgraph-centric graph analytics on Apache Spark," in Proc. of the 1st ACM SIGMOD Workshop on Network Data Analytics, Article No.: 5, 8 pp., San Francisco, CA, USA, 1-1 Jul. 2016.
[16] M. Sagharichian and H. Naderi, "Intelligent and independent processes for overcoming big graphs," The J. of Supercomputing, vol. 73, no. 4, pp. 1438-1466, Apr. 2017.
[17] X. Sui, D. Nguyen, M. Burtscher, and K. Pingali, "Parallel graph partitioning on multicore architectures," in Proc. Int. Workshop on Languages and Compilers for Parallel Computing, pp. 246-260, Houston, TX, USA, 7-9 Oct. 2010.
[18] D. LaSalle and G. Karypis, "Multi-threaded graph partitioning," IEEE 27th Int. Symp. on Parallel and Distributed Processing, pp. 225-236, Cambridge, MA, USA,20-24 May 2013.
[19] M. Naumov and T. Moon, Parallel Spectral Graph Partitioning, Tech. Rep., NVIDIA Tech. Rep, 2016.
[20] H. Meyerhenke, P. Sanders, and C. Schulz, "Parallel graph partitioning for complex networks," IEEE Trans. on Parallel and Distributed Systems, vol. 28, no. 9, pp. 2625-2638, Sept. 2017.
[21] F. Rahimian, A. H. Payberah, S. Girdzijauskas, M. Jelasity, and S. Haridi, "JA-BE-JA: A distributed algorithm for balanced graph partitioning," in Proc. IEEE 7th Int Conf. on Self-Adaptive and Self-Organizing Systems, pp. 51-60, Philadelphia, PA, USA, 9-13 Sept. 2013.
[22] C. Martella, D. Logothetis, A. Loukas, and G. Siganos, "Spinner: scalable graph partitioning in the cloud," in Proc.IEEE 33rd International Conf. on Data Engineering, ICDE'17, pp. 1083-1094, San Diego, CA, USA, 19-22 Apr. 2017.
[23] M. Onizuka, T. Fujimori, and H. Shiokawa, "Graph partitioning for distributed graph processing," Data Science and Engineering, vol. 2, no. 1, pp. 94-105, Mar. 2017.
[24] J. Sun, H. Vandierendonck, and D. S. Nikolopoulos, "Graphgrind: addressing load imbalance of graph partitioning," in Proc. of the Int. Conf. on Supercomputing, Article No.: 16, 10 pp., Chicago, IL, USA, 14-16 Jun. 2017.
[25] C. J. Alpert and A. B. Kahng, "Recent directions in netlist partitioning: a survey," Integration, vol. 19, no. 1-2, pp. 1-81, 1995.
[26] B. Hendrickson and T. G. Kolda, "Graph partitioning models for parallel computing," Parallel Computing, vol. 26, no. 12, pp. 1519-1534, 2000.
[27] T. N. Bui and C. Jones, "Finding good approximate vertex and edge partitions is NP-hard," Information Processing Letters, vol. 42, no. 3, pp. 153-159, May 1992.
[28] B. W. Kernighan and S. Lin, "An efficient heuristic procedure for partitioning graphs," The Bell System Technical J., vol. 49, no. 2, pp. 291-307, Feb. 1970.
[29] Y. G. Saab, "An effective multilevel algorithm for bisecting graphs and hypergraphs," IEEE Trans. on Computers, vol. 53, no. 6, pp. 641-652, Jun. 2004.
[30] L. Sun and M. Leng, "An effective multi-level algorithm based on simulated annealing for bisecting graph," in Proc. Int. Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, 12 pp., Ezhou, China, 27-29 Aug. 2007.
[31] C. Aykanat, B. B. Cambazoglu, and B. Uçar, "Multi-level direct k-way hypergraph partitioning with multiple constraints and fixed vertices," J. of Parallel and Distributed Computing, vol. 68, no. 5, pp. 609-625, May 2008.
[32] R. Khandekar, S. Rao, and U. Vazirani, "Graph partitioning using single commodity flows," J. of the ACM, vol. 56, no. 4, pp. 385-390, 2009.
[33] H. Meyerhenke, B. Monien, and S. Schamberger, "Graph partitioning and disturbed diffusion," Parallel Computing, vol. 35, no. 10-11, pp. 544-569, Oct. 2009.
[34] P. Chardaire, M. Barake, and G. P. McKeown, "A probe-based heuristic for graph partitioning," IEEE Trans. on Computers, vol. 56, no. 12, pp. 1707-1720, Dec. 2007.
[35] R. Zamprogno and A. R. Amaral, "An efficient approach for large scale graph partitioning," J. of Combinatorial Optimization, vol. 13, no. 4, pp. 289-320, May 2007.
[36] A. Trifunovic and W. J. Knottenbelt, "Towards a parallel disk-based algorithm for multilevel k-way hypergraph partitioning," in Proc. IEEE 18th Int. Parallel and Distributed Processing Symp., pp. 236-243, Santa Fe, NM, USA, 26-30 Apr. 2004.
[37] I. Stanton and G. Kliot, "Streaming graph partitioning for large distributed graphs," in Proc. of the 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pp. 1222-1230, Beijing, China, ?12-16 Aug. 2012.
[38] C. Tsourakakis, C. Gkantsidis, B. Radunovic, M. Vojnovic, "Fennel: streaming graph partitioning for massive scale graphs," in Proc. of the 7th ACM Int. Conf. on Web Search and Data Mining, pp. 333-342, New York, NY, USA, 24-26 Feb. 2014.
[39] Y. Tian, A. Balmin, S. A. Corsten, S. Tatikonda, and J. McPherson, "From "think like a vertex" to "think like a graph"," Proc. of the VLDB Endowment, vol. 7, no. 3, pp. 193-204, Nov. 2013.
[40] W. Fan, J. Xu, Y. Wu, W. Yu, and J. Jiang, "GRAPE: parallelizing sequential graph computations," Proc. of the VLDB Endowment, vol. 10, no. 12, pp. 1889-1892, Aug. 2017.
[41] S. Verma, L. M. Leslie, Y. Shin, and I. Gupta, "An experimental comparison of partitioning strategies in distributed graph processing," Proc. of the VLDB Endowment, vol. 10, pp. 493-504, Jan. 2017.
[42] Y. Kim, M. Bae, and S. Oh, "Dynamic block reassignment for load balancing of block centric graph processing systems," KIPS Trans. on Software and Data Engineering, vol. 7, no. 5, pp. 177-188, 2018.
[43] X. Wen, S. Zhang, and H. You, DRONE: A Distributed Subgraph-Centric Framework for Processing Large Scale Power-law Graphs, arXiv preprint arXiv:1812.04380, 2018.
[44] M. Sagharichian, M. A. Langouri, and H. Naderi, "A fast method to exactly calculate the diameter of incremental disconnected graphs," World Wide Web, vol. 20, no. 2, pp. 399-416, Mar. 2017.
[45] Stanford University, Stanford Large Network Dataset Collection, Available from: http://snap.stanford.edu/data.
282 نشریه مهندسی برق و مهندسی کامپیوتر ایران، ب- مهندسی کامپیوتر، سال 20، شماره 4، زمستان 1401
مقاله پژوهشی
معیاری جدید برای بخش‌بندی سیستم‌های
پردازش گراف مبتنی بر بلوک
مسعود ساغریچیان و مرتضی علیپور لنگوری
چکیده: به واسطه قدرت و سادگی، سیستم‌های پردازش گراف مبتنی بر بلوک در سال‌های اخیر مورد توجه ویژه‌ای قرار گرفته‌اند. اغلب این سیستم‌ها از روش‌های بخش‌بندی عمومی و همه‌منظوره جهت تولید پارتیشن‌های مورد نیاز خود استفاده می‌کنند. همین امر منجر شده که کارایی این سیستم‌ها محدود شود. برای رفع این مشکل الگوریتم‌های خاص‌منظوره‌ای برای بخش‌بندی این دسته از سیستم‌ها ارائه شده است، اما مشکل این دسته از روش‌ها آن است که همچنان معیارهای سنتی نظیر تعداد یال برشی و تعادل بار به عنوان تابع هدف این روش‌ها مد نظر قرار گرفته است. این در حالی است که قدرت سیستم‌های پردازش گراف مبتنی بر بلوک به واسطه ویژگی‌های منحصر به فردی است که در طراحی این دسته از سیستم‌ها مد نظر قرار گرفته است. به همین جهت در این مقاله، ویژگی‌های ذاتی و اساسی این دسته از سیستم‌ها مورد توجه قرار گرفته و با توجه به این خواص، دو معیار جدید به عنوان معیار تابع هدف بخش‌بندی، معرفی شده است. بر اساس تحقیقات انجام‌گرفته، روش پیشنهادی اولین الگوریتم بخش‌بندی است که قطر گراف سطح بالا و اندازه گره‌های گراف سطح بالای حاصل از بخش‌بندی را به عنوان تابع هدف در نظر گرفته می‌گیرد. ارزیابی روش پیشنهادی بر روی مجموعه داده‌های واقعی نشان داد که روش پیشنهادی به طور مؤثری قادر به کاهش قطر گراف سطح بالای حاصل از بخش‌بندی نسبت به سایر الگوریتم‌های بخش‌بندی متداول می‌باشد. به علاوه، یال برشی حاصل از روش پیشنهادی بسیار نزدیک به یکی از معروف‌ترین روش‌های بخش‌بندی متمرکز، متیس می‌باشد. از آنجا که قطر گراف سطح بالا رابطه مستقیمی با تعداد سوپراستپ‌های مورد نیاز در سیستم‌های پردازش گراف بلوکی دارد، روش پیشنهادی با کاهش آن قادر به افزایش کارایی این دسته از روش‌ها خواهد شد.
کلیدواژه: بخش‌بندی، مبتنی بر بلوک، گراف، قطر.
1- مقدمه
با افزایش سرعت رشد شبکه‌هایی نظیر شبکه‌های اجتماعی، گراف وب و شبکه‌های نظیر به نظیر، اندازه این شبکه‌ها در سال‌های اخیر با رشد بالایی روبه‌رو بوده است. از آنجا که این شبکه‌ها در حوزه‌های مختلفی اعم از سیاسی [1]، روان‌شناسی [2]، جامعه‌شناسی [3] و نظایر آنها مورد توجه است، استخراج ویژگی‌های این شبکه‌ها و همچنین تحلیل آنها به یک حوزه جذاب تحقیقاتی تبدیل شده است. با توجه به ذات ارتباطات موجود در این شبکه‌ها، نظریه گراف‌ها به عنوان ابزاری اساسی جهت نمایش و پردازش چنین شبکه‌هایی مورد استفاده قرار گرفته است. اغلب گراف‌هایی که با آنها روبه‌رو هستیم عمدتاً بسیار بزرگ هستند. به عنوان مثال گراف شبکه اجتماعی فیس‌بوک طبق گزارش سال 2021 دارای 89/2 میلیارد گره بوده است.
در راستای تحلیل چنین گراف‌های بزرگی، سیستم‌های پردازش گراف مختلفی توسعه داده شده است. برخی از این سیستم‌ها به صورت متمرکز و روی یک ماشین، فرایند پردازش را انجام می‌دهند [4] و [5]، اما درصد قابل توجهی از سیستم‌های پردازش گراف از رویکرد توزیع‌شدگی بهره گرفته‌اند [6] تا [10]. سیستم‌های پردازش گراف مبتنی بر بلوک نسبت به سایر روش‌های پردازش گراف توزیع‌شده، کارایی بهتری را از حیث میزان ترافیک و همچنین تعداد گلوگاه‌های همگام‌سازی از خود نشان داده‌اند [11] تا [16]. به منظور پردازش توزیع‌شده، ابتدا باید گراف به قسمت‌هایی بخش‌بندی شود و هر بخش توسط یک ماشین در سیستم توزیع‌شده مورد پردازش قرار گیرد. با توجه به توزیع یال‌ها در این گراف‌ها و همچنین ارتباطات زیاد بین گره‌ها، بخش‌بندی گراف به صورت تصادفی منجر به تولید پارتیشن‌هایی می‌شود که ارتباط بین گره‌های پارتیشن‌های مختلف بسیار زیاد است. در نتیجه یک بخش‌بند گراف باید بتواند به دو چالش اساسی توجه نماید: 1) کمینه‌سازی تعداد یال‌های برشی و 2) بیشینه‌کردن تعادل بار بین پارتیشن‌ها. اغلب روش‌های ارائه‌شده برای بخش‌بندی گراف تنها به این دو معیار توجه نموده‌اند و سعی کرده‌اند که بخش‌بندی نهایی را با این دو معیار مورد ارزیابی قرار دهند. از سوی دیگر، فرایند بخش‌بندی باید بر روی گراف اصلی که گراف بزرگی است، اعمال شود. برخی از روش‌ها نظیر «متیس» و توسعه‌های آن، فرایند بخش‌بندی را به صورت متمرکز با استفاده از یک ماشین انجام می‌دهند [17] تا [20]. مزیت این دسته از روش‌ها آن است که چون الگوریتم، دانش کاملی از کل گراف را دارا می‌باشد، عمدتاً کیفیت بخش‌بندی تولیدشده بسیار بهتر است. مشکل این دسته از روش‌ها آن است که برای پردازش گراف‌های بزرگ، نیازمند ماشینی با منابع محاسباتی بسیار بالا هستند. همچنین زمان اجرای بالا هم از دیگر نقاط ضعف آنها است. برای غلبه بر این مشکل روش‌های دیگری فرایند بخش‌بندی را به صورت توزیع‌شده انجام می‌دهند [21] تا [24].
در این مقاله نشان داده شده که معیارهای سنتی مورد استفاده در بخش‌بندی گراف برای سیستم‌های پردازش گراف مبتنی بر بلوک لازم است، اما کافی نیست. هدف اصلی این مقاله، استخراج معیارهایی پایه‌ای است که می‌تواند کارایی این دسته از سیستم‌ها را بهبود بخشد. برای نیل به این هدف، ابتدا ویژگی‌های مشترک سیستم‌های پردازش گراف مبتنی بر بلوک تبیین شده است. بر اساس این ویژگی‌ها، دو معیار جدید که تأثیر چشم‌گیری بر کیفیت پارتیشن‌ها برای سیستم‌های مبتنی بر بلوک دارند تعریف شده است: 1) قطر گراف سطح بالا و 2) متوسط انحراف معیار اندازه گره‌های سطح بالا. منظور از گره و گراف سطح بالا، گراف بلوکی حاصل از فرایند بخش‌بندی می‌باشد که مفصلاً در بخش‌های بعدی معین شده است. بر اساس این معیارها، یک روش جدید به منظور بخش‌بندی گراف ارائه شده که به دنبال بهینه‌سازی پارتیشن‌های تولیدی بر اساس
دو معیار پیشنهادی می‌باشد: 1) کمینه‌سازی قطر گراف سطح بالا و 2) کمینه‌سازی متوسط انحراف معیار گره‌های سطح بالا. بخش‌هایی از الگوریتم پیشنهادی که با گراف اصلی سروکار دارند، به صورت توزیع‌شده و قسمت‌هایی که با گراف سطح بالای تولیدی (اندازه آن بسیار کوچک‌تر از گراف اصلی است) سروکار دارند به صورت متمرکز، پیاده‌سازی شده‌اند. نتایج ارزیابی‌ها بر روی مجموعه داده‌های واقعی نشان دادند که نه تنها پارتیشن‌های تولیدی روش پیشنهادی از حیث قطر گراف سطح بالا بسیار کوچک‌تر از پارتیشن‌های تولیدی روش‌های متیس و «ورونوی»2 هستند، بلکه میزان یال برشی و تعادل بار پارتیشن‌های حاصل از روش پیشنهادی (که جزء اهداف ثانویه الگوریتم پیشنهادی و اهداف اصلی روش‌های تحت آزمون است)، بسیار نزدیک به متیس که بهترین روش بخش‌بندی متمرکز است، می‌باشد. به طور خلاصه نوآوری‌های این مقاله عبارت هستند از:
• استخراج و معرفی معیارهایی جدید برای بخش‌بندی سیستم‌های پردازش گراف بلوکی که می‌توانند کارایی این دسته از سیستم‌ها را بهینه‌تر نمایند.
• ارائه یک روش بخش‌بندی مبتنی بر معیارهای معرفی‌شده در این مقاله
• ارزیابی کیفی پارتیشن‌های تولیدشده از روش پیشنهادی
سایر بخش‌های این مقاله به شرح زیر است: بخش 2 به مروری بر کارهای مرتبط می‌پردازد و در بخش 3، معیارها و روش بخش‌بندی پیشنهادی به ترتیب معرفی می‌شوند. بخش 4، نتایج حاصل از ارزیابی روش پیشنهادی را با روش‌های موجود نشان می‌دهد و بخش 5 هم نتیجه‌گیری و کارهای تحقیقاتی آتی را بیان می‌نماید.
2- پیشینه پژوهش
بخش‌بندی به عنوان یکی از مسائل کلاسیک در بسیاری از شاخه‌های علوم کامپیوتر نظیر VLSI [25] و پردازش توزیع‌شده [26] شناخته می‌شود و ارائه یک بخش‌بندی بهینه، یک مسأله NP-Hard است [27]. الگوریتم‌های بخش‌بندی ارائه‌شده را می‌توان به گروه‌هایی طبقه‌بندی نمود. گروه اول بر مبنای جابه‌جایی گره‌ها، عمل بخش‌بندی را انجام می‌دهد که مهم‌ترین الگوریتم این دسته، الگوریتم KL [28] می‌باشد، اما این رهیافت برای گراف‌های بزرگ‌مقیاس مناسب نیست. این بدان جهت است که این دسته از الگوریتم‌ها نیازمند منابع و زمان زیاد به منظور شناسایی بهترین جابه‌جایی‌ها هستند. برای گراف‌های بزرگ، رویکردهای چندسطحه ارائه شدند [29] تا [31] و الگوریتم چندسطحه از 2 فاز تشکیل می‌شود. در فاز اول سعی می‌گردد تا حد امکان، پیچیدگی و اندازه گراف کوچک شود. سپس این گراف کوچک‌شده با استفاده از الگوریتم‌های نیمه‌بهینه نظیر KL بخش‌بندی می‌شود. در فاز دوم، نتیجه بخش‌بندی به گراف اصلی اعمال می‌گردد. دسته دیگر الگوریتم‌ها بر مبنای ماکسیمم جریان عمل می‌نمایند [32] و [33]. دسته بعدی از الگوریتم‌ها بر مبنای الگوریتم‌ها