| Автор | Allahverdyan, A. E. |
| Автор | Ver Steeg, G. |
| Автор | Galstyan, A. |
| Дата выпуска | 2010-04-01 |
| dc.description | We study the problem of graph partitioning, or clustering, in sparse networks with prior information about the clusters. Specifically, we assume that for a fraction ρ of the nodes their true cluster assignments are known in advance. This can be understood as a semi-supervised version of clustering, in contrast to unsupervised clustering where the only available information is the graph structure. In the unsupervised case, it is known that there is a threshold of the inter-cluster connectivity beyond which clusters cannot be detected. Here we study the impact of the prior information on the detection threshold, and show that even minute (but generic) values of ρ>0 shift the threshold downwards to its lowest possible value. For weighted graphs we show that a small semi-supervising can be used for a non-trivial definition of communities. |
| Формат | application.pdf |
| Издатель | Institute of Physics Publishing |
| Копирайт | Europhysics Letters Association |
| Название | Community detection with and without prior information |
| Тип | lett |
| DOI | 10.1209/0295-5075/90/18002 |
| Electronic ISSN | 1286-4854 |
| Print ISSN | 0295-5075 |
| Журнал | EPL (Europhysics Letters) |
| Том | 90 |
| Первая страница | 18002 |
| Последняя страница | 18007 |
| Аффилиация | Allahverdyan, A. E.; Yerevan Physics Institute - Alikhanian Brothers Street 2, Yerevan 375036, Armenia |
| Аффилиация | Ver Steeg, G.; Information Sciences Institute, University of Southern California - Marina del Rey, CA 90292, USA |
| Аффилиация | Galstyan, A.; Information Sciences Institute, University of Southern California - Marina del Rey, CA 90292, USA |
| Выпуск | 1 |
