Komprimerande sociala nätverk kan avsevärt underlätta gruvdrift och avancerad analys av stora sociala nätverk. Sociala nätverk bör helst komprimeras på ett sådant sätt att de fortfarande kan ifrågasättas effektivt utan dekompression. Grannfrågor, som söker efter alla grannar i en fråga vertex, är utan tvekan de viktigaste operationerna på sociala nätverk. Kan vi komprimera sociala nätverk effektivt i en granne fråga vänligt sätt, dvs grannen frågor fortfarande kan besvaras i sublinjär tid med hjälp av komprimering? I detta dokument utvecklar vi en effektiv komprimeringsstrategi för sociala nätverk som uppnås genom en ny eulersk datastruktur med hjälp av multipositionslineariseringar av riktade grafer. Vår metod kommer med en icke-trivial teoretisk bunden på kompressionshastigheten. Såvitt vi vet är vårt tillvägagångssätt det första som kan besvara både frågor om grannar och grannar i sublinjär tid. En omfattande empirisk studie av mer än ett dussin riktmärken verkliga data som verifierar vår design.
Maserrat och Pei REF-schema uppnår kompression genom att definiera en eulersk datastruktur med hjälp av multipositionslinearisering av riktade grafer.
Neighbor query friendly compression of social networks
{'venue': "KDD '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}