%PDF-1.3
1 0 obj
<<
/Kids [ 4 0 R 5 0 R 6 0 R 7 0 R 8 0 R 9 0 R 10 0 R 11 0 R 12 0 R ]
/Type /Pages
/Count 9
>>
endobj
2 0 obj
<<
/Subject (Neural Information Processing Systems http\072\057\057nips\056cc\057)
/Publisher (Curran Associates\054 Inc\056)
/Language (en\055US)
/Created (2016)
/EventType (Poster)
/Description-Abstract (We consider the problem of community detection or clustering in the labeled Stochastic Block Model \050LSBM\051 with a finite number \044K\044 of clusters of sizes linearly growing with the global population of items \044n\044\056 Every pair of items is labeled independently at random\054 and label \044\134ell\044 appears with probability \044p\050i\054j\054\134ell\051\044 between two items in clusters indexed by \044i\044 and \044j\044\054 respectively\056 The objective is to reconstruct the clusters from the observation of these random labels\056 Clustering under the SBM and their extensions has attracted much attention recently\056 Most existing work aimed at characterizing the set of parameters such that it is possible to infer clusters either positively correlated with the true clusters\054 or with a vanishing proportion of misclassified items\054 or exactly matching the true clusters\056 We find the set of parameters such that there exists a clustering algorithm with at most \044s\044 misclassified items in average under the general LSBM and for any \044s\075o\050n\051\044\054 which solves one open problem raised in \134cite\173abbe2015community\175\056 We further develop an algorithm\054 based on simple spectral methods\054 that achieves this fundamental performance limit within \044O\050n \134mbox\173polylog\175\050n\051\051\044 computations and without the a\055priori knowledge of the model parameters\056)
/Producer (PyPDF2)
/Title (Optimal Cluster Recovery in the Labeled Stochastic Block Model)
/Date (2016)
/ModDate (D\07220170112170256\05508\04700\047)
/Published (2016)
/Type (Conference Proceedings)
/firstpage (965)
/Book (Advances in Neural Information Processing Systems 29)
/Description (Paper accepted and presented at the Neural Information Processing Systems Conference \050http\072\057\057nips\056cc\057\051)
/Editors (D\056D\056 Lee and M\056 Sugiyama and U\056V\056 Luxburg and I\056 Guyon and R\056 Garnett)
/Author (Se\055Young Yun\054 Alexandre Proutiere)
/lastpage (973)
>>
endobj
3 0 obj
<<
/Type /Catalog
/Pages 1 0 R
>>
endobj
4 0 obj
<<
/Contents 13 0 R
/Parent 1 0 R
/Resources 14 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 53 0 R 54 0 R 55 0 R ]
/Type /Page
>>
endobj
5 0 obj
<<
/Contents 56 0 R
/Parent 1 0 R
/Resources 57 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 82 0 R 83 0 R 84 0 R 85 0 R 86 0 R 87 0 R 88 0 R 89 0 R 90 0 R 91 0 R 92 0 R 93 0 R 94 0 R 95 0 R ]
/Type /Page
>>
endobj
6 0 obj
<<
/Contents 96 0 R
/Parent 1 0 R
/Resources 97 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 102 0 R 103 0 R 104 0 R 105 0 R 106 0 R 107 0 R 108 0 R ]
/Type /Page
>>
endobj
7 0 obj
<<
/Contents 109 0 R
/Parent 1 0 R
/Resources 110 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 111 0 R 112 0 R 113 0 R 114 0 R 115 0 R 116 0 R 117 0 R 118 0 R 119 0 R 120 0 R 121 0 R 122 0 R 123 0 R 124 0 R 125 0 R 126 0 R 127 0 R 128 0 R 129 0 R 130 0 R ]
/Type /Page
>>
endobj
8 0 obj
<<
/Contents 131 0 R
/Parent 1 0 R
/Resources 132 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 133 0 R 134 0 R 135 0 R 136 0 R 137 0 R ]
/Type /Page
>>
endobj
9 0 obj
<<
/Contents 138 0 R
/Parent 1 0 R
/Resources 139 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 140 0 R 141 0 R 142 0 R 143 0 R ]
/Type /Page
>>
endobj
10 0 obj
<<
/Contents 144 0 R
/Parent 1 0 R
/Resources 145 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 146 0 R 147 0 R 148 0 R 149 0 R 150 0 R 151 0 R 152 0 R 153 0 R 154 0 R 155 0 R 156 0 R 157 0 R ]
/Type /Page
>>
endobj
11 0 obj
<<
/Contents 158 0 R
/Parent 1 0 R
/Resources 159 0 R
/MediaBox [ 0 0 612 792 ]
/Annots [ 160 0 R 161 0 R 162 0 R 163 0 R ]
/Type /Page
>>
endobj
12 0 obj
<<
/Contents 164 0 R
/Parent 1 0 R
/Type /Page
/Resources 165 0 R
/MediaBox [ 0 0 612 792 ]
>>
endobj
13 0 obj
<<
/Length 3754
/Filter /FlateDecode
>>
stream
xZo~>ҀrhKZ-Pm1G
IŹٙ-;\cfvϯJ\IRřv]}Ƙ8fu#8W֨1Jj-e]nvh7
Q|n}ݫ`}A+@w