##### PROJECT # Market Basket Analysis with Graph Theory > [!abstract] Programming Language(s): Python, Rust > URL(s): [Github Repository](https://github.com/Sahil-Pattni/Market-Basket-Analysis-with-Graph-Theory/tree/main/Dissertation/build)  This was the final-year dissertation I submitted for my undergraduate degree at Heriot-Watt University. In this paper, I expanded on a novel approach to association rule item-set generation using minimum spanning trees. While the original paper introduced a technique to generate single item associations (e.g. $A\rightarrow B$), I developed a method to derive associations between sets of items (e.g. $[ A,B,C] \rightarrow [D,E]$). This was achieved by applying Markov Clustering to the minimum spanning tree to identify distinct regions within the tree where products were more closely related. Item-set rules could then be derived from within the same region, or between two distinct regions. The methodology was evaluated on a database of approximately 1.4 million transactions from a chain of gas station stores in Brazil.