{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/102474"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/102474","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Community detection in preferential attachment graphs","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Sankagiri, Suryanarayana"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Hajek, Bruce"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-02-06T19:36:28Z","date_published":"2019-02-06T19:36:28Z","updated_at":"2026-07-22T22:24:42Z","subjects":["community detection","preferential attachment graphs","message passing"],"languages":["en"],"rights":["Copyright 2018 Suryanarayana Sankagiri"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/102474","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Hajek, Bruce"]},{"key":"dc:creator","label":"Author","values":["Sankagiri, Suryanarayana"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-02-06T19:36:28Z","2018-12-04","2018-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["community detection","preferential attachment graphs","message passing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Suryanarayana Sankagiri"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/102474"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-02-05 without embargo terms","The student, Suryanarayana Sankagiri, accepted the attached license on 2018-12-04 at 12:56.","The student, Suryanarayana Sankagiri, submitted this Thesis for approval on 2018-12-04 at 13:09.","This Thesis was approved for publication on 2018-12-04 at 13:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #13201 on 2019-02-05 at 11:13:50","Made available in DSpace on 2019-02-06T19:36:28Z (GMT). No. of bitstreams: 3 SANKAGIRI-THESIS-2018.pdf: 1564589 bytes, checksum: 8271eed7bc1b068c4a473d7e6c4fcc8f (MD5) MS_Thesis.zip: 1829960 bytes, checksum: 9a92808ef16e71986321ef64c893b249 (MD5) LICENSE.txt: 4220 bytes, checksum: d8c199bba7124edb0d121a07f459be21 (MD5) Previous issue date: 2018-12-04"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Community detection in preferential attachment graphs"]}]}],"canonical_facts":{"dc:contributor":["Hajek, Bruce"],"dc:creator":["Sankagiri, Suryanarayana"],"dc:date":["2019-02-06T19:36:28Z","2018-12-04","2018-12"],"dc:description":["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.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2019-02-05 without embargo terms","The student, Suryanarayana Sankagiri, accepted the attached license on 2018-12-04 at 12:56.","The student, Suryanarayana Sankagiri, submitted this Thesis for approval on 2018-12-04 at 13:09.","This Thesis was approved for publication on 2018-12-04 at 13:23.","DSpace SAF Submission Ingestion Package generated from Vireo submission #13201 on 2019-02-05 at 11:13:50","Made available in DSpace on 2019-02-06T19:36:28Z (GMT). No. of bitstreams: 3 SANKAGIRI-THESIS-2018.pdf: 1564589 bytes, checksum: 8271eed7bc1b068c4a473d7e6c4fcc8f (MD5) MS_Thesis.zip: 1829960 bytes, checksum: 9a92808ef16e71986321ef64c893b249 (MD5) LICENSE.txt: 4220 bytes, checksum: d8c199bba7124edb0d121a07f459be21 (MD5) Previous issue date: 2018-12-04"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/102474"],"dc:language":["en"],"dc:rights":["Copyright 2018 Suryanarayana Sankagiri"],"dc:subject":["community detection","preferential attachment graphs","message passing"],"dc:title":["Community detection in preferential attachment graphs"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:42Z"}