PHYS 5116: Complex Networks | Fall 2018

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

Lectures

06

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 slidesHandoutHandoutHomework 211

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 slidesHandoutHandoutHomework 213

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 slidesHandoutHandoutHomework 218

Sep

20

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 slidesHandoutHandoutHomework 225

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 slidesHandoutHandoutHomework 202

Oct

Use your own-laptop during this class. We work with Cytoscpae, analyzing a social network, using many of the measures and the concepts introduced in the previous classes.

View slidesHandoutHandoutHomework 204

Oct

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 slidesHandoutHandoutHomework 211

Oct

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

View slidesHandoutHandoutHomework 213

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 slidesHandoutHandoutHomework 216

Oct

18

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 slidesHandoutHandoutHomework 223

Oct

25

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 slidesHandoutHandoutHomework 227

Oct

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.

View slidesHandoutHandoutHomework 230

Oct

01

Nov

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 206

Nov

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 213

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 slidesHandoutHandoutHomework 215

Nov

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.

View slidesHandoutHandoutHomework 220

Nov

The many networks that surround us do not exist in isolation, but often depend on one another. A classic example being the power grid, which depends on computerized control systems to operate, which in turn depend on power. In this lecture we will explore how some of the concepts and phenomena we are familiar with change in the presence of such multilayer networks.

View slidesHandoutHandoutHomework 227

Nov

29

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