@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 = {http://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},
  title = {Community detection with and without prior information},
  url = {http://stacks.iop.org/0295-5075/90/i=1/a=18002},
  volume = {90},
  year = {2010}
}

{"_id":{"_str":"5343952bf1c2d1f22d000050"},"__v":0,"authorIDs":[],"author_short":["Allahverdyan, A.<nbsp>E.","Steeg","Ver, G.","Galstyan, A."],"bibbaseid":"allahverdyan-steeg-ver-galstyan-communitydetectionwithandwithoutpriorinformation-2010","bibdata":{"html":"","downloads":0,"keyword":["based clustering community constrained detection graph"],"bibbaseid":"allahverdyan-steeg-ver-galstyan-communitydetectionwithandwithoutpriorinformation-2010","urls":{"Paper":"http://stacks.iop.org/0295-5075/90/i=1/a=18002"},"role":"author","year":"2010","volume":"90","url":"http://stacks.iop.org/0295-5075/90/i=1/a=18002","type":"article","title":"Community detection with and without prior information","pages":"18002","number":"1","keywords":"based clustering community constrained detection graph","key":"0295-5075-90-1-18002","journal":"EPL (Europhysics Letters)","intrahash":"ec9d64b1e2f6dda9830589084d3a8d2d","interhash":"8095a5facd7e6331a264edd0fba73bb2","id":"0295-5075-90-1-18002","biburl":"http://www.bibsonomy.org/bibtex/2ec9d64b1e2f6dda9830589084d3a8d2d/folke","bibtype":"article","bibtex":"@article{ 0295-5075-90-1-18002,\n 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.},\n added-at = {2010-07-08T12:16:56.000+0200},\n author = {Allahverdyan, A. E. and Steeg, G. Ver and Galstyan, A.},\n biburl = {http://www.bibsonomy.org/bibtex/2ec9d64b1e2f6dda9830589084d3a8d2d/folke},\n interhash = {8095a5facd7e6331a264edd0fba73bb2},\n intrahash = {ec9d64b1e2f6dda9830589084d3a8d2d},\n journal = {EPL (Europhysics Letters)},\n keywords = {based clustering community constrained detection graph},\n number = {1},\n pages = {18002},\n title = {Community detection with and without prior information},\n url = {http://stacks.iop.org/0295-5075/90/i=1/a=18002},\n volume = {90},\n year = {2010}\n}","author_short":["Allahverdyan, A.<nbsp>E.","Steeg","Ver, G.","Galstyan, A."],"author":["Allahverdyan, A. E.","Steeg","Ver, G.","Galstyan, A."],"added-at":"2010-07-08T12:16:56.000+0200","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."},"bibtype":"article","biburl":"http://www.bibsonomy.org/bib/author/galstyan?items=1000","downloads":0,"keywords":["based clustering community constrained detection graph"],"search_terms":["community","detection","without","prior","information","allahverdyan","steeg","ver","galstyan"],"title":"Community detection with and without prior information","year":2010,"dataSources":["R8Danh2qkDD99G9eu"]}