{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T22:36:03Z","timestamp":1777761363217,"version":"3.51.4"},"reference-count":70,"publisher":"Emerald","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,8,19]]},"abstract":"<jats:p>Graph representations are pervasive in scientific and social computing. They serve as vital tools to model the interplay among different interacting entities.<\/jats:p>\n                  <jats:p>In this paper, we visit the problem of community detection, which is one of the most widely used graph operations toward scientific discovery. Community detection refers to the process of identifying tightly-knit subgroups of vertices in a large graph. These sub-groups (or communities) represent vertices that are tied together through common structure or function. Identification of communities could help in understanding the modular organization of complex networks. However, owing to large data sizes and high computational costs, performing community detection at scale has become increasingly challenging.<\/jats:p>\n                  <jats:p>Here, we present a detailed review and analysis of some of the leading computational methods and implementations developed for executing community detection on modern day multicore and manycore architectures. Our goals are to: a) define the problem of community detection and highlight its scientific significance; b) relate to challenges in parallelizing the operation on modern day architectures; c) provide a detailed report and logical organization of the approaches that have been designed for various architectures; and d) finally, provide insights into the strengths and suitability of different architectures for community detection, and a preview into the future trends of the area. It is our hope that this detailed treatment of community detection on parallel architectures can serve as an exemplar study for extending the application of modern day multicore and manycore architectures to other complex graph applications.<\/jats:p>","DOI":"10.1561\/1000000044","type":"journal-article","created":{"date-parts":[[2016,8,19]],"date-time":"2016-08-19T08:05:14Z","timestamp":1471593914000},"page":"145-247","source":"Crossref","is-referenced-by-count":5,"title":["Fast Uncovering of Graph Communities on a Chip: Toward Scalable Community Detection on Multicore and Manycore Platforms"],"prefix":"10.1108","volume":"10","author":[{"given":"Ananth","family":"Kalyanaraman","sequence":"first","affiliation":[{"name":"School of EECS , WSU, Pullman, WA","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahantesh","family":"Halappanavar","sequence":"additional","affiliation":[{"name":"PNNL , Richland, WA","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Chavarr\u00eda-Miranda","sequence":"additional","affiliation":[{"name":"PNNL , Richland, WA","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Lu","sequence":"additional","affiliation":[{"name":"School of EECS , WSU, Pullman, WA","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Karthi","family":"Duraisamy","sequence":"additional","affiliation":[{"name":"School of EECS , WSU, Pullman, WA","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Partha Pratim","family":"Pande","sequence":"additional","affiliation":[{"name":"School of EECS , WSU, Pullman, WA","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2016,8,19]]},"reference":[{"key":"2026032901221666000_ref001","article-title":"Tile processor: Embedded multicore for networking and multimedia","volume":"19","author":"Agarwal","year":"2007","journal-title":"Hot Chips"},{"key":"2026032901221666000_ref002","first-page":"303","volume-title":"Opentuner: An extensible framework for program autotuning","author":"Ansel","year":"2014"},{"key":"2026032901221666000_ref003","first-page":"12","volume-title":"Modularity and graph algorithms","author":"Bader","year":"2009"},{"key":"2026032901221666000_ref004","volume-title":"Graph partitioning and graph clustering","author":"Bader","year":"2012"},{"issue":"1","key":"2026032901221666000_ref005","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0378-4371(00)00018-2","article-title":"Scale-free characteristics of random networks: the topology of the world-wide web","volume":"281","author":"Barab\u00e1si","year":"2000","journal-title":"Physica A: Statistical Mechanics and its Applications"},{"issue":"5","key":"2026032901221666000_ref006","doi-asserted-by":"crossref","first-page":"056119","DOI":"10.1103\/PhysRevE.83.056119","article-title":"Tolerating the community detection resolution limit with edge weighting","volume":"83","author":"Berry","year":"2011","journal-title":"Physical Review E"},{"issue":"2","key":"2026032901221666000_ref007","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2024716.2024718","article-title":"The gem5 simulator","volume":"39","author":"Binkert","year":"2011","journal-title":"ACM SIGARCH Computer Architecture News"},{"key":"2026032901221666000_ref008","doi-asserted-by":"crossref","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","article-title":"Fast unfolding of communities in large networks","volume-title":"Journal of Statistical Mechanics: Theory and Experiment","author":"Blondel","year":"2008"},{"issue":"2","key":"2026032901221666000_ref009","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","article-title":"On modularity clustering","volume":"20","author":"Brandes","year":"2008","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"11","key":"2026032901221666000_ref010","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1016\/j.parco.2012.07.001","article-title":"Graph coloring algorithms for multi-core and massively multithreaded architectures","volume":"38","author":"Catalyurek","year":"2012","journal-title":"Parallel Computing"},{"key":"2026032901221666000_ref011","doi-asserted-by":"crossref","volume-title":"Optimizing irregular applications for energy and performance on the tilera many-core architecture","author":"Chavarr\u00eda-Miranda","DOI":"10.1145\/2742854.2742865"},{"key":"2026032901221666000_ref012","first-page":"1","volume-title":"Scaling graph community detection on the tilera many-core architecture","author":"Chavarria-Miranda","year":"2014"},{"key":"2026032901221666000_ref013","first-page":"819","volume-title":"Efficient and simplified parallel graph processing over CPU and MIC","author":"Chen","year":"2015"},{"issue":"6","key":"2026032901221666000_ref014","doi-asserted-by":"crossref","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","article-title":"Finding community structure in very large networks","volume":"70","author":"Clauset","year":"2004","journal-title":"Physical Review E"},{"issue":"6720","key":"2026032901221666000_ref015","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1038\/17501","article-title":"Superalliance of bottlenose dolphins","volume":"397","author":"Connor","year":"1999","journal-title":"Nature"},{"key":"2026032901221666000_ref016","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.jpdc.2014.08.009","article-title":"A work stealing based approach for enabling scalable optimal sequence homology detection","volume":"79","author":"Daily","year":"2015","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"1","key":"2026032901221666000_ref017","doi-asserted-by":"crossref","DOI":"10.1145\/2049662.2049663","article-title":"The University of Florida Sparse Matrix Collection","volume":"38","author":"Davis","year":"2011","journal-title":"ACM Transactions on Mathematical Software"},{"issue":"2","key":"2026032901221666000_ref018","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1109\/JETCAS.2012.2193835","article-title":"Wireless NoC as interconnection backbone for multicore chips: Promises and challenges","volume":"2","author":"Deb","year":"2012","journal-title":"IEEE Journal on Emerging and Selected Topics in Circuits and Systems"},{"issue":"12","key":"2026032901221666000_ref019","doi-asserted-by":"crossref","first-page":"2382","DOI":"10.1109\/TC.2012.224","article-title":"Design of an energy-efficient CMOS-compatible NoC architecture with millimeter-wave wireless interconnects","volume":"62","author":"Deb","year":"2013","journal-title":"IEEE Transactions on Computers"},{"key":"2026032901221666000_ref020","first-page":"406","volume-title":"Enhancing performance of wireless NoCs with distributed mac protocols","author":"Duraisamy","year":"2015"},{"key":"2026032901221666000_ref021","first-page":"147","volume-title":"High Performance and Energy Efficient Wireless NoC-Enabled Multicore Architectures for Graph Analytics","author":"Duraisamy","year":"2015"},{"key":"2026032901221666000_ref022","first-page":"17","article-title":"(On the evolution of random graphs)","volume":"5","author":"Erd\u00f6s","year":"1960","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"issue":"3-5","key":"2026032901221666000_ref023","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.physrep.2009.11.002","article-title":"Community detection in graphs","volume":"486","author":"Fortunato","year":"2010","journal-title":"Physics Reports"},{"key":"2026032901221666000_ref024","first-page":"7821","volume-title":"Community structure in social and biological networks","author":"Girvan","year":"2002"},{"key":"2026032901221666000_ref025","first-page":"1360","article-title":"The strength of weak ties","volume-title":"American Journal of Sociology","author":"Granovetter","year":"1973"},{"issue":"13","key":"2026032901221666000_ref026","first-page":"11","article-title":"Adapteva: More flops, less watts","volume":"6","author":"Gwennap","year":"2011","journal-title":"Microprocessor Report"},{"key":"2026032901221666000_ref027","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/978-3-540-77220-0_21","volume-title":"High Performance Computing-HiPC 2007","author":"Harish","year":"2007"},{"issue":"12","key":"2026032901221666000_ref028","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1016\/j.parco.2010.07.002","article-title":"Parallel graph component labelling with GPUs and CUDA","volume":"36","author":"Hawick","year":"2010","journal-title":"Parallel Computing"},{"key":"2026032901221666000_ref029","first-page":"78","volume-title":"Efficient parallel graph exploration on multi-core CPU and GPU","author":"Hong","year":"2011"},{"key":"2026032901221666000_ref030","volume-title":"The C++ Standard Library: A tutorial and reference","author":"Josuttis","year":"2012"},{"issue":"3","key":"2026032901221666000_ref031","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1145\/990308.990313","article-title":"On clusterings: Good, bad and spectral","volume":"51","author":"Kannan","year":"2004","journal-title":"Journal of the ACM"},{"key":"2026032901221666000_ref032","first-page":"1117","volume-title":"Encyclopedia of Parallel Computing","author":"Karypis","year":"2011"},{"issue":"1","key":"2026032901221666000_ref033","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","article-title":"A fast and high quality multilevel scheme for partitioning irregular graphs","volume":"20","author":"Karypis","year":"1998","journal-title":"SIAM Journal on Scientific Computing"},{"key":"2026032901221666000_ref034","first-page":"700","volume-title":"A contribution to the mathematical theory of epidemics","author":"Kermack","year":"1927"},{"issue":"10","key":"2026032901221666000_ref035","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/2398857.2384628","article-title":"Mitigating the compiler optimization phase-ordering problem using machine learning","volume":"47","author":"Kulkarni","year":"2012","journal-title":"ACM SIGPLAN Notices"},{"key":"2026032901221666000_ref036","first-page":"80","article-title":"Toward ideal on-chip communication using express virtual channels","volume-title":"IEEE Micro","author":"Kumar","year":"2008"},{"key":"2026032901221666000_ref037","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.jpdc.2014.09.012","article-title":"Multi-threaded modularity based graph clustering using the multilevel paradigm","volume":"76","author":"LaSalle","year":"2015","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"2026032901221666000_ref038","first-page":"469","volume-title":"Mcpat: an integrated power, area, and timing modeling framework for multicore and manycore architectures","author":"Li","year":"2009"},{"key":"2026032901221666000_ref039","unstructured":"Louvain\n            \n          . findcommunities. URL https:\/\/sites.google.com\/site\/findcommunities\/."},{"key":"2026032901221666000_ref040","first-page":"7","volume-title":"Balanced coloring for parallel computing applications","author":"Lu","year":"2015"},{"key":"2026032901221666000_ref041","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.parco.2015.03.003","article-title":"Parallel heuristics for scalable community detection","volume":"47","author":"Lu","year":"2015","journal-title":"Parallel Computing"},{"key":"2026032901221666000_ref042","first-page":"52","volume-title":"An effective GPU implementation of breadth-first search","author":"Luo","year":"2010"},{"key":"2026032901221666000_ref043","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2172\/951102","volume-title":"A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets","author":"Madduri","year":"2009"},{"key":"2026032901221666000_ref044","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1007\/978-3-540-68111-3_74","volume-title":"Parallel Processing and Applied Mathematics","author":"Manne","year":"2008"},{"issue":"1","key":"2026032901221666000_ref045","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TCAD.2008.2010691","article-title":"Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives","volume":"28","author":"Marculescu","year":"2009","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"2026032901221666000_ref046","first-page":"117","volume-title":"ACM SIGPLAN Notices","author":"Merrill","year":"2012"},{"issue":"2","key":"2026032901221666000_ref047","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/2717511","article-title":"High-performance and scalable GPU graph traversal","volume":"1","author":"Merrill","year":"2015","journal-title":"ACM Transactions on Parallel Computing"},{"issue":"1","key":"2026032901221666000_ref048","first-page":"60","article-title":"The small world problem","volume":"2","author":"Milgram","year":"1967","journal-title":"Psychology Today"},{"key":"2026032901221666000_ref049","article-title":"Introducing the graph 500","volume-title":"Cray Users Group (CUG)","author":"Murphy","year":"2010"},{"issue":"5","key":"2026032901221666000_ref050","doi-asserted-by":"crossref","first-page":"056131","DOI":"10.1103\/PhysRevE.70.056131","article-title":"Analysis of weighted networks","volume":"70","author":"Mark","year":"2004","journal-title":"Physical Review E"},{"issue":"2","key":"2026032901221666000_ref051","doi-asserted-by":"crossref","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","article-title":"Finding and evaluating community structure in networks","volume":"69","author":"Mark","year":"2004","journal-title":"Physical Review E"},{"issue":"2","key":"2026032901221666000_ref052","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","article-title":"The structure and function of complex networks","volume":"45","author":"Mark","year":"2003","journal-title":"SIAM Review"},{"issue":"6","key":"2026032901221666000_ref053","doi-asserted-by":"crossref","first-page":"066133","DOI":"10.1103\/PhysRevE.69.066133","article-title":"Fast algorithm for detecting community structure in networks","volume":"69","author":"Mark","year":"2004","journal-title":"Physical Review E"},{"key":"2026032901221666000_ref054","first-page":"246","volume-title":"Application-specific network-on-chip architecture customization via long-range link insertion","author":"Ogras","year":"2005"},{"issue":"7","key":"2026032901221666000_ref055","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1109\/TVLSI.2006.878263","article-title":"\u201cIt\u2019s a small world after all\u201d: NoC performance optimization via long-range link insertion","volume":"14","author":"Ogras","year":"2006","journal-title":"IEEE Transactions on Very Large Scale Integration (VLSI) Systems"},{"issue":"3","key":"2026032901221666000_ref056","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/s10618-011-0224-z","article-title":"Community detection in social media","volume":"24","author":"Papadopoulos","year":"2012","journal-title":"Data Mining and Knowledge Discovery"},{"key":"2026032901221666000_ref057","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/3-540-36233-9_15","volume-title":"Databases in Networked Information Systems","author":"Krishna Reddy","year":"2002"},{"key":"2026032901221666000_ref058","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/978-3-642-31464-3_29","volume-title":"Parallel Processing and Applied Mathematics","author":"Jason Riedy","year":"2012"},{"issue":"8","key":"2026032901221666000_ref059","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","volume":"22","author":"Shi","year":"2000","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"2","key":"2026032901221666000_ref060","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/BF02478357","article-title":"Connectivity of random nets","volume":"13","author":"Solomonoff","year":"1951","journal-title":"The Bulletin of Mathematical Biophysics"},{"key":"2026032901221666000_ref061","first-page":"568","volume-title":"Fast community detection algorithm with GPUs and multicore architectures","author":"Soman","year":"2011"},{"key":"2026032901221666000_ref062","first-page":"1","volume-title":"A fast GPU algorithm for graph connectivity","author":"Soman","year":"2010"},{"key":"2026032901221666000_ref063","first-page":"180","volume-title":"Engineering high-performance community detection heuristics for massive graphs","author":"Staudt","year":"2013"},{"issue":"5","key":"2026032901221666000_ref064","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1002\/sam.10100","article-title":"Complex networks as a unified framework for descriptive analysis and predictive modeling in climate science","volume":"4","author":"Steinhaeuser","year":"2011","journal-title":"Statistical Analysis and Data Mining: The ASA Data Science Journal"},{"issue":"1","key":"2026032901221666000_ref065","doi-asserted-by":"crossref","first-page":"016114","DOI":"10.1103\/PhysRevE.84.016114","article-title":"Narrow scope for resolution-limit-free community detection","volume":"84","author":"Traag","year":"2011","journal-title":"Physical Review E"},{"key":"2026032901221666000_ref066","doi-asserted-by":"crossref","DOI":"10.1515\/9780691188331","volume-title":"Small worlds: the dynamics of networks between order and randomness","author":"Watts","year":"1999"},{"issue":"6684","key":"2026032901221666000_ref067","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2018small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"issue":"11","key":"2026032901221666000_ref068","doi-asserted-by":"crossref","first-page":"1732","DOI":"10.1109\/TCAD.2014.2351577","article-title":"Design space exploration for wireless nocs incorporating irregular network routing","volume":"33","author":"Wettin","year":"2014","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"2026032901221666000_ref069","first-page":"21","article-title":"A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, FRS","volume-title":"Philosophical Transactions of the Royal Society of London. Series B, Containing Papers of a Biological Character","author":"Yule","year":"1925"},{"issue":"6","key":"2026032901221666000_ref070","doi-asserted-by":"crossref","first-page":"1543","DOI":"10.1109\/TPDS.2013.111","article-title":"Medusa: Simplified graph processing on GPUs","volume":"25","author":"Zhong","year":"2014","journal-title":"IEEE Transactions on Parallel and Distributed Systems"}],"container-title":["Foundations and Trends\u00ae in Electronic Design Automation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fteda\/article-pdf\/10\/3\/145\/10902126\/1000000044en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fteda\/article-pdf\/10\/3\/145\/10902126\/1000000044en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T14:13:41Z","timestamp":1777472021000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fteda\/article\/10\/3\/145\/1320862\/Fast-Uncovering-of-Graph-Communities-on-a-Chip"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,19]]},"references-count":70,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,8,19]]}},"URL":"https:\/\/doi.org\/10.1561\/1000000044","relation":{},"ISSN":["1551-3939","1551-3947"],"issn-type":[{"value":"1551-3939","type":"print"},{"value":"1551-3947","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,19]]}}}