{"doi":"10.1103/physreve.70.066111","title":"Finding community structure in very large networks","abstract":"The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m approximately n and d approximately log n, in which case our algorithm runs in essentially linear time, O (n log(2) n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web site of a large on-line retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400 000 vertices and 2 x 10(6) edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.","journal":"Physical Review E","year":2004,"id":10867,"datarank":21.884752209958805,"base_score":8.914894908906568,"endowment":8.914894908906568,"self_citation_contribution":1.3372342363359855,"citation_network_contribution":20.54751797362282,"self_endowment_contribution":1.3372342363359855,"citer_contribution":20.54751797362282,"corpus_percentile":93.6,"corpus_rank":2041,"citation_count":7441,"citer_count":190,"citers_with_citation_signal":190,"citers_with_endowment":190,"datacite_reuse_total":0,"is_dataset":false,"is_oa":true,"file_count":0,"downloads":0,"has_version_chain":false,"published_date":"2004-12-06","authors":[{"id":39648,"name":"M. E. J. Newman","orcid":"0000-0002-0907-1660","position":1,"is_corresponding":false},{"id":88760,"name":"Cristopher Moore","orcid":"0000-0002-2062-1942","position":2,"is_corresponding":false},{"id":85918,"name":"Aaron Clauset","orcid":"0000-0002-3529-8746","position":0,"is_corresponding":true}],"reference_count":34,"raw_metadata":{"citation_network_status":"fetched"},"created_at":"2026-03-01T18:20:47.508186Z","pmid":null,"pmcid":null,"fwci":null,"citation_percentile":null,"influential_citations":0,"oa_status":null,"license":null,"views":0,"total_file_size_bytes":0,"version_count":0,"clinical_trials":[],"software_tools":[],"db_accessions":[],"linked_datasets":[],"topics":[]}