Examining Higher Order Transformations for Scale-free Small World Graphs

Abstract—The degree distribution of scale-free Small World networks follows a power law. For random graph generators, its exponent is constrained by the construction mechanism, whereas in real-world data, different slopes can be observed. However, the degree distribution alone does not reveal much of the local structure of these graphs. Therefore, we propose a graph transformation we call ”higher order ” transformation, which encodes the number of common neighbours two vertices share in its edge weights. Studying the degree distribution of second-and third order graphs and comparing it to natural language co-occurrence data, we find that the higher order transformation reveals differences that cannot be detected by only looking at traditional measures on the original graph. I