Computer Engineering Commons^™

Power Laws In Complex Graphs: Parsimonious Generative Models, Similarity Testing Algorithms, And The Origins, Shan Lu

Doctoral Dissertations

This dissertation mainly discussed topics related to power law graphs, including graph similarity testing algorithms and power law generative models. For graph similarity testing, we proposed a method based on the mathematical theory of diffusion over manifolds using random walks over graphs. We show that our method not only distinguishes between graphs with different degree distributions, but also graphs with the same degree distributions. We compare the undirected power law graphs generated by Barabasi-Albert model and directed power law graphs generated by Krapivsky's model to the random graphs generated by Erdos-Renyi model. We also compare power law graphs generated by …