Distributed distance-preserving graph approximations

Abstract

Det er en voksende interesse for forskning og analyse av store grafer. Disse grafene kan være grafer man blant annet finner i sosiale medier, hvordan nettsider linker til hverandre og hvordan smitte sprer seg i globale befolkninger. Disse grafene kan ha milliarder med noder og billioner med kanter. Det kan være vanskelig å håndtere og effektivt prosessere grafer på denne størrelsen. Det finnes teknikker for å lage tilnærminger av grafer som kan hjelpe på disse utfordringene. Størrelsen på disse grafene gjør at det kan være vanskelig i seg selv å lage slike tilnærminger. Et problem er at vanlige løsninger kjørende på enkeltdatamaskiner ikke skalerer til denne skalaen. Vi har utforsket og implementert løsninger med teknikkene nodesammenslåing, grafspennere og hopsett. Dette har vi gjort med de distribuerte rammeverkene Pregel og Spark. Vi har gjennomført tester på et distribuert datasystem med storskala grafer hentet fra den virkelige verden. Vi har gjennom våre tester vist at det er mulig å lage skalerbare tilnærminger som forenkler videre håndtering og prosessering av store grafer.

There is a growing interest in research and analysis of large scale graphs such as online social networks, the Web graphs, disease tracking in global populations. These graphs can grow to a scale of billions of vertices and trillions of edges. Handling and effectively processing graphs on this scale can be very challenging and expensive. There exist several ways to create approximations of graphs to ease these challenges. The act of creating these approximations can be challenging in itself on this scale, as typical single-computer solutions do not scale to the size of these graphs. We implement and perform several tests with the approximation techniques vertex contraction, spanner creation, and hopset creation. We have done this using the distributed graph processing framework Pregel and Spark. We had success implementing and running our implementations in a distributed cluster setting, on several different types of real-life, large scale graphs, successfully creating approximations of the original graphs.