Vi föreslår en mycket kompakt tvådelad representation av en given graf G som består av en grafsammanfattning och en uppsättning korrigeringar. Diagramsammanfattningen är en aggregerad graf där varje nod motsvarar en uppsättning noder i G, och varje kant representerar kanterna mellan alla noder i de två uppsättningarna. Å andra sidan anger korrigeringsdelen listan över kantkorrigeringar som ska tillämpas på sammanfattningen för att återskapa G. Våra representationer möjliggör både förlustfri och förlustfri grafkompression med gränser för det införda felet. Dessutom, i kombination med MDL-principen, ger de mycket intuitiva grova-nivå sammanfattningar av ingångsgraf G. Vi utvecklar algoritmer för att konstruera starkt komprimerade graf representationer med små storlekar och garanterad noggrannhet, och validera vår strategi genom en omfattande uppsättning experiment med flera verkliga grafdata. Såvitt vi vet är detta det första arbetet med att beräkna grafsammanfattningar med hjälp av MDL-principen och använda sammanfattningarna (tillsammans med rättelser) för att komprimera grafer med begränsat fel.
Den senaste tidens arbete av Navlakha et al. REF använder MDL-principen för att komprimera grafer med begränsat fel.
Graph summarization with bounded error
{'venue': 'SIGMOD Conference', 'journal': None, 'mag_field_of_study': ['Computer Science']}