Community detection in preferential attachment graphs

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2019

Author dc:creator

• Sankagiri, Suryanarayana

Contributors dc:contributor

• Hajek, Bruce

• community detection
• preferential attachment graphs
• message passing

Statement dc:rights

• Copyright 2018 Suryanarayana Sankagiri

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/102474

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/102474