Clustering Behaviour of Highly Central Nodes in Graph Representations of Data

Sammanfattning

This thesis investigates the relationship between centrality measures andclustering structure in graph representations of data. This is done byexamining whether nodes identified as highly central tend to cluster in denselyconnected regions of the graph, and how the parameter 𝛼 in Katz centralityinfluences this behaviour. The aim of this work is to better understand how centrality measures relateto the global structure of a graph, rather than only being used to identifyindividual important nodes. This work uses images from the MNIST dataset as nodes in a weighted k-nearest neighbour graph, with edge weights defined using a transformation ofthe cosine distance. On this graph, centrality measures are computed, and theclustering behaviour of the most central nodes is analysed using measures ofcluster tightness as a function of 𝛼. The results show that cluster tightness generally increases with 𝛼, indicatingthat higher values of the parameter favour nodes in densely connected regions.This behaviour does however depend on the underlying structure of the graphbeing suitable for the method used, with weaker or less consistent trendsobserved when this is not the case. Additionally, the clustering tightness for the Katz centrality is observed toconverge towards that of the exponential centrality as 𝛼 increases, suggestingthat both measures capture similar global structural features. These results provide insight into how centrality measures can be used toidentify densely connected regions of graphs.