Vi fortsätter forskningen om grafkompression startade i [BV04], men vi flyttar vårt fokus till komprimering av sociala nätverk i rätt mening (t.ex., LiveJournal): de metoder som har använts under en lång tid för att komprimera webbgrafer förlitar sig på en specifik beställning av noderna (lexikografiska URL-beställning) vars utvidgning till allmänna sociala nätverk är inte trivialt. I detta dokument föreslår vi en lösning som blandar kluster och order, och utformar en ny algoritm, kallad Layered Label Propagation, som bygger på tidigare arbete med skalbara kluster och kan användas för att omordna mycket stora grafer (miljarder noder). Vår implementering använder uppgift sönderdelning för att utföra aggressivt på multi-core arkitektur, vilket gör det möjligt att ändra ordning grafer på mer än 600 miljoner noder på några timmar. Experiment utförda på ett brett spektrum av webbgrafer och sociala nätverk visar att kombinera den ordning som produceras av den föreslagna algoritmen med WebGraph komprimering ram ger en stor ökning av komprimering med avseende på alla för närvarande kända tekniker, både på webbgrafer och på sociala nätverk. Dessa förbättringar gör det möjligt att analysera i huvudminnet betydligt större grafer.
Mycket nyligen, Vigna et al. REF införde en skiktad algoritm för spridning av etiketter för omordning av mycket stora grafer.
Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science', 'Physics']}