| 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
:
|
12580213 - Monitoring of isoflurane and desflurane breakdown: interfering gases and infrared detec... 22461153 - A convenient method for electron tomography sample preparation using a focused ion beam. 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.