School of Physical Sciences (Phys-Sciences)

Permanent URI for this community

Mathematical methods for computing centrality measures based on powers of the adjacency matrix for large networks

(Makerere University, 2023-08-07) Anguzu, Collins

Network models have become essential tools in information retrieval, decision making, and general interconnected systems. Importantly, in a network, it is often of interest to locate the most important vertices, mainly by using graph centrality measures. As such, there are numerous centrality measures that give the same ranks. This study focused on centrality measures based on the powers of the adjacency matrix, such as degree, beta, alpha, Katz, cumulative nomination, PageRank, and eigenvector centralities. Based on lazy random walks on directed graphs, some centralities were reformulated and the similarities between them were investigated. Furthermore, basing on the applications of eigenvector centrality measures, especially in social networks, ecology, disease diﬀusion networks, and mechanical infrastructure development, this research developed a method of computing eigenvector centrality using graph partitioning techniques. Essentially, by partitioning, one obtains the directed acyclic graph (DAG) topology of a network at hand. With DAG, the eigenvector centrality was obtained in a closed form. Numerical experiments were performed, and the ﬁndings revealed that the proposed algorithm outperformed the conventional power method and could eﬃciently compute centrality measures for large graphs.