Grafer används ofta för att modellera verkliga objekt och deras relationer, och stora grafdatauppsättningar är vanliga inom många tillämpningsområden. För att förstå de underliggande egenskaperna hos stora grafer, grafsammanfattning tekniker är kritiska. Befintliga grafsammanfattningsmetoder är dock främst statistiska (studiestatistik såsom gradfördelningar, humleplot och klusterkoefficienter). Dessa statistiska metoder är mycket användbara, men besluten i sammanfattningarna är svåra att kontrollera. I det här dokumentet introducerar vi två databasliknande operationer för att sammanfatta grafer. Liksom OLAP-stilen aggregeringsmetoder som gör det möjligt för användare att borra ner eller rulla upp för att styra upplösningen av summering, våra metoder ger en analog funktionalitet för stora grafdataset. Den första åtgärden, kallad SNAP, producerar en sammanfattande graf genom att gruppera noder baserat på användarvalda nodattribut och relationer. Den andra operationen, som kallas k-SNAP, gör det dessutom möjligt för användare att kontrollera upplösningar av sammanfattningar och ger "borra ner" och "roll-up" förmåga att navigera genom sammanfattningar med olika upplösningar. Vi föreslår en effektiv algoritm för att utvärdera SNAP-operationen. Dessutom bevisar vi att k-SNAP-beräkningen är NPfullständig. Vi föreslår två heuristiska metoder för att approximera k-SNAP-resultaten. Genom omfattande experiment på en mängd olika verkliga och syntetiska datauppsättningar visar vi hur effektiva och effektiva de föreslagna metoderna är.
Å andra sidan, Tian et al. REF föreslog OLAP-liknande aggregeringsmetoder för att sammanfatta stora grafer genom att gruppera noder baserade på användarvalda attribut och relationer.
Efficient aggregation for graph summarization
{'venue': 'SIGMOD Conference', 'journal': None, 'mag_field_of_study': ['Computer Science']}