Den stokastiska blockmodellen är en av de äldsta och mest allmänt förekommande modellerna för att studera klusterbildning och community detektion. I en spännande sekvens av utveckling, motiverad av djupa men icke-rigorösa idéer från statistisk fysik, Decelle et al. Antaget en skarp tröskel för när det är möjligt att upptäcka samhället i det glesa systemet. Mossel, Neeman och Sly och Massoulié bevisade hypotesen och gav matchande algoritmer och lägre gränser. Här ser vi tillbaka på den stokastiska blockmodellen ur semirandommodellernas perspektiv där vi låter en motståndare göra "hjälpsamma" förändringar som stärker banden inom varje samhälle och bryter banden mellan dem. Vi visar ett överraskande resultat att dessa "hjälpsamma" förändringar kan förskjuta den informationsteoretiska tröskeln, vilket gör problemet med att upptäcka samhället strängt svårare. Vi kompletterar detta genom att visa att en algoritm baserad på semidefinit programmering (som var känd för att komma nära tröskeln) fortsätter att fungera i semirandom modellen (även för partiell återhämtning). Detta tyder på att algoritmer baserade på semidefinit programmering är robusta på ett sätt som alla algoritmer som uppfyller den informations-teoretiska tröskeln inte kan vara. Dessa resultat pekar på en intressant ny riktning: Kan vi hitta robusta, semirandoma analoger till några av de klassiska, genomsnittliga-fall-trösklarna i statistiken? Vi utforskar också denna fråga i modellen för sändningsträd, och vi visar att semirandommodellernas syn kan bidra till att förklara varför vissa algoritmer föredras framför andra i praktiken, trots luckorna i deras statistiska prestanda på slumpmässiga modeller.
Detta beslut träder i kraft dagen efter det att det har offentliggjorts i Europeiska unionens officiella tidning. REF gav algoritmer (baserat på semidefinit programmering) och lägre gränser för partiell återhämtning i den stokastiska blockmodellen med en monoton motståndare.
How robust are reconstruction thresholds for community detection?
{'venue': 'STOC 2016', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}