Signerade nätverk innehåller kantnoter för att indikera om varje interaktion är vänlig (positiv kant) eller antagonistisk (negativ kant). Modellen är enkel men kraftfull och den kan fånga nya och intressanta strukturella egenskaper hos verkliga fenomen. Analysen av signerade nätverk har många tillämpningar från modellering diskussioner i sociala medier, gruv användarrecensioner, och att rekommendera produkter i e-handelssajter. I detta dokument överväger vi problemet med att upptäcka polariserade samhällen i signerade nätverk. I synnerhet söker vi efter två samhällen (undergrupper av nätverket hörn) där inom samhällen det finns mestadels positiva kanter medan över samhällen finns mestadels negativa kanter. Vi formulerar detta nya problem som en "diskrete eigenvector" problem, som vi visar att vara NP-hård. Vi utvecklar sedan två intuitiva spektralalalgoritmer: en deterministisk, och en randomiserad med kvalitetsgaranti ε n (där n är antalet hörn i grafen), tight upp till konstanta faktorer. Vi validerar våra algoritmer mot icke-triviala baslinjer på verkliga signerade nätverk. Våra experiment bekräftar att våra algoritmer producerar lösningar av högre kvalitet, är mycket snabbare och kan skala till mycket större nätverk än baslinjerna, och kan upptäcka marksanning polariserade samhällen.
Slutligen, en nyare arbetslinje introducerar problemet med att upptäcka antagonistiska samhällen i undertecknade nätverk REF.
Discovering Polarized Communities in Signed Networks
{'venue': "CIKM '19", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}