Files in this item

FilesDescriptionFormat

application/pdf

application/pdfSANKAGIRI-THESIS-2018.pdf (2MB)
(no description provided)PDF

Description

Title:Community detection in preferential attachment graphs
Author(s):Sankagiri, Suryanarayana
Advisor(s):Hajek, Bruce
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):community detection
preferential attachment graphs
message passing
Abstract:This thesis examines the problem of community detection in a new random graph model, which is a generalization of preferential attachment graphs. This model has some features that are more realistic than those of the often-studied stochastic block model (SBM). A message passing algorithm for community detection is derived, and multiple simulation results are shown that demonstrate the efficacy of the algorithm. The algorithm is based on certain asymptotic properties unique to this model. These properties, some of which were discovered as part of this work, prove to be useful for other purposes as well, which are described in this thesis. In particular, a theoretical performance analysis is given for a simple, hypothesis-testing based community recovery algorithm. This thesis opens avenues to further theoretical analysis of this model, and takes a step toward developing community detection algorithms with strong theoretical foundations that work well on real-world networks.
Issue Date:2018-12-04
Type:Thesis
URI:http://hdl.handle.net/2142/102474
Rights Information:Copyright 2018 Suryanarayana Sankagiri
Date Available in IDEALS:2019-02-06
Date Deposited:2018-12


This item appears in the following Collection(s)

Item Statistics