检索结果-内蒙古大学图书馆

Linear-Time Multilevel graph Partitioning via Edge Sparsification

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Gottesbüren, Lars Maas, Nikolai Rosch, Dominik Sanders, Peter Seemaier, Daniel Google Research Zürich Switzerland Karlsruhe Institute of Technology Karlsruhe Germany

The current landscape of balanced graph partitioning is divided into high-quality but expensive multilevel algorithms and cheaper approaches with linear running time, such as single-level algorithms and streaming algorithms. We demonstrate how to achieve the best of both worlds with a linear time multilevel algorithm. Multilevel algorithms construct a hierarchy of increasingly smaller graphs by repeatedly contracting clusters of nodes. Our approach preserves their distinct advantage, allowing refinement of the partition over multiple levels with increasing detail. At the same time, we use edge sparsification to guarantee geometric size reduction between the levels and thus linear running time. We provide a proof of the linear running time as well as additional insights into the behavior of multilevel algorithms, showing that graphs with low modularity are most likely to trigger worst-case running time. We evaluate multiple approaches for edge sparsification and integrate our algorithm into the state-of-the-art multilevel partitioner KaMinPar, maintaining its excellent parallel scalability. As demonstrated in detailed experiments, this results in a 1.49× average speedup (up to 4× for some instances) with only 1% loss in solution quality. Moreover, our algorithm clearly outperforms state-of-the-art single-level and streaming approaches. © 2025, CC BY.

关键词： graph algorithms

MAINTAINING SHORTEST PATHS UNDER DELETIONS IN WEIGHTED DIRECTED graphS

学校读者我要写书评

暂无评论

SIAM JOURNAL ON COMPUTING 2016年第2期45卷 548-574页

作者： Bernstein, Aaron Columbia Univ Dept Comp Sci New York NY 10027 USA

We present an improved algorithm for maintaining all-pairs (1 + epsilon) approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem is total update time (O) over tilde (n(2)root m/epsilon) over all updates for directed unweighted graphs [ S. Baswana, R. Hariharan, and S. Sen, J. algorithms, 62 (2007), pp. 74-92], and (O) over tilde (mn/epsilon) for undirected unweighted graphs [ L. Roditty and U. Zwick, in Proceedings of the 45th FOCS, Rome, Italy, 2004, pp. 499-508]. Both algorithms are randomized and have constant query time. Very recently, Henzinger, Krinninger, and Nanongkai presented a deterministic version of the latter algorithm [ M. Henzinger, S. Krinninger, and D. Nanongkai, in IEEE FOCS, 2013, pp. 538-547]. Note that (O) over tilde (mn) is a natural barrier because even with a (1 + epsilon) approximation, there is no o(mn) combinatorial algorithm for the static all-pairs shortest path problem. Our algorithm works on directed weighted graphs and has total (randomized) update time (O) over tilde (mn log R/epsilon) where R is the ratio of the largest edge weight to appear at any point in the update sequence to the smallest such weight. (As with previous algorithms, our query time is constant.) Technically, the running time is (O) over tilde (mn log R/epsilon) + O(Delta), where Delta is the total number of updates;the same O(Delta) term is also implicitly present in all other algorithms for the problem, since a constant time per update is clearly unavoidable. Note that log R = O(log(n)) as long as weights are polynomial in n;thus, we effectively expand the (O) over tilde (mn/epsilon) total update time bound from undirected unweighted graphs to directed graphs with polynomial weights. This is in fact the first nontrivial algorithm for decremental all-pairs shortest paths that works on weighted graphs (previous algorithms could only handle small integer weights). By a well-known reduction from decremental algo

关键词： graph algorithms dynamic algorithms approximation shortest paths

The Case for External graph Sketching

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bender, Michael A. Farach-Colton, Martín Jacob, Riko Komlós, Hanna Tench, David West, Evan T. Stony Brook University United States RelationalAI United States New York University United States IT University of Copenhagen Denmark Lawrence Berkeley National Laboratory United States

algorithms in the data stream model use $O(polylog(N))$ space to compute someproperty of an input of size $N$, and many of these algorithms are implementedand used in practice. However, sketching algorithms in the graph semi-streamingmodel use $O(V polylog(V))$ space for a $V$-vertex graph, and the fact thatimplementations of these algorithms are not used in the academic literature orin industrial applications may be because this space requirement is too largefor RAM on today\'s hardware. In this paper we introduce the external semi-streaming model, which addressesthe aspects of the semi-streaming model that limit its practical impact. Inthis model, the input is in the form of a stream and $O(V polylog(V))$ space isavailable, but most of that space is accessible only via block I/O operationsas in the external memory model. The goal in the external semi-streaming modelis to simultaneously achieve small space and low I/O cost. We present a general transformation from any vertex-based sketch algorithm toone which has a low sketching cost in the new model. We prove that thisautomatic transformation is tight or nearly (up to a $O(\\log(V))$ factor) tightvia an I/O lower bound for the task of sketching the input stream. Using this transformation and other techniques, we present externalsemi-streaming algorithms for connectivity, bipartiteness testing,$(1+\\epsilon)$-approximating MST weight, testing k-edge connectivity,$(1+\\epsilon)$-approximating the minimum cut of a graph, computing$\\epsilon$-cut sparsifiers, and approximating the density of the densestsubgraph. These algorithms all use $O(V poly(\\log(V), \\epsilon^{-1},k)$ *** many of these problems, our external semi-streaming algorithms outperformthe state of the art algorithms in both the sketching and external-memorymodels. © 2025, CC BY.

关键词： graph algorithms

Faster algorithms for graph Monopolarity

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Philip, Geevarghese Sridhara, Shrinidhi Teganahally Chennai Mathematical Institute India UMI ReLaX France Univ. Bordeaux CNRS Bordeaux INP LaBRI UMR 5800 TalenceF-33400 France

A graph G = (V, E) is said to be monopolar if its vertex set admits a partition V = (C (Equation presented) I) where G[C] is a cluster graph and I is an independent set in G. Monopolar graphs generalize both bipartite graphs and split graphs, and they have been extensively studied from both graph-theoretic and algorithmic points of view. In this work we focus on the problem Monopolar Recognition of deciding whether a given graph is monopolar. Monopolar Recognition is known to be solvable in polynomial time in certain classes of graphs such as cographs and claw-free graphs, and to be NP-hard in various restricted classes such as subcubic planar graphs. We initiate the study of exact exponential-time algorithms for Monopolar Recognition and allied problems. We design an algorithm that solves Monopolar Recognition in O★(1.3734n) time on input graphs with n vertices. In fact we solve the more general problems Monopolar Extension and List Monopolar Partition, which were introduced in the literature as part of the study of graph monopolarity, in O★(1.3734n) time. We also design fast parameterized algorithms for Monopolar Recognition using two notions of distance from triviality as the parameters. Our FPT algorithms solve Monopolar Recognition in O★(3.076kv) and O★(2.253ke) time, where kv and ke are, respectively, the sizes of the smallest claw-free vertex and edge deletion sets of the input graph. These results are a significant addition to the small number of FPT algorithms currently known for Monopolar Recognition. Le and Nevries have shown that if a graph G is chair-free, then an instance (G, C′) of Monopolar Extension can be solved in polynomial time for any subset C′ of its vertices. We significantly generalize this result;we show that we can solve instances (G, C′) of Monopolar Extension in polynomial time for arbitrary graphs G and any chair-free vertex deletion set C′ of G. This result is the starting point of all our fast algorithms for Monopolar Extension, and w

关键词： graph algorithms

Coded Computing for Distributed graph Analytics

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON INFORMATION THEORY 2020年第10期66卷 6534-6554页

作者： Prakash, Saurav Reisizadeh, Amirhossein Pedarsani, Ramtin Avestimehr, Amir Salman Univ Southern Calif Dept Elect & Comp Engn Los Angeles CA 90089 USA Univ Calif Santa Barbara Dept Elect & Comp Engn Santa Barbara CA 93106 USA

Many distributed computing systems have been developed recently for implementing graph based algorithms such as PageRank over large-scale graph-structured datasets such as social networks. Performance of these systems significantly suffers from communication bottleneck as a large number of messages are exchanged among servers at each step of the computation. Motivated by graph based MapReduce, we propose a coded computing framework that leverages computation redundancy to alleviate the communication bottleneck in distributed graph processing. As a key contribution of this work, we develop a novel coding scheme that systematically injects structured redundancy in the computation phase to enable coded multicasting opportunities during message exchange between servers, reducing the communication load substantially in large-scale graph processing. For theoretical analysis, we consider random graph models, and focus on schemes in which subgraph allocation and Reduce allocation are only dependent on vertex ID while the Shuffle design varies with graph connectivity. Specifically, we prove that our proposed scheme enables an (asymptotically) inverse-linear trade-off between computation load and average communication load for two popular random graph models - Erdos-Renyi model, and power law model. Particularly, for a given computation load r, (i.e. when each graph vertex is carefully stored at r servers), the proposed scheme slashes the average communication load by (nearly) a multiplicative factor of r. Furthermore, for the Erdos-Renyi model, we prove that our proposed scheme is optimal asymptotically as the graph size increases by providing an information-theoretic converse. To illustrate the benefits of our scheme in practice, we implement PageRank over Amazon EC2, using artificial as well as real-world datasets, demonstrating gains of up to 50.8% in comparison to the conventional PageRank implementation. Additionally, we specialize our coded scheme and extend our theore

关键词： Servers Load modeling Computational modeling Resource management Adaptation models Redundancy Encoding Coded computation distributed computing graph algorithms MapReduce PageRank

Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2006年第9期28卷 1393-1403页

作者： Lafon, Stephane Lee, Ann B. Google Inc Mountain View CA 94043 USA Carnegie Mellon Univ Dept Stat Pittsburgh PA 15213 USA

We provide evidence that nonlinear dimensionality reduction, clustering, and data set parameterization can be solved within one and the same framework. The main idea is to define a system of coordinates with an explicit metric that reflects the connectivity of a given data set and that is robust to noise. Our construction, which is based on a Markov random walk on the data, offers a general scheme of simultaneously reorganizing and subsampling graphs and arbitrarily shaped data sets in high dimensions using intrinsic geometry. We show that clustering in embedding spaces is equivalent to compressing operators. The objective of data partitioning and clustering is to coarse-grain the random walk on the data while at the same time preserving a diffusion operator for the intrinsic geometry or connectivity of the data set up to some accuracy. We show that the quantization distortion in diffusion space bounds the error of compression of the operator, thus giving a rigorous justification fork-means clustering in diffusion space and a precise measure of the performance of general clustering algorithms.

关键词： machine learning text analysis knowledge retrieval quantization graph-theoretic methods compression (coding) clustering clustering similarity measures information visualization Markov processes graph algorithms

Experimental comparison of graph-based approximate nearest neighbor search algorithms on edge devices

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Ganbarov, Ali Yuan, Jicheng Le-Tuan, Anh Hauswirth, Manfred Le-Phuoc, Danh Open Distributed Systems Technical University of Berlin Germany Fraunhofer Institute for Open Communication Systems Berlin Germany

In this paper, we present an experimental comparison of various graph-based approximate nearest neighbor (ANN) search algorithms deployed on edge devices for real-time nearest neighbor search applications, such as smart city infrastructure and autonomous vehicles. To the best of our knowledge, this specific comparative analysis has not been previously conducted. While existing research has explored graph-based ANN algorithms, it has often been limited to single-threaded implementations on standard commodity hardware. Our study leverages the full computational and storage capabilities of edge devices, incorporating additional metrics such as insertion and deletion latency of new vectors and power consumption. This comprehensive evaluation aims to provide valuable insights into the performance and suitability of these algorithms for edge-based real-time tracking systems enhanced by nearest-neighbor search algorithms. © 2024, CC BY.

关键词： graph algorithms

Listing all potential maximal cliques of a graph

学校读者我要写书评

暂无评论

THEORETICAL COMPUTER SCIENCE 2002年第1-2期276卷 17-32页

作者： Bouchitté, V Todinca, I Ecole Normale Super Lyon LIP UMR 5668 F-69364 Lyon 07 France

A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-in are polynomially tractable for these graphs. We show here that the potential maximal cliques of a graph can be generated in polynomial time in the number of minimal separators of the graph. Thus, the treewidth and the minimum fill-in are polynomially tractable for all classes of graphs with a polynomial number of minimal separators. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： graph algorithms treewidth minimal separators potential maximal cliques

学校读者我要写书评

暂无评论

SIAM REVIEW 2004年第4期46卷 647-666页

作者： Blondel, VD Gajardo, A Heymans, M Senellart, P Van Dooren, P Catholic Univ Louvain Div Appl Math B-1348 Louvain Belgium Univ Concepcion Dept Ingn Matemat Concepcion Chile Google Inc Mountain View CA 94043 USA Ecole Normale Super Dept Comp Sci F-75230 Paris 05 France

We introduce a concept of similarity between vertices of directed graphs. Let CA and G(B) be two directed graphs with, respectively, n(A) and n(B) vertices. We define an n(B) x n(A) similarity matrix S whose real entry s(ij) expresses how similar vertex j (in G(A)) is to vertex i (in G(B)): we say that s(ij) is their similarity score. The similarity matrix can be obtained as the limit of the normalized even iterates of Sk+1 = BS(k)A(T) + B(T)S(k)A, where A and B are adjacency matrices of the graphs and So is a matrix whose entries are all equal to 1. In the special case where G(A) = G(B) = G, the matrix S is square and the score s(ij) is the similarity score between the vertices i and j of G. We point out that Klemberg's "hub and authority" method to identify web-pages relevant to a given query can be viewed as a special case of our definition in the case where one of the graphs has two vertices and a unique directed edge between them. In analogy to Kleinberg, we show that our similarity scores are given by the components of a dominant eigenvector of a nonnegative matrix. Potential applications of our similarity concept are numerous. We illustrate an application for the automatic extraction of synonyms in a monolingual dictionary.

关键词： algorithms graph algorithms graph theory eigenvalues of graphs