Cluster detection in general Markov chains with applications to directed networks

Abstract

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.