Mapping Edges to Nodes by Utilizing Morton Codes in Stochastic Kronecker Graphs

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. Developing algorithms to quickly generate edges in a large stochastic kronecker graph eases the study of networks substantially. In previous research, we created an algorithm to more quickly sample Kronecker graphs. Once the edges are generated though, they must be backward-mapped to their respective nodes. This project establishes a novel connection between the fractal structure of Kronecker graphs and the Morton Code (z-order code) which maps multidimensional data to unidimensional data while preserving locality of data points. We mathematically prove that the Morton code provides the correct mapping between the edge-permutations and their corresponding nodes. This is the first known research to establish and prove this connection. Furthermore, as a side problem, we present an algorithm to efficiently sample fixed-edge Erdos-Renyi graphs by utilizing a generalized unranking procedure.

Awards (4)

• Third Award of $1,000 $1,000
• Raytheon Technologies Corporation: Each winning project will receive $3,000 in shares of UTC common stock. $3,000
• American Mathematical Society: Third Award of $500 $500
• University of Arizona: Tuition Scholarship Award

Competition history

• ISEF 2017 Mathematics · Entry MATH042

Resources

• ISEF abstract page ↗

Related projects

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