Document Detail


Graph spectra and the detectability of community structure in networks.
MedLine Citation:
PMID:  22681123     Owner:  NLM     Status:  In-Data-Review    
Abstract/OtherAbstract:
We study networks that display community structure-groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods, we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.
Authors:
Raj Rao Nadakuditi; M E J Newman
Related Documents :
23757343 - Microfluidic multiplexing in bioanalyses.
12580213 - Monitoring of isoflurane and desflurane breakdown: interfering gases and infrared detec...
7126263 - Identification and measurement of 6-hydroxy-1-methyl-1,2,3,4-tetrahydro-beta-carboline ...
Publication Detail:
Type:  Journal Article     Date:  2012-05-01
Journal Detail:
Title:  Physical review letters     Volume:  108     ISSN:  1079-7114     ISO Abbreviation:  Phys. Rev. Lett.     Publication Date:  2012 May 
Date Detail:
Created Date:  2012-06-11     Completed Date:  -     Revised Date:  -    
Medline Journal Info:
Nlm Unique ID:  0401141     Medline TA:  Phys Rev Lett     Country:  United States    
Other Details:
Languages:  eng     Pagination:  188701     Citation Subset:  IM    
Affiliation:
Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, Michigan 48109, USA.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Bubble Rearrangement Duration in Foams near the Jamming Point.
Next Document:  Synchronous melanoma and renal carcinoma: a clinicopathological study of five cases.