PHYS 5116: Complex Networks | Fall 2019

**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.

**Course organization**

*Lectures:* Lectures will be given jointly by Prof. Barabási, by Drs. Towlson, Ruf, Danziger, and Shekhtman.

*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.

Lectures

14

Nov

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 2HomeworkHomework26

Nov

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 slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework04

Sep

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 2HomeworkHomework06

Sep

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 2HomeworkHomework09

Sep

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 2HomeworkHomework11

Sep

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 2HomeworkHomework18

Sep

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 2HomeworkHomework25

Sep

Use your own-laptop during this class. We will first cover theory about networks & computers, followed by hands-on analysis using Python and NetworkX.

View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework30

Sep

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.

View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework02

Oct

Use your own-laptop during this class. Shortest-paths, diameter, connectedness, and components.

View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework07

Oct

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 2HomeworkHomework09

Oct

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 2HomeworkHomework16

Oct

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 2HomeworkHomework18

Oct

21

Oct

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 slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework23

Oct

We will implement calculation of null-models and discuss issues related to github

View slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework30

Oct

24

Oct

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 slidesView slidesHandoutHandoutHandout 2Handout 2HomeworkHomework