%0 Journal Article %1 0295-5075-90-1-18002 %A Allahverdyan, A. E. %A Steeg, G. Ver %A Galstyan, A. %D 2010 %J EPL (Europhysics Letters) %K based clustering community constrained detection graph %N 1 %P 18002 %T Community detection with and without prior information %U http://stacks.iop.org/0295-5075/90/i=1/a=18002 %V 90 %X 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.

@article{0295-5075-90-1-18002, abstract = {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.}, added-at = {2010-07-08T12:16:56.000+0200}, author = {Allahverdyan, A. E. and Steeg, G. Ver and Galstyan, A.}, biburl = {https://www.bibsonomy.org/bibtex/2ec9d64b1e2f6dda9830589084d3a8d2d/folke}, interhash = {8095a5facd7e6331a264edd0fba73bb2}, intrahash = {ec9d64b1e2f6dda9830589084d3a8d2d}, journal = {EPL (Europhysics Letters)}, keywords = {based clustering community constrained detection graph}, number = 1, pages = 18002, timestamp = {2010-07-08T12:16:56.000+0200}, title = {Community detection with and without prior information}, url = {http://stacks.iop.org/0295-5075/90/i=1/a=18002}, volume = 90, year = 2010 }