Trust nätverk, där människor lämnar förtroende och misstro feedback, blir allt vanligare. Dessa nätverk kan betraktas som signerade grafer, där en positiv kantvikt fångar graden av tillit medan en negativ kantvikt fångar graden av misstro. Analys av sådana signerade nätverk har blivit ett allt viktigare forskningsämne. En viktig analysuppgift är den om teckeninferens, d.v.s. om okänd (eller framtida) tillit eller misstro relationer med tanke på ett delvis observerat signerat nätverk. De flesta state-of-the-art metoder överväga begreppet strukturell balans i undertecknade nätverk, bygga inference algoritmer som bygger på information om länkar, triader och cykler i nätverket. I detta dokument visar vi först att begreppet svag strukturell balans i tecknade nätverk naturligtvis leder till en global modell med låga rankningar för nätet. Under en sådan modell, tecken inference problem kan formuleras som en låg-rank matris slutföra problem. Vi visar att vi helt kan återställa saknade relationer, under vissa förhållanden, med hjälp av toppmoderna matriskompletteringsalgoritmer. Vi föreslår också användning av en låg-rankad matris factorization metod med generaliserade förlustfunktioner som en praktisk metod för tecken inference -detta tillvägagångssätt ger hög noggrannhet samtidigt som den är skalbar till stora signerade nätverk, till exempel, visar vi att denna analys kan utföras på en syntetisk graf med 1,1 miljoner noder och 120 miljoner kanter på 10 minuter. Vi visar vidare att modellen med låg rankning kan användas för andra analysuppgifter på signerade nätverk, såsom användarsegmentering genom signerad grafklustring, med teoretiska garantier. Experiment på syntetiska såväl som verkliga data visar att vår modell med låga rankningar avsevärt förbättrar exaktheten av teckeninferens samt klusterbildning. Som ett exempel, på den största verkliga datauppsättning som finns tillgänglig för oss (Epinions data med 130K noder och 840K kanter), vår matris factorization approach ger 94,6% noggrannhet på tecken inference uppgift jämfört med 90,8% noggrannhet med hjälp av en toppmodern cykelbaserad metod - dessutom, vår metod körs i 40 sekunder jämfört med 10 000 sekunder för den cykelbaserade metoden.
REF modellerar matematiskt förtroende och misstro förutsägelse problem som en låg-rank matris faktorisering modell, baserat på den svaga strukturella balansen på förtroende / missbruk nätverk.
Low rank modeling of signed networks
{'venue': 'KDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}