{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/50662"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/50662","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Scaling overlapping community detection algorithms","abstract":"Community structure is observed in many real-world networks in fields ranging from social networking to biological networks. Over the last decade many approaches have been proposed to efficiently detect the underlying structure of communities in graphs with a greater degree of correctness. This specific area of graph mining is known as community detection. It is one of the most critical components of graph mining. It helps in understanding the underlying properties of the graph. While a lot of effort has been expended on detecting standard partitions in a graph, real world applications are complicated and they exhibit nodes belonging to multiple communities concurrently. Although many algorithms such as Clique Percolation Method, COPRA, etc., have been developed to detect overlapping communities in graphs, they rely on expensive and complicated optimization techniques and do not scale well to real world datasets containing millions of nodes and tens of millions of edges. In this thesis, we propose a vertex centric approach to the problem and we evaluate scalability of overlapping community detection algorithms when implemented using vertex centric graph processing frameworks such as GraphLab/GraphChi. In particular we implemented BigCLAM in GraphChi and were able to achieve speedups of up to 6.5x on large scale real world graphs, thus proving that our approach can give linear speedups on the same hardware settings.","abstract_html":"Community structure is observed in many real-world networks in fields ranging from social networking to biological networks. Over the last decade many approaches have been proposed to efficiently detect the underlying structure of communities in graphs with a greater degree of correctness. This specific area of graph mining is known as community detection. It is one of the most critical components of graph mining. It helps in understanding the underlying properties of the graph. While a lot of effort has been expended on detecting standard partitions in a graph, real world applications are complicated and they exhibit nodes belonging to multiple communities concurrently. Although many algorithms such as Clique Percolation Method, COPRA, etc., have been developed to detect overlapping communities in graphs, they rely on expensive and complicated optimization techniques and do not scale well to real world datasets containing millions of nodes and tens of millions of edges. In this thesis, we propose a vertex centric approach to the problem and we evaluate scalability of overlapping community detection algorithms when implemented using vertex centric graph processing frameworks such as GraphLab/GraphChi. In particular we implemented BigCLAM in GraphChi and were able to achieve speedups of up to 6.5x on large scale real world graphs, thus proving that our approach can give linear speedups on the same hardware settings.","abstract_has_math":false,"creators":["Chaugule, Amey"],"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":["Polychronopoulos, Constantine D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-09-16T17:25:00Z","date_published":"2014-09-16T17:25:00Z","updated_at":"2026-07-22T22:25:40Z","subjects":["Network Communities","Overlapping community detection","Scalable Systems","Distributed graph processing"],"languages":["en"],"rights":["Copyright 2014 Amey S. Chaugule"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/50662","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Polychronopoulos, Constantine D."]},{"key":"dc:creator","label":"Author","values":["Chaugule, Amey"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-09-16T17:25:00Z","2014-08","2014-09-16"]},{"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":["Network Communities","Overlapping community detection","Scalable Systems","Distributed graph processing"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2014 Amey S. Chaugule"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/50662"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Community structure is observed in many real-world networks in fields ranging from social networking to biological networks. Over the last decade many approaches have been proposed to efficiently detect the underlying structure of communities in graphs with a greater degree of correctness. This specific area of graph mining is known as community detection. It is one of the most critical components of graph mining. It helps in understanding the underlying properties of the graph. While a lot of effort has been expended on detecting standard partitions in a graph, real world applications are complicated and they exhibit nodes belonging to multiple communities concurrently. Although many algorithms such as Clique Percolation Method, COPRA, etc., have been developed to detect overlapping communities in graphs, they rely on expensive and complicated optimization techniques and do not scale well to real world datasets containing millions of nodes and tens of millions of edges. In this thesis, we propose a vertex centric approach to the problem and we evaluate scalability of overlapping community detection algorithms when implemented using vertex centric graph processing frameworks such as GraphLab/GraphChi. In particular we implemented BigCLAM in GraphChi and were able to achieve speedups of up to 6.5x on large scale real world graphs, thus proving that our approach can give linear speedups on the same hardware settings.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-07-23T21:52:04Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Chaugule_Amey.pdf: 1361166 bytes, checksum: 4c48045fffa4c512085e87ec6e5793fc (MD5)","Made available in DSpace on 2014-09-16T17:25:00Z (GMT). No. of bitstreams: 2 Amey_Chaugule.pdf: 1389371 bytes, checksum: be020c00aaf8c5f33153c25f2304a1e6 (MD5) license.txt: 4063 bytes, checksum: 0d01a97066cd30392a5a295add4e6a8f (MD5)"]},{"key":"dc:title","label":"Title","values":["Scaling overlapping community detection algorithms"]}]}],"canonical_facts":{"dc:contributor":["Polychronopoulos, Constantine D."],"dc:creator":["Chaugule, Amey"],"dc:date":["2014-09-16T17:25:00Z","2014-08","2014-09-16"],"dc:description":["Community structure is observed in many real-world networks in fields ranging from social networking to biological networks. Over the last decade many approaches have been proposed to efficiently detect the underlying structure of communities in graphs with a greater degree of correctness. This specific area of graph mining is known as community detection. It is one of the most critical components of graph mining. It helps in understanding the underlying properties of the graph. While a lot of effort has been expended on detecting standard partitions in a graph, real world applications are complicated and they exhibit nodes belonging to multiple communities concurrently. Although many algorithms such as Clique Percolation Method, COPRA, etc., have been developed to detect overlapping communities in graphs, they rely on expensive and complicated optimization techniques and do not scale well to real world datasets containing millions of nodes and tens of millions of edges. In this thesis, we propose a vertex centric approach to the problem and we evaluate scalability of overlapping community detection algorithms when implemented using vertex centric graph processing frameworks such as GraphLab/GraphChi. In particular we implemented BigCLAM in GraphChi and were able to achieve speedups of up to 6.5x on large scale real world graphs, thus proving that our approach can give linear speedups on the same hardware settings.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2014-07-23T21:52:04Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Chaugule_Amey.pdf: 1361166 bytes, checksum: 4c48045fffa4c512085e87ec6e5793fc (MD5)","Made available in DSpace on 2014-09-16T17:25:00Z (GMT). No. of bitstreams: 2 Amey_Chaugule.pdf: 1389371 bytes, checksum: be020c00aaf8c5f33153c25f2304a1e6 (MD5) license.txt: 4063 bytes, checksum: 0d01a97066cd30392a5a295add4e6a8f (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/50662"],"dc:language":["en"],"dc:rights":["Copyright 2014 Amey S. Chaugule"],"dc:subject":["Network Communities","Overlapping community detection","Scalable Systems","Distributed graph processing"],"dc:title":["Scaling overlapping community detection algorithms"],"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:25:40Z"}