Bibliographies thématiques / Sparsification de graphe

Sommaire

Articles de revues
Thèses
Chapitres de livres
Actes de conférences

Littérature scientifique sur le sujet « Sparsification de graphe »

Auteur : Grafiati

Publié le 25 janvier 2025

Créez une référence correcte selon les styles APA, MLA, Chicago, Harvard et plusieurs autres

Choisissez une source :

Consultez les listes thématiques d’articles de revues, de livres, de thèses, de rapports de conférences et d’autres sources académiques sur le sujet « Sparsification de graphe ».

À côté de chaque source dans la liste de références il y a un bouton « Ajouter à la bibliographie ». Cliquez sur ce bouton, et nous générerons automatiquement la référence bibliographique pour la source choisie selon votre style de citation préféré : APA, MLA, Harvard, Vancouver, Chicago, etc.

Vous pouvez aussi télécharger le texte intégral de la publication scolaire au format pdf et consulter son résumé en ligne lorsque ces informations sont inclues dans les métadonnées.

Articles de revues sur le sujet "Sparsification de graphe"

Chen, Yuhan, Haojie Ye, Sanketh Vedula, Alex Bronstein, Ronald Dreslinski, Trevor Mudge et Nishil Talati. « Demystifying Graph Sparsification Algorithms in Graph Properties Preservation ». Proceedings of the VLDB Endowment 17, n^o 3 (novembre 2023) : 427–40. http://dx.doi.org/10.14778/3632093.3632106.

Texte intégral

Résumé :

Graph sparsification is a technique that approximates a given graph by a sparse graph with a subset of vertices and/or edges. The goal of an effective sparsification algorithm is to maintain specific graph properties relevant to the downstream task while minimizing the graph's size. Graph algorithms often suffer from long execution time due to the irregularity and the large real-world graph size. Graph sparsification can be applied to greatly reduce the run time of graph algorithms by substituting the full graph with a much smaller sparsified graph, without significantly degrading the output quality. However, the interaction between numerous sparsifiers and graph properties is not widely explored, and the potential of graph sparsification is not fully understood. In this work, we cover 16 widely-used graph metrics, 12 representative graph sparsification algorithms, and 14 real-world input graphs spanning various categories, exhibiting diverse characteristics, sizes, and densities. We developed a framework to extensively assess the performance of these sparsification algorithms against graph metrics, and provide insights to the results. Our study shows that there is no one sparsifier that performs the best in preserving all graph properties, e.g. sparsifiers that preserve distance-related graph properties (eccentricity) struggle to perform well on Graph Neural Networks (GNN). This paper presents a comprehensive experimental study evaluating the performance of sparsification algorithms in preserving essential graph metrics. The insights inform future research in incorporating matching graph sparsification to graph algorithms to maximize benefits while minimizing quality degradation. Furthermore, we provide a framework to facilitate the future evaluation of evolving sparsification algorithms, graph metrics, and ever-growing graph data.

Styles APA, Harvard, Vancouver, ISO, etc.

Parchas, Panos, Nikolaos Papailiou, Dimitris Papadias et Francesco Bonchi. « Uncertain Graph Sparsification ». IEEE Transactions on Knowledge and Data Engineering 30, n^o 12 (1 décembre 2018) : 2435–49. http://dx.doi.org/10.1109/tkde.2018.2819651.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Batson, Joshua, Daniel A. Spielman, Nikhil Srivastava et Shang-Hua Teng. « Spectral sparsification of graphs ». Communications of the ACM 56, n^o 8 (août 2013) : 87–94. http://dx.doi.org/10.1145/2492007.2492029.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Spielman, Daniel A., et Shang-Hua Teng. « Spectral Sparsification of Graphs ». SIAM Journal on Computing 40, n^o 4 (janvier 2011) : 981–1025. http://dx.doi.org/10.1137/08074489x.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Li, Jiayu, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad et Reza Zafarani. « Graph sparsification with graph convolutional networks ». International Journal of Data Science and Analytics 13, n^o 1 (13 octobre 2021) : 33–46. http://dx.doi.org/10.1007/s41060-021-00288-8.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Sun, He, et Luca Zanetti. « Distributed Graph Clustering and Sparsification ». ACM Transactions on Parallel Computing 6, n^o 3 (5 décembre 2019) : 1–23. http://dx.doi.org/10.1145/3364208.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Spielman, Daniel A., et Nikhil Srivastava. « Graph Sparsification by Effective Resistances ». SIAM Journal on Computing 40, n^o 6 (janvier 2011) : 1913–26. http://dx.doi.org/10.1137/080734029.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Danciu, Daniel, Mikhail Karasikov, Harun Mustafa, André Kahles et Gunnar Rätsch. « Topology-based sparsification of graph annotations ». Bioinformatics 37, Supplement_1 (1 juillet 2021) : i169—i176. http://dx.doi.org/10.1093/bioinformatics/btab330.

Texte intégral

Résumé :

Abstract Motivation Since the amount of published biological sequencing data is growing exponentially, efficient methods for storing and indexing this data are more needed than ever to truly benefit from this invaluable resource for biomedical research. Labeled de Bruijn graphs are a frequently-used approach for representing large sets of sequencing data. While significant progress has been made to succinctly represent the graph itself, efficient methods for storing labels on such graphs are still rapidly evolving. Results In this article, we present RowDiff, a new technique for compacting graph labels by leveraging expected similarities in annotations of vertices adjacent in the graph. RowDiff can be constructed in linear time relative to the number of vertices and labels in the graph, and in space proportional to the graph size. In addition, construction can be efficiently parallelized and distributed, making the technique applicable to graphs with trillions of nodes. RowDiff can be viewed as an intermediary sparsification step of the original annotation matrix and can thus naturally be combined with existing generic schemes for compressed binary matrices. Experiments on 10 000 RNA-seq datasets show that RowDiff combined with multi-BRWT results in a 30% reduction in annotation footprint over Mantis-MST, the previously known most compact annotation representation. Experiments on the sparser Fungi subset of the RefSeq collection show that applying RowDiff sparsification reduces the size of individual annotation columns stored as compressed bit vectors by an average factor of 42. When combining RowDiff with a multi-BRWT representation, the resulting annotation is 26 times smaller than Mantis-MST. Availability and implementation RowDiff is implemented in C++ within the MetaGraph framework. The source code and the data used in the experiments are publicly available at https://github.com/ratschlab/row_diff.

Styles APA, Harvard, Vancouver, ISO, etc.

Fung, Wai-Shing, Ramesh Hariharan, Nicholas J. A. Harvey et Debmalya Panigrahi. « A General Framework for Graph Sparsification ». SIAM Journal on Computing 48, n^o 4 (janvier 2019) : 1196–223. http://dx.doi.org/10.1137/16m1091666.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Broutin, Nicolas, Luc Devroye et Gábor Lugosi. « Almost optimal sparsification of random geometric graphs ». Annals of Applied Probability 26, n^o 5 (octobre 2016) : 3078–109. http://dx.doi.org/10.1214/15-aap1170.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Plus de sources

Thèses sur le sujet "Sparsification de graphe"

Petit, Claude. « E︠́chantillonnage de données : acquisition comprimée et réduction de graphe ». Electronic Thesis or Diss., Université de Rennes (2023-....), 2024. http://www.theses.fr/2024URENS049.

Texte intégral

Résumé :

Dans cette thèse, nous étudions trois aspects du problème de réduction de la dimension. Le premier concerne la compression de base de données. Nous proposons plusieurs algorithmes d’échantillonnage préservant l’information contenue dans les données, ainsi que deux applications au conditionnement de matrices et à l’acquisition comprimée. Ces algorithmes sont déterministes et leur faible complexité en font une alternative intéressante aux meilleurs algorithmes connus. Le second aspect abordé concerne la sparsification de graphe. Nous proposons de réduire le nombre d’arêtes d’un graphe tout en préservant sa connectivité. Nous élaborons deux algorithmes itératifs, déterministes et de faible complexité, permettant d’approcher la solution de ce problème NP-difficile. Nous présentons également une application possible à la simplification du graphe sous-jacent à un réseau neuronal sur graphe. La troisième partie de la thèse traite d’acquisition comprimée et propose une analyse statistique d’un algorithme de reconstruction de signaux parcimonieux. Dans le cadre d’un modèle asymptotique où la matrice de mesure et le signal sont aléatoires et pour lequel les paramètres de taille tendent vers l’infini à la même vitesse, nous montrons que la probabilité de succès à une itération donnée tend vers 1
In this thesis, we study three aspects of the dimensionality reduction problem. The first concerns database compression. We propose several sampling algorithms that preserve the information contained in the data, along with two applications in matrix conditioning and compressive sensing. These algorithms are deterministic, and their low complexity makes them an interesting alternative to the state-of-the-art algorithms. The second aspect addressed is graph reduction. We aim to reduce the number of edges, while attempting to preserve the graph’s connectivity. We develop two iterative, deterministic, and low-complexity algorithms that approximate the solution to this NP-hard problem. We also present a possible application in simplifying the underlying graph of a Graph Neural Network. The third part of the thesis deals with compressive sensing and provides a statistical analysis of a reconstruction algorithm for sparse signals. In the context of an asymptotic model where both the measurement matrix and the sparse signal are random, and the size parameters tend to infinity at the same rate, we show that the probability of success at a given iteration tends to 1

Styles APA, Harvard, Vancouver, ISO, etc.

Shah, Shivani. « Graph sparsification and unsupervised machine learning for metagenomic binning ». Thesis, Tours, 2019. http://theses.scd.univ-tours.fr/index.php?fichier=2019/shivani.shah_18225.pdf.

Texte intégral

Résumé :

La métagénomique est le domaine de la biologie qui concerne l’étude du contenu génomique des communautés microbiennes directement dans leur environnement. Les données métagénomiques utilisées dans ces travaux de thèse correspondent à des technologies de séquençage produisant des fragments d’ADN courts (reads). L'une des étapes clé de l'analyse des données métagénomiques et développée dans cette étude est le regroupement de reads, appelé également binning. Lors de cette tâche de binning, des groupes (bins) doivent être formés de sorte que chaque groupe soit composé de reads provenant de la même espèce ou genre. La méthodologie traditionnelle consiste à effectuer cette étape sur des séquences plus grandes (contigs), mais cette étape génère potentiellement des séquences dites chimériques. L'un des problèmes liés au binning appliqué aux lectures est lié à la taille importante des jeux de données. La méthodologie traditionnelle appliquée sur les reads, accable les ressources de calcul. Par conséquent, il est nécessaire de développer des approches de binning adaptables à de données massives.Dans cette thèse, nous abordons ce problème en proposant une méthode évolutive pour effectuer le binning. Nous positionnons notre travail parmi les approches de binning basées sur la composition et dans un contexte totalement non supervisé. Afin de réduire la complexité de la tâche de binning, des méthodes sont proposées pour filtrer préalablement les associations entre les données. Le développement de l'approche a été réalisé en deux étapes. D'abord, la méthodologie a été évaluée sur des ensembles de données métagénomiques plus petits (composés de quelques milliers de points). Dans un deuxième temps, nous proposons d’adapter cette approche à des ensembles de données plus volumineux (composés de millions de points) avec des méthodes d’indexation sensibles à la similarité (LSH). La thèse comporte trois contributions majeures.Premièrement, nous proposons un ensemble varié d’algorithmes de filtrage d’associations entre les données (reads) par l’intermédiaire de graphes de proximité. Ces graphes de proximité sont construits pour capturer les relations les plus pertinentes entre reads pour la tâche de binning. Nous exploitons par suite des algorithmes de détection de communautés sur ces graphes pour identifier les groupes de reads d’intérêts. Une étude exploratoire a été réalisée avec plusieurs graphes de proximité et algorithmes de détection de communautés sur trois jeux de données métagénomiques. Suite à cette étude, nous proposons une approche pipeline nommée ProxiClust couplant la construction d’un graphe de type kNN et l’algorithme Louvain de détection de communautés.Deuxièmement, afin d’adresser le problème de la scalabilité et aborder des jeux de données plus volumineux, la matrice de similarité utilisée dans le pipeline est remplacée par l’exploitation de tables de hachage sensibles à la similarité d’intérêt construites à partir de l'approche LSH Sim-Hash. Nous introduisons deux stratégies pour construire des graphes de proximité à partir des tables de hachage: 1) le graphe des microclusters et 2) le graphe kNN approché. Les performances et les limites de ces graphes ont été évaluées sur de grands ensembles de données MC et discutées. Sur la base de cette étude, nous retenons le graphe kNN mutuels comme le graphe de proximité le plus approprié pour les grands ensembles de données. Cette proposition a également été évaluée et confirmée sur des données de séquences métagénomiques de référence issues du challenge international CAMI.Enfin, nous examinons des approches de hachage alternatives pour construire des tables de hachage de meilleures qualités. L’approche de hachage dépendante des données ITQ est introduite et exploitée, puis nous en proposons deux variantes : orthogonale (ITQ-OrthSH) et non orthogonale (ITQ-SH). Ces approches de hachage ont été évaluées et discutées sur les données de reads massives à disposition
Metagenomics is the field biology that relates to the study of genomic content of microbial communities directly in their natural environments. The metagenomic data is generated by sequencing technology that take the enviormental samples as the input. The generated data is composed of short fragments of DNA (called reads), which originate from genomes of all species present in the sample. The datasets size range from thousands to millions of reads. One of the steps of metagenomic data analysis is binning of the reads. In binning groups (called bins) are to be formed such that each group is composed of reads which are likely to originate from the same specie or specie family. It has essentially been treated as a task of clustering in the metagenomic literature. One of the challenges in binning occurs due to the large size of the datasets. The method overwhelms the computational resources required while performing the task. Hence the development of binning approaches which are scalable to large datasets is required.In this thesis, we address this issue by proposing a scalable method to perform binning. We position our work among the compositional based binning approaches (use of short kmers) and in completely unsupervised context. On order to decrease the complexity of the binning task, methods are proposed to perform sparsification of the data prior to clustering. The development of the approach has been performed in two steps. First the idea has been evaluated on smaller metagenomic datasets (composed of few thousands of points). In the second step, we propose to scale this approach to larger datasets (composed of Millions of points) with similarity based indexing methods (LSH approaches). There are three major contributions of the thesis.First, we propose the idea of performing sparsification of the data with proximity graphs, prior to clustering. The proximity graphs are built on the data to capture pair-wise relationships between data points that are relevant for clustering. Then we leverage community detection algorithms on these graphs to identify clusters from the data. An exploratory study has been performed with several proximity graphs and community detection algorithm on three metagenomic datasets. Based on this study we propose an approach named ProxiClust with KNN graph and Louvain community detection to perform binning.Second, to scale this approach to larger datasets the distance matrix in the pipeline is replaced with hash tables built from Sim-hash LSH approach. We introduce two strategies to build proximity graphs from the hash tables: 1) Microclusters graph and 2) Approximate k nearest neighbour graph. The performance of these graphs have been evaluated on large MC datasets. The performance and limitations of these graphs are discussed. The baseline evaluation of these datasets have also been performed to determine their clustering difficulty. Based on this study we propose Mutual-KNN graph to be the appropriate proximity graph for the large datasets. This proposal has also evaluated and confirmed on the CAMI benchmark metagenomic datasets.Lastly, we examine alternative hashing approaches to build better quality hash tables. A data-dependent hashing approach ITQ and orthogonal version of Sim-hash have been included. Two new data dependent hashing approaches named ITQ-SH and ITQ-OrthSH are introduced. All the hashing approaches have been evaluated w.r.t their ability to hash the MC datasets with high precision and recall. AndThe introduction of Mutual-KNN as the appropriate proximity graph has led to new challenges in the pipeline. First, large number of clusters are generated due to high number of components in the Mutual-KNN graph. So, in order to obtain appropriate number of clusters, a strategy needs to be devised to merge the similar clusters. Also an approach to build Mutual-KNN graph from hash tables needs to be designed. This would complete the ProxiClust pipeline for the large datasets

Styles APA, Harvard, Vancouver, ISO, etc.

Ortmann, Mark [Verfasser]. « Combinatorial Algorithms for Graph Sparsification / Mark Ortmann ». Konstanz : Bibliothek der Universität Konstanz, 2017. http://d-nb.info/1173616438/34.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Di, Jinchao. « Gene Co-expression Network Mining Using Graph Sparsification ». The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1367583964.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Machimada, Machaiah Chittiappa <1993&gt. « Graph Sparsification and Semi-Supervised Learning : an Experimental Study ». Master's Degree Thesis, Università Ca' Foscari Venezia, 2021. http://hdl.handle.net/10579/19404.

Texte intégral

Résumé :

This study focuses on comparing the various graph sparsification methods that have been devised and tests the efficiency when compared to one another. And on the latter side of the project, semi-supervised learning algorithms are trained on a combination of labeled and unlabeled data. Hence, different sparsification methods are explored and the effect of such methods in Semi Supervised Graph Based Algorithms are evaluated.

Styles APA, Harvard, Vancouver, ISO, etc.

Wang, Guan. « STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS ». Kent State University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Asathulla, Mudabir Kabir. « A Sparsification Based Algorithm for Maximum-Cardinality Bipartite Matching in Planar Graphs ». Thesis, Virginia Tech, 2017. http://hdl.handle.net/10919/88080.

Texte intégral

Résumé :

Matching is one of the most fundamental algorithmic graph problems. Many variants of matching problems have been studied on different classes of graphs, the one of special interest to us being the Maximum Cardinality Bipartite Matching in Planar Graphs. In this work, we present a novel sparsification based approach for computing maximum/perfect bipartite matching in planar graphs. The overall complexity of our algorithm is O(n^{6/5} log^2 {n}) where n is the number of vertices in the graph, bettering the O(n^{3/2}) time achieved independently by Hopcroft-Karp algorithm and by Lipton and Tarjan divide and conquer approach using planar separators. Our algorithm combines the best of both these standard algorithms along with our sparsification technique and rich planar graph properties to achieve the speed up. Our algorithm is not the fastest, with the existence of O(nlog^3 {n}) algorithm based on max-flow reduction.
MS

Styles APA, Harvard, Vancouver, ISO, etc.

Wang, Nan. « A Framework of Transforming Vertex Deletion Algorithm to Edge Deletion Algorithm ». University of Cincinnati / OhioLINK, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1504878748832156.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Chakeri, Alireza. « Scalable Unsupervised Learning with Game Theory ». Scholar Commons, 2017. http://scholarcommons.usf.edu/etd/6616.

Texte intégral

Résumé :

Recently dominant sets, a generalization of the notion of the maximal clique to edge-weighted graphs, have proven to be an effective tool for unsupervised learning and have found applications in different domains. Although, they were initially established using optimization and graph theory concepts, recent work has shown fascinating connections with evolutionary game theory, that leads to the clustering game framework. However, considering size of today's data sets, existing methods need to be modified in order to handle massive data. Hence, in this research work, first we address the limitations of the clustering game framework for large data sets theoretically. We propose a new important question for the clustering community ``How can a cluster of a subset of a dataset be a cluster of the entire dataset?''. We show that, this problem is a coNP-hard problem in a clustering game framework. Thus, we modify the definition of a cluster from a stable concept to a non-stable but optimal one (Nash equilibrium). By experiments we show that this relaxation does not change the qualities of the clusters practically. Following this alteration and the fact that equilibriums are generally compact subsets of vertices, we design an effective strategy to find equilibriums representing well distributed clusters. After finding such equilibriums, a linear game theoretic relation is proposed to assign vertices to the clusters and partition the graph. However, the method inherits a space complexity issue, that is the similarities between every pair of objects are required which proves practically intractable for large data sets. To overcome this limitation, after establishing necessary theoretical tools for a special type of graphs that we call vertex-repeated graphs, we propose the scalable clustering game framework. This approach divides a data set into disjoint tractable size chunks. Then, the exact clusters of the entire data are approximated by the clusters of the chunks. In fact, the exact equilibriums of the entire graph is approximated by the equilibriums of the subsets of the graph. We show theorems that enable significantly improved time complexity for the model. The applications include, but are not limited to, the maximum weight clique problem, large data clustering and image segmentation. Experiments have been done on random graphs and the DIMACS benchmark for the maximum weight clique problem and on magnetic resonance images (MRI) of the human brain consisting of about 4 million examples for large data clustering. Also, on the Berkeley Segmentation Dataset, the proposed method achieves results comparable to the state of the art, providing a parallel framework for image segmentation and without any training phase. The results show the effectiveness and efficiency of our approach. In another part of this research work, we generalize the clustering game method to cluster uncertain data where the similarities between the data points are not exactly known, that leads to the uncertain clustering game framework. Here, contrary to the ensemble clustering approaches, where the results of different similarity matrices are combined, we focus on the average utilities of an uncertain game. We show that the game theoretical solutions provide stable clusters even in the presence of severe uncertainties. In addition, based on this framework, we propose a novel concept in uncertain data clustering so that every subset of objects can have a ''cluster degree''. Extensive experiments on real world data sets, as well as on the Berkeley image segmentation dataset, confirm the performance of the proposed method. And finally, instead of dividing a graph into chunks to make the clustering scalable, we study the effect of the spectral sparsification method based on sampling by effective resistance on the clustering outputs. Through experimental and theoretical observations, we show that the clustering results obtained from sparsified graphs are very similar to the results of the original non-sparsified graphs. The rand index is always at about 0.9 to 0.99 in our experiments even when lots of sparsification is done.

Styles APA, Harvard, Vancouver, ISO, etc.

Liang, Weifa, et wliang@cs anu edu au. « Designing Efficient Parallel Algorithms for Graph Problems ». The Australian National University. Department of Computer Science, 1997. http://thesis.anu.edu.au./public/adt-ANU20010829.114536.

Texte intégral

Résumé :

Graph algorithms are concerned with the algorithmic aspects of solving graph problems. The problems are motivated from and have application to diverse areas of computer science, engineering and other disciplines. Problems arising from these areas of application are good candidates for parallelization since they often have both intense computational needs and stringent response time requirements. Motivated by these concerns, this thesis investigates parallel algorithms for these kinds of graph problems that have at least one of the following properties: the problems involve some type of dynamic updates; the sparsification technique is applicable; or the problems are closely related to communications network issues. The models of parallel computation used in our studies are the Parallel Random Access Machine (PRAM) model and the practical interconnection network models such as meshes and hypercubes. ¶ Consider a communications network which can be represented by a graph G = (V;E), where V is a set of sites (processors), and E is a set of links which are used to connect the sites (processors). In some cases, we also assign weights and/or directions to the edges in E. Associated with this network, there are many problems such as (i) whether the network is k-edge (k-vertex) connected withfixed k; (ii) whether there are k-edge (k-vertex) disjoint paths between u and v for a pair of given vertices u and v after the network is dynamically updated by adding and/or deleting an edge etc; (iii) whether the sites in the network can communicate with each other when some sites and links fail; (iv) identifying the first k edges in the network whose deletion will result in the maximum increase in the routing cost in the resulting network for fixed k; (v) how to augment the network at optimal cost with a given feasible set of weighted edges such that the augmented network is k-edge (k-vertex) connected; (vi) how to route messages through the network efficiently. In this thesis we answer the problems mentioned above by presenting efficient parallel algorithms to solve them. As far as we know, most of the proposed algorithms are the first ones in the parallel setting. ¶ Even though most of the problems concerned in this thesis are related to communications networks, we also study the classic edge-coloring problem. The outstanding difficulty to solve this problem in parallel is that we do not yet know whether or not it is in NC. In this thesis we present an improved parallel algorithm for the problem which needs [bigcircle]([bigtriangleup][superscript 4.5]log [superscript 3] [bigtriangleup] log n + [bigtriangleup][superscript 4] log [superscript 4] n) time using [bigcircle](n[superscript 2][bigtriangleup] + n[bigtriangleup][superscript 3]) processors, where n is the number of vertices and [bigtriangleup] is the maximum vertex degree. Compared with a previously known result on the same model, we improved by an [bigcircle]([bigtriangleup][superscript 1.5]) factor in time. The non-trivial part is to reduce this problem to the edge-coloring update problem. We also generalize this problem to the approximate edge-coloring problem by giving a faster parallel algorithm for the latter case. ¶ Throughout the design and analysis of parallel graph algorithms, we also find a technique called the sparsification technique is very powerful in the design of efficient sequential and parallel algorithms on dense undirected graphs. We believe that this technique may be useful in its own right for guiding the design of efficient sequential and parallel algorithms for problems in other areas as well as in graph theory.

Styles APA, Harvard, Vancouver, ISO, etc.

Chapitres de livres sur le sujet "Sparsification de graphe"

Ahmed, Reyan, Keaton Hamm, Stephen Kobourov, Mohammad Javad Latifi Jebelli, Faryad Darabi Sahneh et Richard Spence. « Multi-priority Graph Sparsification ». Dans Lecture Notes in Computer Science, 1–12. Cham : Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-34347-6_1.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Gollub, Tim, et Benno Stein. « Unsupervised Sparsification of Similarity Graphs ». Dans Studies in Classification, Data Analysis, and Knowledge Organization, 71–79. Berlin, Heidelberg : Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-10745-0_7.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Escolano, Francisco, Manuel Curado, Silvia Biasotti et Edwin R. Hancock. « Shape Simplification Through Graph Sparsification ». Dans Graph-Based Representations in Pattern Recognition, 13–22. Cham : Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-58961-9_2.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Eades, Peter, Quan Nguyen et Seok-Hee Hong. « Drawing Big Graphs Using Spectral Sparsification ». Dans Lecture Notes in Computer Science, 272–86. Cham : Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-73915-1_22.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Ahn, Kook Jin, Sudipto Guha et Andrew McGregor. « Spectral Sparsification in Dynamic Graph Streams ». Dans Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 1–10. Berlin, Heidelberg : Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-40328-6_1.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Laeuchli, Jesse. « Fast Community Detection with Graph Sparsification ». Dans Advances in Knowledge Discovery and Data Mining, 291–304. Cham : Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-47426-3_23.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Upadhyay, Jalaj. « Random Projections, Graph Sparsification, and Differential Privacy ». Dans Advances in Cryptology - ASIACRYPT 2013, 276–95. Berlin, Heidelberg : Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-42033-7_15.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Ahn, Kook Jin, et Sudipto Guha. « Graph Sparsification in the Semi-streaming Model ». Dans Automata, Languages and Programming, 328–38. Berlin, Heidelberg : Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02930-1_27.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Hossain, Tanvir, Khaled Mohammed Saifuddin, Muhammad Ifte Khairul Islam, Farhan Tanvir et Esra Akbas. « Tackling Oversmoothing in GNN via Graph Sparsification ». Dans Lecture Notes in Computer Science, 161–79. Cham : Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-70371-3_10.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Jambulapati, Arun, Sushant Sachdeva, Aaron Sidford, Kevin Tian et Yibin Zhao. « Eulerian Graph Sparsification by Effective Resistance Decomposition ». Dans Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1607–50. Philadelphia, PA : Society for Industrial and Applied Mathematics, 2025. https://doi.org/10.1137/1.9781611978322.50.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Actes de conférences sur le sujet "Sparsification de graphe"

Hashemi, Mohammad, Shengbo Gong, Juntong Ni, Wenqi Fan, B. Aditya Prakash et Wei Jin. « A Comprehensive Survey on Graph Reduction : Sparsification, Coarsening, and Condensation ». Dans Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. California : International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/891.

Texte intégral

Résumé :

Many real-world datasets can be naturally represented as graphs, spanning a wide range of domains. However, the increasing complexity and size of graph datasets present significant challenges for analysis and computation. In response, graph reduction techniques have gained prominence for simplifying large graphs while preserving essential properties. In this survey, we aim to provide a comprehensive understanding of graph reduction methods, including graph sparsification, graph coarsening, and graph condensation. Specifically, we establish a unified definition for these methods and introduce a hierarchical taxonomy to categorize the challenges they address. Our survey then systematically reviews the technical details of these methods and emphasizes their practical applications across diverse scenarios. Furthermore, we outline critical research directions to ensure the continued effectiveness of graph reduction techniques.

Styles APA, Harvard, Vancouver, ISO, etc.

Gong, Zheng, Guifeng Wang, Ying Sun, Qi Liu, Yuting Ning, Hui Xiong et Jingyu Peng. « Beyond Homophily : Robust Graph Anomaly Detection via Neural Sparsification ». Dans Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California : International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/234.

Texte intégral

Résumé :

Recently, graph-based anomaly detection (GAD) has attracted rising attention due to its effectiveness in identifying anomalies in relational and structured data. Unfortunately, the performance of most existing GAD methods suffers from the inherent structural noises of graphs induced by hidden anomalies connected with considerable benign nodes. In this work, we propose SparseGAD, a novel GAD framework that sparsifies the structures of target graphs to effectively reduce noises and collaboratively learns node representations. It then robustly detects anomalies by uncovering the underlying dependency among node pairs in terms of homophily and heterophily, two essential connection properties of GAD. Extensive experiments on real-world datasets of GAD demonstrate that the proposed framework achieves significantly better detection quality compared with the state-of-the-art methods, even when the graph is heavily attacked. Code will be available at https://github.com/KellyGong/SparseGAD.git.

Styles APA, Harvard, Vancouver, ISO, etc.

Huang, Guoquan, Michael Kaess et John J. Leonard. « Consistent sparsification for graph optimization ». Dans 2013 European Conference on Mobile Robots (ECMR). IEEE, 2013. http://dx.doi.org/10.1109/ecmr.2013.6698835.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Mazuran, Mladen, Tipaldi Gian Diego, Spinello Luciano et Wolfram Burgard. « Nonlinear Graph Sparsification for SLAM ». Dans Robotics : Science and Systems 2014. Robotics : Science and Systems Foundation, 2014. http://dx.doi.org/10.15607/rss.2014.x.040.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Parchas, Panos, Nikolaos Papailiou, Dimitris Papadias et Francesco Bonchi. « Uncertain Graph Sparsification (Extended Abstract) ». Dans 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 2019. http://dx.doi.org/10.1109/icde.2019.00265.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Spielman, Daniel A., et Nikhil Srivastava. « Graph sparsification by effective resistances ». Dans the 40th annual ACM symposium. New York, New York, USA : ACM Press, 2008. http://dx.doi.org/10.1145/1374376.1374456.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Satuluri, Venu, Srinivasan Parthasarathy et Yiye Ruan. « Local graph sparsification for scalable clustering ». Dans the 2011 international conference. New York, New York, USA : ACM Press, 2011. http://dx.doi.org/10.1145/1989323.1989399.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Fung, Wai Shing, Ramesh Hariharan, Nicholas J. A. Harvey et Debmalya Panigrahi. « A general framework for graph sparsification ». Dans the 43rd annual ACM symposium. New York, New York, USA : ACM Press, 2011. http://dx.doi.org/10.1145/1993636.1993647.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Wu, Hang-Yang, et Yi-Ling Chen. « Graph Sparsification with Generative Adversarial Network ». Dans 2020 IEEE International Conference on Data Mining (ICDM). IEEE, 2020. http://dx.doi.org/10.1109/icdm50108.2020.00172.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Charalambides, Neophytos, et Alfred O. Hero. « Graph Sparsification by Approximate matrix Multiplication ». Dans 2023 IEEE Statistical Signal Processing Workshop (SSP). IEEE, 2023. http://dx.doi.org/10.1109/ssp53291.2023.10208048.

Texte intégral

Styles APA, Harvard, Vancouver, ISO, etc.

Nous offrons des réductions sur tous les plans premium pour les auteurs dont les œuvres sont incluses dans des sélections littéraires thématiques. Contactez-nous pour obtenir un code promo unique!