Abstract

Analysis of large network datasets has become increasingly important. Algorithms have been designed to find many kinds of structure, with numerous applications across the social and biological sciences. However, a tradeoff is always present between accuracy and scalability; otherwise promising techniques can be computationally infeasible when applied to networks with huge numbers of nodes and edges. One way of extending the reach of network analysis is to sparsify the graph by retaining only a subset of its edges. The reduced network could prove much more tractable. For this thesis, I propose a new sparsification algorithm that preserves the properties of a random walk on the network. Specifically, the algorithm finds a subset of edges that best preserves the stationary distribution of a random walk by minimizing the Kullback-Leibler divergence between a walk on the original and sparsified graphs. A highly efficient greedy search strategy is developed to optimize this objective. Experimental results are presented that test the performance of the algorithm on the influence maximization task. These results demonstrate that sparsification allows near-optimal solutions to be found in a small fraction of the runtime that would required using the full network. Two cases are shown where sparsification allows an influence maximization algorithm to be applied to a dataset that previous work had considered intractable.

Notes

If this is your Honors thesis, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Thesis Completion

2015

Semester

Spring

Advisor

Sukthankar, Gita

Degree

Bachelor of Science (B.S.)

College

College of Engineering and Computer Science

Department

Electrical Engineering and Computer Science

Degree Program

Computer Science

Subjects

Dissertations, Academic -- Engineering and Computer Science; Engineering and Computer Science -- Dissertations, Academic

Format

PDF

Identifier

CFH0004732

Language

English

Access Status

Open Access

Length of Campus-only Access

None

Document Type

Honors in the Major Thesis

Download

Share

COinS