Network Structure, Modeling, and Properties for Complex Systems

Pre­requisites: No requirement. Basic knowledge on Graph Theory, Probability Theory, Linear Algebra, and Python will be helpful.

Grading Policy:

Exam 28%: in-class exam at the beginning of lectures 2, 3, 4, 5;

Homework 40%: assigned after lectures 1, 2, 3, 4 and due by the end of the next lecture;

Project report 32%: 

Each student find and collect a network he/she is interested of, or download a network from http://networksciencebook.com/translations/en/resources/data.html or https://snap.stanford.edu/data/ for study.  Student should use the network knowledge learned from the class but not limited to perform analysis and conduct some conclusion. The analysis and result will be presented to the class in the last lab session, and the project report is due midnight of the day after the last lecture (before 11:59pm Saturday). A report should consists of (but not limited to) following sections: title, author, abstract, introduction, problem/model, method, result, analysis and conclusion. Discussion is encouraged but project and report is individual contribution and should not be shared.

Background and Objectives:

It is often the case that complex systems, both living and man-made, can be represented as static or dynamic networks of many interacting components. These components are typically much simpler in terms of behavior or function than the overall system, implying that the additional complexity of the latter is an emergent network property. Network science is a relatively new discipline that investigates the topology, structural properties, evolution dynamics, and vulnerabilities of such complex networks, aiming to better understand the variant and invariant properties, such as patterns of connection, interaction, and relationships, of the underlying systems. The applications of network science span a wide variety of areas that pervade our lives: Internet, neuroscience, power grid, physical, biological, ecology, and social systems. This course will focus on essential concepts and core ideas of network literacy and basic tools to analyze and visualize them. After the course students should be able to:

•         Explain basic metrics and measures used to characterize networks

•         Analyze a network using the various measures and a suitable network analysis software tool

•         Discuss the strengths and weaknesses of random graph models

•         Understand and apply algorithms for node ranking, community detection, and network comparison

•         Understand and explain the interdisciplinary nature of the area of network science

Software and Tools:

1.       Python: https://www.python.org/downloads/

2.       NetworkX: https://networkx.org/documentation/stable/reference/index.html

3.       igraph: https://igraph.org/python/

4.       RolX: https://github.com/benedekrozemberczki/RolX

5.       BCTPy: https://pypi.org/project/bctpy

6.       Graphviz: https://pypi.org/project/graphviz/

Books:

1.       A. Barabasi, Network Science http://networksciencebook.com/

2.       M.E.J. Newman, Networks: An Introduction, Oxford University Press, 2010. 

3.       D. Easley and J. Kleinberg, Networks, Crowds and Markets, Cambridge Univ Press, 2010. https://www.cs.cornell.edu/home/kleinber/networks-book/

Schedule:

Lecture 1: 

(a) Course Introduction

We first cover course specifics and logistics. We then introduce the notion of network and present a general notion of Network Science as a cross-disciplinary field. We will motivate this via several examples and highlight the associated challenges.

(b) Introduction to Graph Theory

We will cover basic notions and definitions related to undirected and directed graphs: vertices, edges, simple graphs, weighted graphs, neighborhoods, degree, path, cycle, connected components, random walks, directed acyclic graphs, bipartite graphs, max-flow/min-cut, etc. Also, we introduce concepts from algebraic and spectral graph theory, such as adjacency, incidence, and Laplacian matrices.

(c) Lab: Python introduction and installation; Network creation and visualization with adjacency, incidence, and Laplacian matrices.

(d) <lecture1>  <lecture2>  <lab1> <homework1>

Lecture 2:        

(a) Introduction to Graph Theory (continue)

(b) Random Networks and Their Properties

• Network properties: degree distribution, clustering coefficients, path length, diameter, connectivity

• Erdos-Renyi random graph model

(b) Lab: Compute network properties of a given network; Generate and visualize Erdos-Renyi Random networks and review their properties

(c) <lecture2>  <lecture3>  <lab2> <homework2> (solutions only published on moodle)

Lecture 3:        

(a) Random Networks and Their Properties

• Properties of random networks

• Properties of real networks

• The Small-World Phenomenon

• Watts-Strogatz (small-world) model

(b) Lab: Generate and visualize small-world networks, Kronecker networks, and scale-free networks, and review their properties

(c) <lecture3>  <lecture4>  <lab3> <homework3>

Lecture 4:        

(a) Scale-free networks

(b) Degree Correlations: Assortative vs disassortative networks

(c) BA Model and Preferential Attachment

(d) Lab: Compute and compare centrality measures of previously generated networks and real network examples

(e) <lecture4>  <lecture4-1> <lab4-5> <homework4> <hw4-network>

Lecture 5:        

(a)  Centrality and Network-core Metrics

We introduce the notion of node centrality to measure the importance of a node within the network. We compare classical measures such as degree, closeness, betweenness, eigenvector, and Katz centrality. We then continue with the following centrality metrics:

• Link-based centrality metrics

• Path-based centrality metrics

• k-core decomposition

• Core-periphery structure

• Rich-club set of nodes

(b) Network Structures: Subnetwork, motifs, and graphlets

(c) Lab:  Project presentation 

(d) <lecture5> <lecture5-1>