Current Search: Wilder, Bryan (x)
-
-
Title
-
SPARSIFICATION OF SOCIAL NETWORKS USING RANDOM WALKS.
-
Creator
-
Wilder, Bryan, Sukthankar, Gita, University of Central Florida
-
Abstract / Description
-
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...
Show moreAnalysis 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.
Show less
-
Date Issued
-
2015
-
Identifier
-
CFH0004732, ucf:45387
-
Format
-
Document (PDF)
-
PURL
-
http://purl.flvc.org/ucf/fd/CFH0004732
