Den klassiska miljön för samhällsdetektion består av nätverk som uppvisar en klusterstruktur. För att mer exakt modellera verkliga system anser vi en klass av nätverk (i) vars kanter kan bära etiketter och (ii) som kan sakna en klusterstruktur. Speciellt antar vi att noder har latenta attribut hämtade från ett allmänt kompakt utrymme och kanter mellan två noder genereras slumpmässigt och märkas enligt någon okänd fördelning som en funktion av deras latenta attribut. Vårt mål är då att härleda kantetikettdistributionerna från ett delvis observerat nätverk. Vi föreslår en beräkningseffektiv spektralalgoritm och visar att den möjliggör asymptotiskt korrekt slutledning när den genomsnittliga nodgraden kan vara så låg som logaritmisk i det totala antalet noder. Omvänt, om den genomsnittliga nodgraden är under en specifik konstant tröskel, visar vi att ingen algoritm kan uppnå bättre slutledning än gissning utan att använda observationer. Som en biprodukt av vår analys visar vi att vår modell ger en allmän procedur för att konstruera slumpmässiga grafmodeller med ett spektrum asymptotiskt till en förspecificerad eigen value distribution såsom en power-law distribution.
I REF föreslogs en spektral klustereringsmetod för att sluta sig till eggetikettdistributionen för ett nätverk som provtagits från en generaliserad stokastisk blockmodell.
Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results
{'venue': 'COLT', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}