Complex networks are heterogeneous data sets appearing in very different domains. Social networks revealing friendships, technical networks describing the internet topology, or biological networks modeling protein interactions constitute only a small sample of examples. Accordingly, algorithmic methods for their analysis are quickly becoming pervasive in science and technology: Node ranking by centrality is the basis for modern web search, community detection methods find application in cancer research, and tracking social influence through networks is interesting to both sociologists and advertisers. As network analysis is a relatively young field at the intersection of several disciplines, one can expect further groundbreaking insights in the future as our theoretical understanding and our computing capabilities increase.
This tutorial introduces major aspects of complex networks and their analysis. In the first part we outline several characteristics of complex networks and discuss algorithmic kernels for finding and assessing these characteristics efficiently. As just two examples, we discuss how to rank nodes according to their importance and cluster vertices into natural groups efficiently for large data sets using parallelism. To this end, we give an introduction to our tool suite NetworKit, which allows fast interactive analytic workflows.
In the second part the participants apply the concepts learned during the first part in a hands-on session with NetworKit. They learn how to solve fundamental workflows efficiently with simple Python code executed within their browser and get a glimpse on NetworKit’s C++ backend, the reason for its efficiency.
More information about NetworKit can be found on the toolkit’s website.
Jun.-Prof. Dr. Henning Meyerhenke
Henning Meyerhenke is an Assistant Professor (Juniorprofessor) at the Institute of Theoretical Informatics at Karlsruhe Institute of Technology, Germany, since October 2011. From October 2010 to September 2011 Henning was a postdoctoral researcher in Georgia Tech’s College of Computing, more precisely in the group headed by Prof. David Bader. Henning received his Diplom degree in Computer Science from Friedrich-Schiller-University Jena, Germany, in 2004 and his Ph.D. (with highest distinction) in Computer Science from the University of Paderborn, Germany, in 2008. After his graduation he was a Research Scientist at NEC Laboratories Europe in Sankt Augustin, Germany, and a Postdoctoral Researcher at the University of Paderborn until September 2010.
His main research interests are in parallel algorithm engineering for massive data sets in three main application areas: Combinatorial scientific computing (graph partitioning, load balancing, multilevel methods), network analysis (community detection, network metrics in dynamic scenarios, NetworKit library), and in algorithmic problems with connection to the life sciences (such as sequence assembly).
Recently Henning has acquired significant funding by DFG and MWK Baden-Wuerttemberg. Sponsors of smaller grants include YIN of KIT and Pittsburgh Supercomputing Center. Before his current position Henning worked on numerous other projects funded by external sponsors such as DARPA, EU, and DFG. Together with his co-authors, Henning received the Best Algorithms Paper Award at the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS’08).
Dipl.-Inform. Christian Staudt
Christian Staudt received his Diplom degree in computer science from Karlsruhe Institute of Technology (KIT) in 2012. He is currently a researcher and PhD candidate in the Parallel Computing Group, Institute of Theoretical Informatics, KIT. His research focuses on developing efficient algorithms and software for the analysis of large complex networks. Beyond that, he is interested in how network analysis methods can enable the study of complex systems in various domains. Christian maintains the open-source software NetworKit with the goal of packaging the results of algorithm engineering research and putting them into the hands of domain experts.