Dissertation Proposal - Josh Johnston

Random Processes with High Variance Produce Scale Free Networks

Presented by Josh Johnston – Computer Science Emphasis

Abstract

Real-world networks tend to be scale free, having power law degree distributions with more hubs than predicted by classical random graph generation methods. Preferential attachment and growth are the most commonly accepted mechanisms leading to these networks and are incorporated in the Barabási–Albert (BA) model. But while the BA model leads to scale free networks, preferential attachment and growth have never been proven as the mechanism for real world networks. Some even question whether the heavy-tailed degree distributions we observe are best described as power laws. Instead, preferential attachment and growth have become accepted because there has been no alternative, generalized model proposed in the 23 years since the heavy-tailed degree distribution phenomenon was first observed.

We developed an alternative to the BA model for network growth using a randomly stopped linking process inspired by a generalized Central Limit Theorem (CLT) for geometric distributions with widely varying parameters. The common characteristic of both the BA model and our randomly stopped linking model is the mixture of widely varying geometric distributions, suggesting the critical characteristic of scale free networks is high variance, not growth or preferential attachment. The limitation of classical random graph models is low variance in parameters, while scale free networks are the natural, expected result of real-world variance.

Committee

Dr. Tim Andersen (Chair), Dr. Casey Kennington, Dr. Francesca Spezzano