Handouts

0 - The Network Science Course

• Slides:
  • Information about the course

1 - Fundamentals of Network Science

• Videos:
  • Motivation and the "small world" phenomenon [23m36s]
  • Emergence of Network Science [36m33s]
  • Brief Introduction to Graph Theory and Network Vocabulary [35m33s]
• Slides:
  • An introduction to Network Science
• Other Material:
  • Network Science - Chapter 1: Introduction (A. Barabasi)
  • Network Science - Chapter 2: Graph Theory (A. Barabasi)
  • Networks, Crowds and Markets - Chapter 1: Overview (D. Easley and J. Kleinberg)
  • Networks, Crowds and Markets - Chapter 2: Graphs (D. Easley and J. Kleinberg)
  • The "new" science of networks (D. Watts)

Chapter 2 - Measuring Networks and Random Graph Models

• Videos:
  • Measuring Graphs and Results on Real Networks [54m27s]
  • Erdös-Renyi Random Graph Model [56m39s]
  • Motivation and the "small world" phenomenon [29m11s]
  • Power Laws and Preferential Attachment [1h35m09s]
• Slides:
  • Measuring Networks and Random Graph Models
• Other Material:
  • Network Science - Chapter 3: Random Networks (A. Barabasi)
  • Network Science - Chapter 4: The Scale-Free Property (A. Barabasi)
  • Network Science - Chapter 5: The Barabasi-Albert Model (A. Barabasi)
  • Networks, Crowds and Markets - Chapter 18: Power Laws and Rich-Get-Richer Phenomena (D. Easley and J. Kleinberg)
  • Networks, Crowds and Markets - Chapter 20: The Small-World Phenomenon (D. Easley and J. Kleinberg)
  • NetLogo Visualizations:
    • ErdosRenyiDegDist.nlogo
    • GiantComponent.nlogo
    • SmallWorldWS.nlogo
    • RAndPrefAttachment.nlogo
  • Some papers mentioned in lectures:
    • Leskovec, J., & Horvitz, E. (2008, April). Planetary-scale views on a large instant-messaging network. In Proceedings of the 17th international conference on World Wide Web (pp. 915-924).
    • Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1), 17-60.
    • Travers, J., & Milgram, S. (1969). An experimental study of the small world problem. Sociometry, 32(4), 452-443.
    • Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’networks. Nature, 393(6684), 440-442.
    • Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512.
    • Clauset, A., Shalizi, C. R., & Newman, M. E. (2009). Power-law distributions in empirical data. SIAM review, 51(4), 661-703.

3 - Centrality

• Videos:
  • Node Centrality [1h10m49s]
• Slides:
  • Node Centrality
• Other Material:
  • Centrality Measures and Link Analysis (G. Mateos)
  • Wikipedia: Centrality

4 - Link Analysis

• Videos:
  • Link Analysis and PageRank [1h44m03s]
• Slides:
  • Link Analysis: PageRank
• Other Material:
  • Centrality Measures and Link Analysis (G. Mateos)
  • Wikipedia: HITS algorithm
  • Wikipedia: PageRank
  • NetLogo Visualizations:
    • PageRank.nlogo
  • Some papers mentioned in lectures:
    • Broder, A., Kumar, R., ... & Wiener, J. (2000). Graph structure in the web. Computer networks, 33(1-6), 309-320.
    • Kleinberg, J. M. (1999). Authoritative sources in a hyperlinked environment. Journal of the ACM (JACM), 46(5), 604-632.
    • Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab.

5 - Graph Visualization and Exploration with Gephi

• Videos:
  • Gephi Tutorial [41m11s]
• Other Material:
  •   Gephi – Free and Open-Source Network Analysis Platform (main webpage for download)
  • Gephi – Introduction to Network Analysis and Visualization (tutorial by M. Grandjean)
  • Some datasets:
    • KONECT - The Koblenz Network Collection
    • Network Repository
    • Stanford Large Network Dataset Collection
    • Mark Newman Network Data
    • Pajek Datasets
    • Movie Galaxies (Harvard Dataverse)
    • The Colorado Index of Complex Networks (ICON)
    • Gephi Datasets

6 - Roles and Community Structure in Networks

• Videos:
  • Roles and Community Structure in Networks [1h37m39ss]
• Slides:
  • Community Structure in Networks (selected slides from J. Leskovec and G. Mateos)
• Other Material:
  • Network Science - Chapter 9: Communities (A. Barabasi)
  • Networks, Crowds and Markets - Chapter 3: Strong and Weak Ties (D. Easley and J. Kleinberg)
  • Some papers mentioned in lectures:
    • Henderson et al (2012). Rolx: structural role extraction & mining in large graphs. Proceedings of the 18th ACM SIGKDD international conference on Knowledge Discovery and Data Mining (pp. 1231-1239).
    • Fortunato, S. (2010). Community detection in graphs. Physics reports, 486(3-5), 75-174.
    • Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics reports, 659, 1-44.
    • Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008(10), P10008. [Louvain Algorithm]

7 - Creating, manipulating and analyzing networks with NetworkX

• Some example code: jupyter notebook | html
• NetworkX

8 - Subgraph Patterms

• Videos:
  • Subgraphs as Fundamental Ingredients of Complex Networks [2h11m21s]
• Slides:
  • Subgraphs as Fundamental Ingredients of Complex Networks
• Other Material:
  • gtrieScanner (P. Ribeiro)
  • Some articles to read:
  • Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: simple building blocks of complex networks. Science, 298(5594), 824-827.
  • Milo, R., Itzkovitz, S., Kashtan, N., Levitt, R., Shen-Orr, S., Ayzenshtat, I., ... & Alon, U. (2004). Superfamilies of evolved and designed networks. Science, 303(5663), 1538-1542.
  • Pržulj, N. (2007). Biological network comparison using graphlet degree distribution. Bioinformatics, 23(2), e177-e183.
  • Ribeiro, P., & Silva, F. (2014). G-tries: a data structure for storing and finding subgraphs. Data Mining and Knowledge Discovery, 28(2), 337-377. [pre-print version]
  • Ribeiro, P., Paredes, P., Silva, M. E., Aparicio, D., & Silva, F. (2021). A Survey on Subgraph Counting: Concepts, Algorithms, and Applications to Network Motifs and Graphlets. ACM Computing Surveys (CSUR), 54(2), 1-36.

9 - Diffusion and Cascading Behavior

• Videos:
  • Diffusion and Cascading Behavior - Part 1 (Decision Based Models) [58m59s]
  • Diffusion and Cascading Behavior - Part 2 (Probabilistic Models) [1h29m38s]
• Slides:
  • Diffusion and Cascading Behavior - Part 1 (Decision Based Models) (selected slides from J. Leskovec)
  • Diffusion and Cascading Behavior - Part 2 (Probabilistic Models) (selected slides from J. Leskovec)
• Other Material:
  • Reproductive Number
    • Basic Reproductive Number (Wikipedia)
    • Liu, Y., Gayle, A. A., Wilder-Smith, A., & Rocklöv, J. (2020). The reproductive number of COVID-19 is higher compared to SARS coronavirus. Journal of travel medicine.
  • Epidemic Models
    • Compartmental Models in Epidemiology (Wikipedia)
    • The Mathematics of Epidemicsl (Alan Zucconi)
    • Epidemix - Visually Explore Disease Transmission (University of London)
    • Epidemic Calculator for COVID-19
    • What Happens Next? COVID-19: Futures, Explained With Playable Simulations (M. Salathé, epidemiologist & N. Case, art/code)
    • Gomes, M. F., y Piontti, A. P., Rossi, L., Chao, D., Longini, I., Halloran, M. E., & Vespignani, A. (2014). Assessing the international spreading risk associated with the 2014 West African Ebola outbreak. PLoS currents, 6.
    • Althaus, C. L. (2014). Estimating the reproduction number of Ebola virus (EBOV) during the 2014 outbreak in West Africa. PLoS currents, 6.
  • Data and general resources for COVID-19
    • The Coronavirus Tech Handbook
    • COVID-19 Data Repository (Johns Hopkins University) [includes times series for all countries]
    • Dados relativos à pandemia COVID-19 em Portugal (Data Science for Social Good Portugal)

10 - Network Construction

• Videos:
  • Network Construction [1h34m41s]
• Slides:
  • Network Construction (selected slides from J. Leskovec and L. Lacasa)

11 - Link Prediction

• Slides:
  • Link Prediction: an introduction
• Other Material:
  • Some example code: jupyter notebook | html
  • Some papers mentioned in lectures:
    • Martínez, V., Berzal, F., & Cubero, J. C. (2016). A survey of link prediction in complex networks. ACM computing surveys (CSUR), 49(4), 1-33.
    • Kumar, A., Singh, S. S., Singh, K., & Biswas, B. (2020). Link prediction techniques, applications, and performance: A survey. Physica A: Statistical Mechanics and its Applications, 553, 124289.
    • Daud, N. N., Ab Hamid, S. H., Saadoon, M., Sahran, F., & Anuar, N. B. (2020). Applications of link prediction in social networks: A review. Journal of Network and Computer Applications, 166, 102716.
    • Araujo, M., Ribeiro, P, & Faloutsos, C. (2017). Tensorcast: Forecasting with context using coupled tensors (best paper award). In 2017 IEEE International Conference on Data Mining (ICDM) (pp. 71-80). IEEE.

Other topics

• Graph Neural Networks:
  • Graph Representation Learning Book (William L. Hamilton, McGill University)
  • CS224W - Machine Learning with Graphs (Jure Leskovec, Stanford University) | [Video Lectures]
  • Wu, Z. et al. (2020). A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1), 4-24.
  • Zhou, J. et al. (2020). Graph neural networks: A review of methods and applications. AI Open, 1, 57-81.
• Graph Databases:
  • Graph Databases Book (Ian Robinson, Jim Webber and Emil Eifrem, O'Reilly)
  • Besta, M. et al. (2019). Demystifying graph databases: Analysis and taxonomy of data organization, system designs, and graph queries. arXiv preprint arXiv:1910.09017.
  • Arenas, M., Gutierrez, C., & Sequeda, J. F. (2021, June). Querying in the Age of Graph Databases and Knowledge Graphs. In Proceedings of the 2021 International Conference on Management of Data (pp. 2821-2828). [tutorial slides]

Last update: