Booth Id:
MATH042
Category:
Mathematics
Year:
2017
Finalist Names:
Ramani, Arjun
Abstract:
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 Won:
Raytheon Technologies Corporation: Each winning project will receive $3,000 in shares of UTC common stock.
University of Arizona: Tuition Scholarship Award
Third Award of $1,000
American Mathematical Society: Third Award of $500