Course description and objectives
The course is an interdisciplinary introduction to the emerging science of complex networks and their applications. Topics to be covered include the mathematics of networks (graph theory), data analysis, and applications to biology, sociology, technology, and other fields. Students will learn about the ongoing research in the field, and ultimately apply their knowledge to conduct their own analysis of a real network data set of their choosing as part of the final project.
Lectures: Lectures will be given jointly by Prof. Barabási, by Dr. Shekhtman, and Mr. McCabe.
Homework: There will be three (3) homework assignments representing a mix of mathematical work and computational data analysis. Students are expected to turn in their source code for the computational exercises. Students in the Network Science Ph.D. program will typically be asked to do at least one, more challenging, problem on top of each assignment.
Examinations: Final project presentation — complete analysis of a real network. In place of a midterm exam, there will be an intermediate presentation to check your progress and provide feedback.
We are surrounded by systems that are hopelessly complex, from the society, a collection of seven billion individuals, to communications systems, integrating billions of devices, from computers to cell phones. Our very existence is rooted in the ability of thousands of genes to work together in a seamless fashion; our thoughts, reasoning, and our ability to comprehend the world surrounding us is hidden in the coherent activity of billions of neurons in our brain.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
Networks and graphs: In its simplest form, a network is a set of nodes connected by links. A graph, however, is a set of vertices connected by edges? Do you sense the difference? Well, regarding the common usage of these terms, there is none: graph and networks these days are used interchangeably, and so do terms of nodes and vertices and links and edges.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
The first basic question we need to answer is the following: if you are given a network, how do you think of it? How do you model it? How do you describe them analytically? This is a particularly difficult question, particularly given the diversity of the networks we are facing in this discipline. Most important, it is difficult to understand how the position of the links are decided in a given networks—each network may have a different role for that.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
Many real world networks have a similar architecture: WWW, Internet (routers and domains), electronic circuits, computer software, movie actors, coauthorship networks, sexual web, instant messaging, email web, citations, phone calls, metabolic, protein interaction, protein domains, brain function web, linguistic networks, comic book characters, international trade, bank system, encryption trust net, energy landscapes, earthquakes, astrophysical network…View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
How do we quantify how “important” a node is in a network? This depends on how we define importance, and can be a purely local measure or incorporate the node's place in the network. We discuss the most commonly used centrality metrics and the information they capture. Many real networks have links which carry weights of varying definition. We examine some examples of such networks and adapt our metrics and analyses to incorporate the edge weights.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
The structure of a network should reflect the function of the complex system it represents. An important task is to identify units which are topologically closely related - they are expected to play a functional role. We define the network motif, a small subgraph in a network, and learn how to statistically quantify the frequency of such motifs in real world networks. Through several empirical examples, we see how such motifs can provide insight into network function.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
Hubs represent the most striking difference between a random and a scale-free network. On the World Wide Web, they are websites with an exceptional number of links, like google.com or facebook.com; in the metabolic network they are molecules like ATP or ADP, energy carriers involved in an exceptional number of chemical reactions. To understand why so different systems converge to a similar architecture we need to first understand the mechanism responsible for the emergence of the scale-free property.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
The goal of these classes is to understand how the differences in the node’s ability to acquire links affect the network topology. Going beyond this competitive landscape, we also explore how other processes, like node and link deletion or the aging of nodes, phenomena frequently observed in real networks, change the way networks evolve and alter their topology. Our goal is to develop a self-consistent theory of evolving networks that can be adjusted at will to predict the dynamics and the topology of a wide range of real networks.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework
In social networks hubs tend to “date” each other. In the protein interaction network the opposite is true: The hubs avoid linking to other hubs, connecting instead to many small degree nodes. These patterns are manifestations of a general property of real networks: they exhibit a phenomena called degree correlations. We discuss how to measure degree correlations and explore their impact on the network topology.View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework