Cluster detection in general Markov chains with applications to directed networks

Many community detection algorithms rely on information provided by the eigenvalues of matrices of the associated network. These techniques cannot be extended for directed networks since the matrices required are symmetric, diagonalizable, and have only real eigenvalues. Directed networks do not necessarily have these properties, which makes their analysis difficult. In this thesis, we created a community detection algorithm that utilizes the eigenvalues and eigenvectors of a transition matrix to find communities within Markov chains and directed networks. We test our community detection algorithm on various benchmarks, such as an implementation of the stochastic block model, Lancichinetti-Fortunato benchmarks, and real-world networks. We score the algorithm’s performance against other detection algorithms using validation metrics such as the Rand index. Our findings indicate that our algorithm’s performance depends on the strength of the clusters as measured by weight and structure ratios and that its performance is comparable to other community detection algorithms.

Name thesis:degree_name

Master of Science (MSc)

Discipline thesis:degree_discipline

Modelling and Computational Science

Grantor

University of Ontario Institute of Technology

Year dc:date.issued

2024

Author dc:creator

• Sands, Darryen

Advisor dc:contributor.advisor

• Breen, Jane

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/10155/1868

OAI identifier oai:identifier

oai:ontariotechu.scholaris.ca:10155/1868