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.