Anmeldung:

Bitte melden Sie sich am Studierendenportal für diese Veranstaltung an (Prüfungsnummer 357).
 

Course Materials:

Introductory slides (17.04.2015)

Template and Ipe tutorial slides (24.04.2015) [+ template files for the write-up and Ipe]

Description:

In the last two decades, large complex networks have become ubiquitous, and as a result the need to analyze them is increasing at a fast rate. Such data was previously limited to only a few industries (i.e., transportation and communication), but with the explosive growth of the Web, social networks, and biological networks, we have open access to more data than ever before. There are clear monetary benefits to analyzing such data, as can be seen by the sheer number of big data startups. However, analyzing such networks is not just about earning advertising dollars, or giving useful product suggestions; we can better understand our behavior, understand the world around us, and build systems that allow us to communicate and solve problems like never before.

In this seminar, we will discuss state-of-the-art theoretical and practical algorithms for analyzing large networks. Though our main focus is on social networks, many of the methods extend to other large sparse graphs such as transportation networks, biological networks, and the Web graph. Topics include, but are not limited to: computing graph metrics (centrality measures, diameter), computing graph features (cliques, induced subgraphs), combinatorial optimization algorithms (vertex coloring and graph clustering), dynamic algorithms, algorithms in the external memory model and MapReduce frameworks, and general techniques for coping with massive graphs. In addition to assessing the quality of an algorithm in terms of its running time and space requirements, it is also our intention to understand the proposed application, and to critique the methodology through the lens of network science.

Details:

On the first day of the seminar, we will present a collection of recent articles from algorithms literature and match each student with an article. Under the guidance of a supervisor, each student will write up a thorough analysis of their article, and give a presentation to share the techniques, results, and applications of the research.