31642 - Complex Networks

Academic Year 2017/2018

  • Teaching Mode: Traditional lectures
  • Campus: Bologna
  • Corso: Second cycle degree programme (LM) in Physics (cod. 8025)

Learning outcomes

The student will acquire knowledge about the main mathematical properties characterizing a network, and he will receive an overview of the most recent and important applications of network models to real situations, in particular related to biology. Moreover, he will understand (and apply) the main algorithms for graph analysis and for implementing dynamical models embedded in networks of different topological structure.

Course contents

Introduction to complex networks: examples from physics, biology, informatics.

Definition of a network: graph. Simple and bipartite graphs. Weighted/unweighted, directed/undirected networks.

Characterization of global network topology and single-node features: single-node parameter distribution. Connectivity degree, clustering, centrality measures. Network diameter. Subnetworks: clustering, cliques and modules. Definition and calculations of the main network features. Clustering methods. Laplacian of a network.

Erdos-Renyi random networks: parameter distribution and limit theorems (N>>1). Wigner matrices and eigenvalue spectrum. Giant cluster phase transition. Relations between parameters (e.g. assortativity/mixing, connectivity degree and betweenness centrality).

Lattices: properties and examples. Generalization to small-world networks: Watts-Strogatz model.

Scale-free networks: examples. Preferential attachmenet growth rules and dynamics.

Network perturbations: attack/error tolerance, node relevance, efficiency.

Statistical mechanics of networks: definition of ensembles, constraints, network entropy.

Applications: Immune System network hierarchy, gene expression time series, metabolic networks and flux balance analysis. Examples in biological models (hierarchy, motifs).

Readings/Bibliography

Selected papers and slides.

BOOKS

- Networks: an introduction (Newman, Oxford)

- Large Scale Structure And Dynamics Of Complex Networks – vol. 2

(Caldarelli Vespignani Eds.) – World Press

- Dynamical processes on complex network

(Barrat Barthelemy Vespignani) – Cambridge press 2008

Teaching methods

The course consists of theoretical lessons, in which are explained network theory concepts and analysis methods based on it, with some practical examples on real networks. During the lessons there will be computer exercises, to see practical implementations of the algorithms studied and specific case studies.

Assessment methods

Oral exam with the discussion of homework on a selected topic. The student must be able to: - apply the network analysis methods learnt - adapt such methods to the context of the homework

Teaching tools

Software-based laboratory for network generation and analysis: Octave/Matlab (Matlab BGL toolbox/Octave network toolbox).

Network visualization and coloring based on topological features. Evaluation of network features. Giant Cluster phase transition: dynamics of network growth.

Office hours

See the website of Daniel Remondini