# Winter Semester 2014-2015

## Complex Networks: Structural Aspects and Algorithms

### Content

Complex networks are typically large real-world graphs that are used to model objects in the physical, biological and social sciences. Examples include social networks such as Facebook or LinkedIn, co-authorship networks such as DBLP, infrastucture networks such as the World Wide Web and various telephone/power grid networks, biological networks that model metabolic or signaling pathways.

Complex networks are hard to classify into any one graph class. What is known
is that many complex networks share some core properties. Chief among them
is the * small-worlds * property, which asserts that the typical distances
between a pair of nodes in the network is small compared to the size of the
network. Another striking property is that many networks are * scale-free *
in the sense that the empirical degree distribution of the nodes is
independent of the size of the graph and is often governed by a power law.

In this seminar course, we wish to survey several aspects of complex networks. We plan to do this in four modules. We plan to start with empirical studies of several complex networks. This should hopefully give us a sense of what it is that we are dealing with. We will then move on to a mathematical study of the large-scale structure of networks. This would be followed by algorithmic problems and design techniques that are suitable for large networks. Finally, we will also study random graph models of complex networks.

### Prerequisites

This is a seminar for Masters students. We expect participants to have some background in algorithms and discrete mathematics (including graph theory and linear algebra).- Each participants will be assigned a topic which they have to present during the seminar. As a part of this, particpants might have to verify experimental claims by running tests on benchmarks.
- Participants have to present a summary of their study in a report. Use this file.