Resources

Syllabus

Lecture I. 

Introduction to the course. Network gallery. Basic definitions: networks (undirected, directed, unweighted, weighted), link density, subnetworks, degree, strength. Network representations: adjacency lists, edge lists. Network visualization.

Hands-on session I.

Topics covered in Lecture I. 

Lecture II. 

Paths: definitions. Birth of graph theory: the puzzle of the Königsberg bridges. Shortest paths: distance, average path length, and diameter. Connectedness and components. Social distance. Small worlds: Milgram’s experiment. Friend of a friend: the clustering coefficient. Assortativity. Centrality measures: degree, betweenness. Centrality distributions. Friendship paradox.

Hands-on session II.

Topics covered in Lecture II. 

Lecture III. 

Network models. The random network of Erdős and Rényi. The configuration model. Preferential attachment: the Barabási-Albert model. Extensions of the Barabási-Albert model: the random walk model. Dynamics on networks. Information diffusion: threshold models.

Hands-on session III.

Topics covered in Lecture III. 

Lecture IV. 

Information diffusion: independent cascade models. Epidemic spreading. Contact networks. The SIS and SIR models. Rumor spreading. Opinion dynamics with discrete opinions: the majority model and the voter model. Opinion dynamics with continuous opinions: the bounded confidence model. Co-evolution of networks and dynamics.

Hands-on session IV.

Topics covered in Lecture IV. 


Sample Project Pitches


Analysis of real networks. 

Choose a network you like from the repositories we have indicated in the Dropbox folder. Run a basic analysis of the network, calculating:


If you wish, you can randomize the network using the configuration model, run the same analysis on the randomized network, and compare the results. How random is the network? Are there features that depend only on the degree sequence, i.e., that are approximately the same in the randomized network? Which ones?


Network models I: Emergence of the giant component of random networks. 

Build Gilbert random networks with 1000 nodes and 25 equally-spaced values of the link probability, in the interval [0; 0.005] (0, 0.0002, 0.0004, 0.0006, …, 0.0048, 0.005). For each value of the link probability generate 20 different networks, compute the relative size of the giant component (number of nodes in the largest component divided by the total number of nodes) and report the average and the standard deviation in the plot. Comment on the results.


Network models II: The random walk model. 

Write the code of the random walk model. Build networks with 1000 nodes and different values of the probability p: 0, 0.2, 0.5, 0.7, 1 (you can choose the values of m0 and m, or set them to 4 and 3, respectively). Compare the networks with a Barabási-Albert network with the same number of nodes and average degree m. Highlight similarities and differences. 


Network dynamics I: Simulation of COVID-19-like disease spreading and containment. 

Upload the contact network of school children on Google Colab (use the `nx.read_gexf()` function to read the file). 

Run an SIR epidemic dynamic on it (the initial number of infected people could be fixed or a percentage of the total population, e.g., 1%). Use values of the reproduction number R0 both above and below the epidemic threshold. Plot the proportion of infected nodes as a function of time for all networks and all R0 values. Next, assume that a random fraction f of nodes is vaccinated and cannot contract the disease. Rerun the dynamic in this new scenario, for different values of f (0.1, 0.3, 0.5, 0.9) for R0 values larger than the epidemic threshold. Check what happens if, instead of random vaccination, you immunize the fraction f of nodes with the highest degree. Discuss the results. Finally, assign to each node a number t between 0 and 1, indicating the fraction of time that the node is out and can get the disease. Consider two cases: lockdown (t is randomly selected in the interval [0,0.1]), and standard (r is randomly selected in the interval [0, 1]). Rerun the dynamics in these scenarios. Here, when you check whether a node i will get the disease or not, you must first verify that they are exposed. For this, generate a random number r and check whether it is larger or smaller than the value ti of node i. If r < ti, the node is exposed, and you can proceed as usual. Otherwise, the node cannot get the disease during that iteration of the process. Again, rerun the dynamic in this scenario for all values of the parameters and discuss the results. Is vaccination more effective than lockdown? For which fractions of immunized individuals f? If you feel ambitious and have some extra time, try to play with the ingredients above and possibly add new (realistic) ones.


Network dynamics II: Influence maximization. 

Consider the independent cascade model, with influence probability p = 0.0524, and the network of friendships of Spanish high school students. Upload the network to Google Colab and use the nx.read_gexf()` function to read the network.


In the initial configuration a set of 1% of the nodes are spreaders, the others are susceptible. Choose the initial set of spreaders in the following ways:


Run the dynamic 10 times in each case and average the fraction of influenced nodes at the end of the process. Which initial set leads to the largest fraction of influenced nodes?

Network dynamics III: Opinion dynamics.

Generate a (Gilbert) random network with 1000 nodes and link probability p=0.01. Assign binary opinions randomly to the nodes (so that about half of them have opinion 0 and the other half opinion 1). Run a hybrid opinion dynamic, that combines the majority model and the voter model, as follows: the focal node takes the majority opinion of its neighbors, with a probability q, and the opinion of a randomly chosen neighbor, with probability 1-q. Try different q-values: q=0, 0.1, 0.2, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0. For each q-value do 10 runs of the dynamic (always starting from an initial configuration with randomly distributed opinions) and compute the fraction of runs that lead to consensus (i.e. the number of consensus runs divided by 10). Plot this value as a function of q. If, given a q-value, the system always reaches consensus, compute the average number of iterations needed to converge.