University of Lethbridge Theses

Permanent URI for this collection

Now showing 1 - 1 of 1

Graph decomposition algorithms for analyzing social and large complex networks
(Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2022) Abdullah, Wali Mohammad; University of Lethbridge. Faculty of Arts and Science; Hossain, Shahadat
Graphs are often used to model or represent large and sparse networks with billions of vertices and edges and store extensive amounts of structural and semantic information. Therefore, analyzing characteristics in networked data, such as graphs that can yield important information on the modelled structure, is challenging due to their linked nature and size. A common way to uncover this high-quality information is by analyzing subgraphs to get a deeper understanding of the data, which are helpful for classification, clustering, and knowledge discovery. This thesis proposes using a compact network data representation based on sparse matrix data structures. We will consider the enumeration of subgraphs (edge clique cover problem) with some ordering schemes. Finally, we benefit from the linear algebraic approach to graph algorithms for counting triangles, triangle enumeration, the k-count algorithm, and triangle centrality calculation. This thesis will present both serial and parallel algorithms for solving these problems.