TY - GEN
T1 - Spectral clustering for multiclass Erdös-Rényi graphs
AU - Belabbas, Mohamed Ali
PY - 2010
Y1 - 2010
N2 - In this article, we study the properties of the spectral analysis of multiclass Erdös-Rényi graphs. With a view towards using the embedding afforded by the decomposition of the graph Laplacian for subsequent processing, we analyze two basic geometric properties, namely interclass intersection and interclass distance. We will first study the dyadic two-class case in details and observe the existence of a phase transition for the interclass intersection. We then focus on the general multiclass case, where we introduce an appropriate notion of diagonal concentration and derive a statistical model that allows sampling graphs whose expected diagonal concentration is fixed. The simulations provided yield useful guidelines for practitioners to choose appropriately parameters in the context of spectral clustering.
AB - In this article, we study the properties of the spectral analysis of multiclass Erdös-Rényi graphs. With a view towards using the embedding afforded by the decomposition of the graph Laplacian for subsequent processing, we analyze two basic geometric properties, namely interclass intersection and interclass distance. We will first study the dyadic two-class case in details and observe the existence of a phase transition for the interclass intersection. We then focus on the general multiclass case, where we introduce an appropriate notion of diagonal concentration and derive a statistical model that allows sampling graphs whose expected diagonal concentration is fixed. The simulations provided yield useful guidelines for practitioners to choose appropriately parameters in the context of spectral clustering.
KW - Community detection
KW - Non-Euclidean datasets
KW - Random graph models
KW - Spectral graph theory
UR - http://www.scopus.com/inward/record.url?scp=78049381681&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78049381681&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2010.5494932
DO - 10.1109/ICASSP.2010.5494932
M3 - Conference contribution
AN - SCOPUS:78049381681
SN - 9781424442966
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 5422
EP - 5425
BT - 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2010 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2010
Y2 - 14 March 2010 through 19 March 2010
ER -