Fast Sampling of Stochastic Kronecker Graphs by Identifying Erdos-Renyi Subregions

Overview

From the world wide web to social networks, big data often take the form of graphs. It is important to be able to generate realistic random graphs in order to analyze the properties of real networks. For example, anomalistic network motifs can be identified by comparing real networks to random networks. The kronecker product is one such way to simulate the evolution of graphs over time by recursively expanding a simple initiator adjacency matrix to a larger kronecker graph. Kronecker graphs have similar properties to real world networks such as power law degree distributions, shrinking diameters, and the well-known 6 degrees of separation. Developing algorithms to quickly generate edges in a large stochastic kronecker graph eases the study of networks substantially. Previous methods like coin flipping involve going through each pair of nodes one by one and flipping a weighted coin. Coin flipping is inefficient creating the need for new algorithms in this field. Recently, common probability regions named Erdos-Renyi subregions were found in kronecker graphs. This project develops a novel method to sample kronecker graphs by using geometric random variables within Erdos-Renyi subregions to quickly generate edges. In addition, this project solves the unranking problem, which entails backward-mapping the created edges to the corresponding pairs of nodes in the larger kronecker graph. This algorithm is currently the fastest for generating kronecker graphs.

Competition history

• ISEF 2016 Category not listed · Entry MATH046

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.