You are here

UCF Digital Collections ยป Honors Collection

SPARSIFICATION OF SOCIAL NETWORKS USING RANDOM WALKS

Download pdf | Full Screen View

Date Issued:
2015
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 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.
Title: SPARSIFICATION OF SOCIAL NETWORKS USING RANDOM WALKS.
25 views
11 downloads
Name(s): Wilder, Bryan, Author
Sukthankar, Gita, Committee Chair
University of Central Florida, Degree Grantor
Type of Resource: text
Date Issued: 2015
Publisher: University of Central Florida
Language(s): English
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 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.
Identifier: CFH0004732 (IID), ucf:45387 (fedora)
Note(s): 2015-05-01
B.S.
Engineering and Computer Science, Dept. of Electrical Engineering and Computer Science
Bachelors
This record was generated from author submitted information.
Subject(s): sparsification
social network analysis
influence maximization
Persistent Link to This Record: http://purl.flvc.org/ucf/fd/CFH0004732
Restrictions on Access: public
Host Institution: UCF

In Collections