Adresse und Kontakt

AG Netzbasierte Informationssysteme
FU Berlin
Königin-Luise-Straße 24-26
14195 Berlin

Tel.: +49-30-838-75221
Fax: +49-30-838-75220

This site is no longer maintained. You see a static copy as of April 1 2016.

Einsatz des MapReduce Frameworks zur nebenläufigen Berechnung von Netzwerkanalysemetriken

Webapplikationen wie Twitter, Google, Facebook und Wikipedia ermöglichen, dass riesige Datenmengen analysiert werden können, um Entitäten wie Personen, Inhalte und deren Interaktionen zu untersuchen. Zur Analyse dieser digitalen Spuren finden vor allem Prinzipien aus dem Bereich der Parallelen Programmierung Anwendung. In dieser Bachelorarbeit soll das MapReduce Software-Framework bzw. deren Open Source Implementierung Hadoop eingesetzt werden, um eine Webapplikation aufzubauen, die für die Analyse von komplexen Netzwerken genutzt werden kann.

Innerhalb der wissenschaftlichen Analyse von Datensätzen ist es notwendig, eine bestehende, häufig komplexe Fragestellung in Teilanalyseschritte zu zerlegen. Gerade bei großen Netzwerken kann die Berechnung von Metriken viel Zeit in Anspruch nehmen, daher soll in dieser Bachelorarbeit, der Nutzer bei der Analyse von großen Netzwerken unterstützt werden. Durch den Aufbau einer Webapplikation soll der analytische Prozess in Teilschritte zerlegt werden. Als Input sollen grundsätzlich alle Daten dienen, die in einem bestimmten Format (z.B. graphml, csv) vorliegen. (*) Mit Hilfe der Webapplikation soll eine Analyse der Daten in einzelnen, durch den Nutzer definierten Schritten möglich sein. In jedem Teilschritt soll bestimmt werden, ob und wie das Ergebnis weiterbearbeitet wird. So kann eine einzelne Berechnung bereits das finale Ergebnis darstellen oder aber als Input für einen weiteren Analyseschritt genutzt werden. Die Berechnung der einzelnen Metriken soll mit Hilfe von MapReduce erfolgen.

Es stehen derzeit zwei Anwendungsfälle zur Verfügung, anhand derer der Prototype getestet werden soll.(**) Der erste Anwendungsfall basiert auf dem Twitterdatensatz. Die in Twitter versendeten Nachrichten (tweets), können auf ihre Eigenschaften untersucht werden, wie das Vorkommen von Hashtags, Erwähnungen und Weblinks. Eine Erweiterung hin zu einer inhaltlichen Analyse der Tags ist möglich. Der zweite Anwendungsfall basiert auf dem GNOME Call Graphen. Hier sollen bestehende Komponenten (eng vernetzte Teilgraphen) und deren strukturellen Veränderungen über die Zeit untersucht werden.

Für beide Anwendungsfälle soll der vollständige Analyseprozess mit Hilfe des Prototypen in Teilschritte zerlegt werden. Den Umfang dieser Zerlegung zu bestimmen, ist Teil der Arbeit. Für die Analysen (eine eigene Implementierung der Algorithmen soll nicht erfolgen) soll der Nutzer Methoden der GNU R Packete tm und igraph auswählen können.

(*) Die Spezifikation des Datenformats erfolgt in Abhängigkeit von den Testfällen.
(**) Die Datensätze werden von der Betreuerin zur Verfügung gestellt. Eine genaue Spezifikation der Testfälle erfolgt während der Arbeit. 

Ausgewählte Literatur:

Aniket Kittur, Boris Smus, Robert E. Kraut: CrowdForge: Crowdsourcing Complex Work. Technical Report CMU-HCII-11-100, Carnegie Mellon University, 2011. (Hinweis: Interessant ist besonders die Beschreibung des Prototypen, der für die Zerlegung die analytischen Prozess als Vorbild dienen kann)

danah boyd, Kate Crawford: Six Provocations for Big Data. Paper to be presented at Oxford Internet Institute’s “A Decade in Internet Time: Symposium on the Dynamics of the Internet and Society” on September 21, 2011. (Hinweis: Interessanter Artikel zum Thema “Big Data” und dem Problem, diesen Begriff zu nutzen und warum die Interpretation der Analyseergebnisse manchmal schwierig ist)

J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters. In OSDI, pages 137–150, 2004.

Ralf Lämmel. 2007. Google’s MapReduce programming model; Revisited. Sci. Comput. Program. 68, 3 (October 2007), 208-237. DOI=10.1016/j.scico.2007.07.001

Hung-chih Yang, Ali Dasdan, Ruey-Lung Hsiao, and D. Stott Parker. 2007. Map-reduce-merge: simplified relational data processing on large clusters. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data (SIGMOD ’07). ACM, New York, NY, USA, 1029-1040. DOI=10.1145/1247480.1247602

Webseiten

Art der Arbeit: Bachelorarbeit

Voraussetzungen:  Kenntnisse im Bereich Webtechnologien und in der Java Programmierung sind Bedingung sowie im Bereich Netzwerkanalyse wünschenswert

Betreuerin: Prof. Claudia Müller-Birn

Bei Interesse, weiteren Fragen oder zwecks Vereinbarung eines Sprechstundentermins bitte senden Sie eine E-Mail an Prof. Claudia Müller-Birn.

AG Netzbasierte Informationssysteme, http://www.ag-nbi.de
Königin-Luise-Straße 24-26, 14195 Berlin, Tel.: +49-30-838-75221, Fax: +49-30-838-75220