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 by Prof. Barabási, by Drs. Towlson and Cornelius
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.
Examinations: The final exam will be a complete study of a real network, from data collection to network analysis. In place of a midterm exam, there will be an intermediate presentation to check your progress on this project 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 slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
Errors and failures can corrupt all human designs: The failure of a component in your car’s engine may force you to call for a tow truck or a wiring error in your computer chip can make your computer useless. Many natural and social systems have, however, a remarkable ability to sustain their basic functions even when some of their components fail. Networks play a key role in the robustness of biological, social and technological systems. The purpose of these classes is to understand the role networks play in ensuring the robustness of a complex system.View slidesHandoutHandoutHomework 2
In network science by community we mean a group of nodes that have a higher affinity to connect to each other than to nodes from other communities. We explore communities in different kinds of networks, as well as methods and algorithms to detect them.View slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
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 slidesHandoutHandoutHomework 2
From biological to computer viruses, from ideas to products, diverse agents spread on different types of networks, from social to computer network and professional networks; they follow widely different time scales and mechanisms of transmission. Despite this diversity, spreading processes follow common patterns and can be described using the same network-based theoretical and modeling framework. In these classes we introduce the quantitative framework that helps us understand and model these spreading phenomena.View slidesHandoutHandoutHomework 2