Finding Planted Partitions in Random Graphs with General Degree Distributions

DOI10.1137/070699354zbMath1207.05178OpenAlexW2090731451MaRDI QIDQ3058526

Amin Coja-Oghlan, André Lanka

Publication date: 3 December 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/43264/1/WRAP_Coja-Oghlan_fppac.pdf

zbMATH Keywords

algorithmspartitioningrandom graphsspectral methods

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (13)

An impossibility result for reconstruction in the degree-corrected stochastic block model ⋮ Maximum cliques in graphs with small intersection number and random intersection graphs ⋮ The expected adjacency and modularity matrices in the degree corrected stochastic block model ⋮ Convexified modularity maximization for degree-corrected stochastic block models ⋮ Consistency of community detection in networks under degree-corrected stochastic block models ⋮ Matrix and discrepancy view of generalized random and quasirandom graphs ⋮ Unnamed Item ⋮ A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection ⋮ Generalized quasirandom properties of expanding graph sequences ⋮ A spectral method for community detection in moderately sparse degree-corrected stochastic block models ⋮ Unnamed Item ⋮ Bootstrap percolation on the stochastic block model ⋮ Robust and computationally feasible community detection in the presence of arbitrary outlier nodes

This page was built for publication: Finding Planted Partitions in Random Graphs with General Degree Distributions