Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 20 for “"Triangle Counting"”.
-
Triangle counting in graph streams: Power of multi-sampling
… known streaming algorithms to estimate number of triangles in a graph stream work as follows: Sample a single triangle with high enough probability and repeat this basic step to obtain a global triangle count. For example, one such algorithm uniformly at random picks a single vertex v and a single …
-
Fast and scalable triangle counting in graph streams: the hybrid approach
Triangle counting is a major graph problem with several applications in social network analysis, anomaly detection, etc. A considerable amount of work has contributed to approximately computing the global triangle counts using several computational models. One of the most popular streaming models …
-
Triangle counting and listing in directed and undirected graphs using single machines
Triangle enumeration is an important element in graph analysis, and because of this it is a topic that has been studied extensively. Although the formulation is simple, for large networks the computation becomes challenging as we have to deal with memory limitation and efficiency. Many algorithms …
-
Techniques for enabling GPU code generation of low-level optimizations and dynamic parallelism from high-level abstractions
… input graphs are discussed in detail. Lastly, a triangle counting application case study is performed in order to ascertain the performance of the newly possible Tangram generated code that leverages all techniques presented in this thesis. Performance of the generated code outperforms a cutting …
-
Cohesive subgraph computation over large heterogeneous information networks
… in which each edge participates in at least k-2 triangles. Nevertheless, existing solutions mainly focus on homogeneous networks, where vertices are of the same type, and thus cannot be applied to HINs. In this thesis, we study the problem of cohesive subgraphs mining and analysis over large …
-
1D-CROSSPOINT ARRAY AND ITS CONSTRUCTION, APPLICATION TO BIG DATA PROBLEMS, AND HIGHER DIMENSION VARIANTS
… algorithms of matrix multiplica- tion and triangle counting for the 1D-Crosspoint Array are introduced and analyzed. Lastly, two higher dimensional variants, 2D- and 3D-Crosspoint Array are also proposed with a construction method, which succeeds in reducing the number of PEs required by …
-
Towards Performance Portable Graph Algorithms
… algorithms for solving graph merging and triangle counting problems. Then, generalizing from our experiences, we propose an algorithmic framework, for shared-memory, heterogeneous machines for implementing block-based graph algorithms; PGAbB. PGAbB aims to maximally leverage different …
-
Large-scale graph algorithms and applications with an emphasis on fintech data
… include: (1) novel cover-edge based triangle counting algorithms that significantly reduce computational overhead through breadth-first search preprocessing, achieving substantial speedups over traditional methods and dramatic communication reduction in distributed settings, (2) …
-
On designing structure-aware high-performance graph algorithms
… (i) the SAPCo Sort algorithm as a parallel counting sort algorithm that is faster than comparison-based sorting algorithms in degree-ordering of power-law graphs, (ii) the iHTL algorithm that optimizes locality in Sparse Matrix-Vector (SpMV) Multiplication graph algorithms by extracting …
-
Scalable Parallel Algorithms for Massive Scale-free Graphs
… Connected Components, K-Core decomposition, Triangle Counting, and Page Rank. Our experimental study of these algorithms demonstrates excellent scalability on supercomputers, clusters with non-volatile memory, and shared memory systems. Our study includes multiple synthetic scale-free graph …
-
Efficient and Private Graph Mining: From Cohesive Subgraphs to Motif Counting
… Cohesive subgraph computation and motif counting are two fundamental tasks in graph mining, with many real-world applications. In this thesis, we address several fundamental problems in cohesive subgraph computation and motif counting, focusing on both bipartite and general graphs, under …
-
Graphlet counting in massive networks
… analyze complex networks. Graph motifs such as triangle (a cycle of size three), diamond (two triangles with one vertex in common), butterfly (a (2,2)-biclique), and $k$-clique (for $k \leq 6$) are indeed regarded as building blocks to understand the true structure of an underlying network. …
-
Efficient and scalable triangle centrality algorithms in the arkouda framework
… of a recently designed centrality measure called Triangle Centrality which is a centrality metric that considers both connectivity of a node with other nodes and the connectivity of a node’s neighbors. The connectivity is aptly measured through the triangles formed by nodes. There are two ways to …
-
Dense graph pattern mining and visualization
… high running time. In Chapter 5 we employed triangle counting in dense subgraph mining, which enables us to handle large graphs more efficiently. In this chapter, we propose a set of triangulation (the process of counting triangles inside a graph) based solutions to mine $DN$-graphs …
-
New results on verifiable and differentially private data analysis
… accuracy bounds for distinct-element counting, degree-histogram estimation, and triangle counting on dynamic streams. Thus, although error that is polynomial in the stream length T can be unavoidable in the worst case, substantially better accuracy can be obtained for many realistic …
-
Parallel Mining and Analysis of Triangles and Communities in Big Networks
… are often characterized by an abundance of triangles and the existence of well-structured communities. Thus, counting triangles and detecting communities in networks have become important algorithmic problems in network mining and analysis. In the era of big data, the network data emerged …
-
Accelerating graph computation with system optimizations and algorithmic design
… as we show in a case study with distributed triangle counting. 2. DeepGalois is a distributed graph neural network system that uses the observation that graph neural network computation can be expressed as a graph problem which allows it to be implemented in graph analytics systems. …
-
Graphlet based network analysis
… and early graphlet analyses is based on triples (triangles or paths of length two). Graphlet analysis based on cycles and cliques are also explored in several recent works. Another more comprehensive class of graphlet analysis methods works with graphlets of specific sizes—graphlets with three, …
-
Accelerating graph pattern mining algorithms on modern graphics processing units
Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-11 without embargo terms