Kliknij ten link, aby zobaczyć inne rodzaje publikacji na ten temat: Multi-level graph partitioning.
Artykuły w czasopismach na temat „Multi-level graph partitioning”
Utwórz poprawne odniesienie w stylach APA, MLA, Chicago, Harvard i wielu innych
Sprawdź 15 najlepszych artykułów w czasopismach naukowych na temat „Multi-level graph partitioning”.
Przycisk „Dodaj do bibliografii” jest dostępny obok każdej pracy w bibliografii. Użyj go – a my automatycznie utworzymy odniesienie bibliograficzne do wybranej pracy w stylu cytowania, którego potrzebujesz: APA, MLA, Harvard, Chicago, Vancouver itp.
Możesz również pobrać pełny tekst publikacji naukowej w formacie „.pdf” i przeczytać adnotację do pracy online, jeśli odpowiednie parametry są dostępne w metadanych.
Przeglądaj artykuły w czasopismach z różnych dziedzin i twórz odpowiednie bibliografie.
1
Fatih Talu, Muhammed. "Multi-level spectral graph partitioning method". Journal of Statistical Mechanics: Theory and Experiment 2017, nr 9 (27.09.2017): 093406. http://dx.doi.org/10.1088/1742-5468/aa85ba.
Pełny tekst źródła
2
Moreira, Orlando, Merten Popp i Christian Schulz. "Evolutionary multi-level acyclic graph partitioning". Journal of Heuristics 26, nr 5 (15.07.2020): 771–99. http://dx.doi.org/10.1007/s10732-020-09448-8.
Pełny tekst źródła
3
Pastukhov, R. K., A. V. Korshunov, D. Yu Turdakov i S. D. Kuznetsov. "Improving quality of graph partitioning using multi-level optimization". Programming and Computer Software 41, nr 5 (wrzesień 2015): 302–6. http://dx.doi.org/10.1134/s0361768815050096.
Pełny tekst źródła
4
Djidjev, Hristo N., Georg Hahn, Susan M. Mniszewski, Christian F. A. Negre i Anders M. N. Niklasson. "Using Graph Partitioning for Scalable Distributed Quantum Molecular Dynamics". Algorithms 12, nr 9 (7.09.2019): 187. http://dx.doi.org/10.3390/a12090187.
Pełny tekst źródłaStreszczenie:
The simulation of the physical movement of multi-body systems at an atomistic level, with forces calculated from a quantum mechanical description of the electrons, motivates a graph partitioning problem studied in this article. Several advanced algorithms relying on evaluations of matrix polynomials have been published in the literature for such simulations. We aim to use a special type of graph partitioning to efficiently parallelize these computations. For this, we create a graph representing the zero–nonzero structure of a thresholded density matrix, and partition that graph into several components. Each separate submatrix (corresponding to each subgraph) is then substituted into the matrix polynomial, and the result for the full matrix polynomial is reassembled at the end from the individual polynomials. This paper starts by introducing a rigorous definition as well as a mathematical justification of this partitioning problem. We assess the performance of several methods to compute graph partitions with respect to both the quality of the partitioning and their runtime.
5
Li, Yong, Jinxing Li, Yu Sun i Haisheng Li. "Load Balancing Based on Firefly and Ant Colony Optimization Algorithms for Parallel Computing". Biomimetics 7, nr 4 (17.10.2022): 168. http://dx.doi.org/10.3390/biomimetics7040168.
Pełny tekst źródłaStreszczenie:
With the wide application of computational fluid dynamics in various fields and the continuous growth of the complexity of the problem and the scale of the computational grid, large-scale parallel computing came into being and became an indispensable means to solve this problem. In the numerical simulation of multi-block grids, the mapping strategy from grid block to processor is an important factor affecting the efficiency of load balancing and communication overhead. The multi-level graph partitioning algorithm is an important algorithm that introduces graph network dynamic programming to solve the load-balancing problem. This paper proposed a firefly-ant compound optimization (FaCO) algorithm for the weighted fusion of two optimization rules of the firefly and ant colony algorithm. For the graph, results after multi-level graph partitioning are transformed into a traveling salesman problem (TSP). This algorithm is used to optimize the load distribution of the solution, and finally, the rough graph segmentation is projected to obtain the most original segmentation optimization results. Although firefly algorithm (FA) and ant colony optimization (ACO), as swarm intelligence algorithms, are widely used to solve TSP problems, for the problems for which swarm intelligence algorithms easily fall into local optimization and low search accuracy, the improvement of the FaCO algorithm adjusts the weight of iterative location selection and updates the location. Experimental results on publicly available datasets such as the Oliver30 dataset and the eil51 dataset demonstrated the effectiveness of the FaCO algorithm. It is also significantly better than the commonly used firefly algorithm and other algorithms in terms of the search results and efficiency and achieves better results in optimizing the load-balancing problem of parallel computing.
6
Ahmed, Nesreen, i Ryan Rossi. "Interactive Visual Graph Analytics on the Web". Proceedings of the International AAAI Conference on Web and Social Media 9, nr 1 (3.08.2021): 566–69. http://dx.doi.org/10.1609/icwsm.v9i1.14653.
Pełny tekst źródłaStreszczenie:
We present a web-based network visual analytics platform called GraphVis that combines interactive visualizations with analytic techniques to reveal important patterns and insights for sense making, reasoning, and decision-making. The platform is designed with simplicity in mind and allows users to visualize and explore networks in seconds with a simple drag-and-drop of a graph file into the web browser. GraphVis is fast and flexible, web-based, requires no installation, while supporting a wide range of graph formats as well as state-of-the-art visualization and analytic techniques. In particular, the multi-level network analysis engine of GraphVis gives rise to a variety of new possibilities for exploring, analyzing, and understanding complex networks interactively in real-time. Finally, we also highlight other key aspects including filtering, querying, ranking, manipulating, exporting, partitioning (community/role discovery), as well as tools for dynamic network analysis and visualization, interactive graph generators (including two new block model approaches), and a variety of multi-level network analysis and statistical techniques.
7
Wan, Xinchen, Kaiqiang Xu, Xudong Liao, Yilun Jin, Kai Chen i Xin Jin. "Scalable and Efficient Full-Graph GNN Training for Large Graphs". Proceedings of the ACM on Management of Data 1, nr 2 (13.06.2023): 1–23. http://dx.doi.org/10.1145/3589288.
Pełny tekst źródłaStreszczenie:
Graph Neural Networks (GNNs) have emerged as powerful tools to capture structural information from graph-structured data, achieving state-of-the-art performance on applications such as recommendation, knowledge graph, and search. Graphs in these domains typically contain hundreds of millions of nodes and billions of edges. However, previous GNN systems demonstrate poor scalability because large and interleaved computation dependencies in GNN training cause significant overhead in current parallelization methods. We present G3, a distributed system that can efficiently train GNNs over billion-edge graphs at scale. G3 introduces GNN hybrid parallelism which synthesizes three dimensions of parallelism to scale out GNN training by sharing intermediate results peer-to-peer in fine granularity, eliminating layer-wise barriers for global collective communication or neighbor replications as seen in prior works. G3 leverages locality-aware iterative partitioning and multi-level pipeline scheduling to exploit acceleration opportunities by distributing balanced workload among workers and overlapping computation with communication in both inter-layer and intra-layer training processes. We show via a prototype implementation and comprehensive experiments that G3 can achieve as much as 2.24x speedup in a 16-node cluster, and better final accuracy over prior works.
8
Deepthy, Dinesan, i Joseph Varghese Kureethara. "INDUCED \(nK_{2}\) DECOMPOSITION OF INFINITE SQUARE GRIDS AND INFINITE HEXAGONAL GRIDS". Ural Mathematical Journal 8, nr 1 (29.07.2022): 23. http://dx.doi.org/10.15826/umj.2022.1.003.
Pełny tekst źródłaStreszczenie:
The induced \(nK_2\) decomposition of infinite square grids and hexagonal grids are described here. We use the multi-level distance edge labeling as an effective technique in the decomposition of square grids. If the edges are adjacent, then their color difference is at least 2 and if they are separated by exactly a single edge, then their colors must be distinct. Only non-negative integers are used for labeling. The proposed partitioning technique per the edge labels to get the induced \(nK_2\) decomposition of the ladder graph is the square grid and the hexagonal grid.
9
Drummond, C. "Accelerating Reinforcement Learning by Composing Solutions of Automatically Identified Subtasks". Journal of Artificial Intelligence Research 16 (1.02.2002): 59–104. http://dx.doi.org/10.1613/jair.904.
Pełny tekst źródłaStreszczenie:
This paper discusses a system that accelerates reinforcement learning by using transfer from related tasks. Without such transfer, even if two tasks are very similar at some abstract level, an extensive re-learning effort is required. The system achieves much of its power by transferring parts of previously learned solutions rather than a single complete solution. The system exploits strong features in the multi-dimensional function produced by reinforcement learning in solving a particular task. These features are stable and easy to recognize early in the learning process. They generate a partitioning of the state space and thus the function. The partition is represented as a graph. This is used to index and compose functions stored in a case base to form a close approximation to the solution of the new task. Experiments demonstrate that function composition often produces more than an order of magnitude increase in learning rate compared to a basic reinforcement learning algorithm.
10
Li, Zhi Yong, i Yun Ping Ai. "Study on the Multi-Core DSP Parallel Processing of Polarization Images Registration". Advanced Materials Research 756-759 (wrzesień 2013): 3532–36. http://dx.doi.org/10.4028/www.scientific.net/amr.756-759.3532.
Pełny tekst źródłaStreszczenie:
Three-channel polarization images must be registered before pixel-level fusion processing to acquire accurate polarization characteristics information. In the condition of serial processing, the image registration efficiency is bad, and then the real-time of polarization imaging application is poor. The multi-core DSP chip which type is TMS320C6670 is selected as the polarization images processing platform. Fourier-Mellin Transform (FMT) is selected as the registration algorithm. The parallel processing of the polarization image registration is studied based on data flow model. The hierarchical task graph is designed in the parallel processing tasks partitioning. According to processing performance and functions, four DSP cores and two FFT coprocessors are divided into different processor groups in each task processing stage. Same hierarchical tasks are assigned to each processor group. According to principles including load balancing and reducing inter-processor communication, algorithms and data of each hierarchical task are assigned manually to each processing unit in the processor group. Experimental results show that the average processing time is 0.429 second while the average registration accuracy achieves 0.5 pixel, the propose parallel processing method improves the efficiency of the polarization image registration.
11
Anisimov, Vladimir, Natalya Nesterova i Sergey Goncharuk. "DESIGNING A MULTIMODAL TRANSPORT NETWORK". Bulletin of scientific research results, nr 4 (17.12.2017): 41–51. http://dx.doi.org/10.20295/2223-9987-2017-4-41-51.
Pełny tekst źródłaStreszczenie:
Objective: To create a methodology for designing a multimodal transport network under various scenarios of socioeconomic development of the Russian Federation and its regions which take into account the influence of factors that create initial-information indeterminacy in decisionmaking. Methods: System theory, partitioning principle, theory of sets, theory of probability and mathematical statistics, basics of information theory, graph theory and reliability theory; as well as methods of system analysis, mathematic simulation of processes and systems, mathematical logic, decision-making, dynamical programming, multi-objective optimization, economic evaluation of efficiency of design solutions were applied. Results: The authors developed and proposed a concept for designing methodology of multimodal transport networks, systemic presentation of multimodal transport networks, four-level partitioning and set-theoretical presentation of multimodal transport networks layout, mathematical simulation of multimodal transport network development strategy which takes into account the scenario of socioeconomic development of a region under study, balanced system of indices for evaluation of multimodal transport network development strategy and managing the trajectory of change of its layout and capacity in accordance with set strategic objectives, method for forming layout of multimodal transport network, method for forming a variety of possible strategies of gradual changing of layout and capacity of multimodal transport network objects, method for forming an area of efficient multimodal transport network development strategies, technology for decision-makers’ work with efficient strategy area for decision-making. Practical relevance: This methodology can be used in investment evaluation and technical and economic feasibility study of strategies of multimodal transport networks’ layout and capacity change strategies as an aggregate of multimodal transport corridors designed with the purpose of implementation of strategic tasks of development of a country’s single transport network.
12
Sahebi, Amin, Marco Barbone, Marco Procaccini, Wayne Luk, Georgi Gaydadjiev i Roberto Giorgi. "Distributed large-scale graph processing on FPGAs". Journal of Big Data 10, nr 1 (4.06.2023). http://dx.doi.org/10.1186/s40537-023-00756-x.
Pełny tekst źródłaStreszczenie:
AbstractProcessing large-scale graphs is challenging due to the nature of the computation that causes irregular memory access patterns. Managing such irregular accesses may cause significant performance degradation on both CPUs and GPUs. Thus, recent research trends propose graph processing acceleration with Field-Programmable Gate Arrays (FPGA). FPGAs are programmable hardware devices that can be fully customised to perform specific tasks in a highly parallel and efficient manner. However, FPGAs have a limited amount of on-chip memory that cannot fit the entire graph. Due to the limited device memory size, data needs to be repeatedly transferred to and from the FPGA on-chip memory, which makes data transfer time dominate over the computation time. A possible way to overcome the FPGA accelerators’ resource limitation is to engage a multi-FPGA distributed architecture and use an efficient partitioning scheme. Such a scheme aims to increase data locality and minimise communication between different partitions. This work proposes an FPGA processing engine that overlaps, hides and customises all data transfers so that the FPGA accelerator is fully utilised. This engine is integrated into a framework for using FPGA clusters and is able to use an offline partitioning method to facilitate the distribution of large-scale graphs. The proposed framework uses Hadoop at a higher level to map a graph to the underlying hardware platform. The higher layer of computation is responsible for gathering the blocks of data that have been pre-processed and stored on the host’s file system and distribute to a lower layer of computation made of FPGAs. We show how graph partitioning combined with an FPGA architecture will lead to high performance, even when the graph has Millions of vertices and Billions of edges. In the case of the PageRank algorithm, widely used for ranking the importance of nodes in a graph, compared to state-of-the-art CPU and GPU solutions, our implementation is the fastest, achieving a speedup of 13 compared to 8 and 3 respectively. Moreover, in the case of the large-scale graphs, the GPU solution fails due to memory limitations while the CPU solution achieves a speedup of 12 compared to the 26x achieved by our FPGA solution. Other state-of-the-art FPGA solutions are 28 times slower than our proposed solution. When the size of a graph limits the performance of a single FPGA device, our performance model shows that using multi-FPGAs in a distributed system can further improve the performance by about 12x. This highlights our implementation efficiency for large datasets not fitting in the on-chip memory of a hardware device.
13
Schlag, Sebastian, Tobias Heuer, Lars Gottesbüren, Yaroslav Akhremtsev, Christian Schulz i Peter Sanders. "High-Quality Hypergraph Partitioning". ACM Journal of Experimental Algorithmics, 21.04.2022. http://dx.doi.org/10.1145/3529090.
Pełny tekst źródłaStreszczenie:
Hypergraphs are a generalization of graphs where edges (aka nets ) are allowed to connect more than two vertices. They have a similarly wide range of applications as graphs. This paper considers the fundamental and intensively studied problem of balanced hypergraph partitioning , which asks for partitioning the vertices into k disjoint blocks of bounded size while minimizing an objective function over the hyperedges. Here, we consider the two most commonly used objectives: the cut-net metric and the connectivity metric . We describe our open source hypergraph partitioner KaHyPar which is based on the successful multi-level approach – driving it to the extreme of using one level for (almost) every vertex. Using carefully designed data structures and dynamic update techniques, this approach turns out to have a very good time–quality tradeoff. We present two preprocessing techniques – pin sparsification using locality sensitive hashing and community detection based on the Louvain algorithm . The community structure is used to guide the coarsening process that incrementally contracts vertices. Portfolio-based partitioning of the contracted hypergraph then already achieves a good initial solution. While reversing the contraction process, a combination of several refinement techniques achieves a good final partitioning. In particular, we support a highly-localized local search that can directly produce a k -way partitioning and complement this with flow-based techniques that take a more global view. Optionally, a memetic algorithm evolves a pool of solution candidates to an overall good solution. We evaluate KaHyPar for a large set of instances from a wide range of application domains. With respect to quality, KaHyPar outperforms all previously considered systems that can handle large hypergraphs such as hMETIS, PaToH, Mondriaan, or Zoltan. Somewhat surprisingly, to some extend, this even extends to graph partitioners such as KaHIP when considering the special case of graphs. KaHyPar is also faster than most of these systems except for PaToH which represents a different speed–quality tradeoff.
14
Kaur, Mandeep, Sanjay Kadam i Naeem Hannoon. "Multi-level parallel scheduling of dependent-tasks using graph-partitioning and hybrid approaches over edge-cloud". Soft Computing, 9.04.2022. http://dx.doi.org/10.1007/s00500-022-07048-1.
Pełny tekst źródła
15
Corvello, Vincenzo, Roberto Musmanno, Giuseppe Pavone, Francesco Santoro i Francesca Vocaturo. "Optimization and public transport tendering: a case study in Southern Italy". Public Transport, 11.04.2023. http://dx.doi.org/10.1007/s12469-023-00324-9.
Pełny tekst źródłaStreszczenie:
AbstractThis article presents a multi-start heuristic approach to a design problem motivated by a real-world application in the Italian transport system. Specifically, it focuses on the problem of designing optimal lots in the public transport organization. In defining lots (in terms of number, size, and boundaries) both cost and service level have to be considered. Under certain assumptions, we model the problem as a graph partitioning problem and consider the same performance measure indicated by the relevant decree-law enacted by the Italian Ministry of Transport. The multi-start algorithm proposed for individuating high-quality solutions for the problem uses adaptive large neighbourhood search. The results of a computational study based on real data from a region in Southern Italy are reported.