Course presentation for the 2020 edition.
Graphs are a fundamental data type that is present in a large number of applications. Networks science studies a number of graphs arising in biology, communication, transport, and many diverse areas. In particular, the analysis of social networks and activity traces brings the promise of obtaining insights that are of great importance to sociologists, psychologists, and communication scholars. There are, however, numerous algorithmic challenges on working with large graphs.
This course offers the students the possibility of learning the fundamentals of networks science and to practice by performing basic operations in small and large graphs.
Basic competences
CB3. That the students have the ability of collecting and interpreting relevant data (normally within their study area) to issue judgements which include a reflection about relevant topics of social, scientific or ethical nature.
Transversal competences
CT3. Applying with flexibility and creativity the acquired knowledge and adapting it to new contexts and situations.
Specific competences
RA.CE7.1 Knowing the fundamental statistic aspects of networks science.
At the end of the course, the students would have acquired:
- Knowledge on graph theory concepts
- Knowledge on basic centrality measures
- Knowledge on graph clustering
- Knowledge on diffusion ("viral") phenomena
- Techniques for creating graphs from non-graph data
- Techniques for visualizing and analyzing large graphs
- Techniques for detecting dense sub-graphs and performing graph clustering
- Techniques for determining the relative importance of nodes in graphs
The course requires:
- Skills in programming and data structures.
- Knowledge of basic linear algebra methods
The course will be delivered in Python, hence it is strongly recommended to have a background in Python.
- Introduction
- Why studying networks
- Basics concepts of graph theory
- Network formation models
- Random networks
- Scale-free networks
- Preferential attachment
- Other network growth models
- Structural patterns in networks
- Hubs and authorities
- PageRank
- Link-based centrality
- Network flows
- Dense sub-graphs
- Dynamic processes in networks
- Spreading phenomena
- Epidemics
The course is structured around theory classes in which the topics of the course are introduced.
In seminar and practice sessions, students can work individually or in small groups in performing network analysis tasks. At the end of each session, each student reports his/her findings individually with a 1-2 pages report.
See evaluation rules
📚 Books:
- "Network Science" (2016) by Albert-László Barabási. The first half of the course follows this book and its companion course at North Eastern University.
- "Networks, Crowds, and Markets" (2010) by Easley and Kleinberg.
- "A First Course on Networks Science" (2020) by Menczer, Fortunato, and Davis.
- "Complex Network Analysis in Python" (2018) by Dmitry Zinoviev. Also available as an e-book for UPF students.
🔗 Additional contents of the course come from:
- "AMAzING" (2003) tutorial by Frieze, Gionis, and Tsourakakis.
Other sources are listed in their respective slides.