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: 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.
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.
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.
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…
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.
Use your own-laptop during this class. We work with Gephi, analyzing a social network, using many of the measures and the concepts introduced in the previous classes.
Use your own-laptop during this class. We will first cover theory about networks & computers, followed by hands-on analysis using Python and NetworkX.
Use your own-laptop during this class. Shortest-paths, diameter, connectedness, and components.
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.
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.
We will implement calculation of modularity and several algorithms for community detection, both agglomerative and divisive. These will be applied to a number of datasets, real and synthetic.
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.
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.
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.
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.
A lesson on the importance of using null models in your study of networks, followed by a broad overview of the new field of temporal networks.
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.