Community detection in preferential attachment graphs

community detection;preferential attachment graphs;message passing

Sankagiri, Suryanarayana ; Hajek ; Bruce

关键词: community detection;    preferential attachment graphs;    message passing;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/102474/SANKAGIRI-THESIS-2018.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

This thesis examines the problem of community detection in a new random graph model, which is ageneralization 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.