Course Title

Network Science

Course Code

SDS 424

Course Type

Elective

Level

Year / Semester

2^nd Semester

Instructor’s Name

Prof. Constantine Dovrolis

ECTS

5

Lectures / week

2

Laboratories / week

1

Course Purpose 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. Network Science is a new discipline that investigates the topology and dynamics of such complex networks, aiming to better understand the behavior, function and properties of the underlying systems.

The applications of Network Science include technological, informational, biological, cognitive, and social systems.

This course will provide graduate students with a solid understanding of both methods and applications of Network Science. The methods include graph theoretic concepts and metrics, algorithms for the analysis of large networks, statistical and data mining tools for inferring interesting network characteristics, mathematical techniques for understanding the dynamics of network processes, and computational methods for modeling complex network phenomena. The applications that the course covers include robustness effects in communication networks, information spreading effects in informational networks, co- evolutionary phenomena in brain networks, and epidemic processes in social networks.

Learning Outcomes

By the end of this course, students should be able to:

• Identify specific problems in their domain of expertise or discipline that can be solved in terms of network analysis and/or modeling.
• Develop simple models (computational or mathematical) that can be used to understand the behavior of complex network phenomena or systems.
• Apply existing (or develop new) graph mining algorithms to infer various structural or dynamic properties of a network (e.g., community structure, hierarchy, spreading phenomena, cascades).
• Collect, pre-process and analyze large network datasets in computationally efficient
• Become familiar with several network-related problems from a diverse set of disciplines (e.g., biology, neuroscience or sociology), enabling our students to collaborate with domain experts in cross-disciplinary applications of network science.

Prerequisites

Undergraduate-level courses in Linear Algebra, Calculus, Probability & Statistics, Algorithms.

Course Content

Week 1: What is Network Science? Relevant Concepts From Graph Theory

• What is (not) network science?
• The main premise of network science
• History and relation to graph theory, physics, sociology, and other disciplines
• Examples of networks from different application domain
• Undirected, directed, signed, weighted and spatial networks
• Paths, connected components, random walks, etc
• Directed Acyclic Graphs, Bipartite graphs, Max-flow/min-cut

Week 2: Degree Distribution and ER Graphs, Random vs. Real Graphs and "Scale Free" Networks

• Degree distribution
• Friendship paradox
• ER graphs and their degree distribution
• Giant component size in ER graphs
• Assortative vs disassortative networks
• The degree distribution of real-world networks
• Power-law degree distributions
• Preferential attachment model
• How to detect a power-law and estimate the exponent
• Configuration model and degree-preserving randomization

Week 3: Network Paths, Clustering and The “Small World” Property; Centrality and Network-core Metrics and Algorithms

• Clustering and transitivity in networks
• Diameter and characteristic path length
• Small-world networks and the Watts-Strogatz model
• Network motifs
• Link-based centrality metrics
• Path-based centrality metrics
• k-core decomposition
• Core-periphery structure
• Rich-club set of nodes

Week 4: Community Detection and Hierarchical Modularity; Advanced Topics in Community Detection

• Hierarchical clustering in network
• Modularity metric
• Algorithms for modularity maximization
• Limitations of modularity
• Hiearchical modularity
• Overlapping communities
• Dynamic communities
• Comparing community structures
• The role of nodes within and between communities
• Applications of community detection

Week 5: Network Contagion and Epidemics; Influence Phenomena On Networks

• Epidemics on networks
• Epidemic modeling (SI, SIS, SIR, etc) under homogeneous mixing
• Epidemic modeling under arbitrary degree distributions
• Basic reproductive number and superspreaders
• The linear threshold model and the Independent cascades model
• Empirical studies in information and behavior spreading
• Seeding strategies on how to maximize influence
• Cascades and community structure
• Percolation, random failures, and targeted attacks on network
• Search on networks
• Synchronization on networks
• Coevolutionary networks

Week 6: Models of Static and Dynamic Networks; Statistical Analysis of Network Data

• Stochastic network models that generate power-law degree distributions
• Optimization-based network models
• Stochastic block models
• Hierarchical Random Graphs
• Network sampling methods
• Estimation of network metrics
• Association networks
• Network tomography

Week 7: Machine Learning meets Network Science

• Node embeddings
• Graph neural networks
• Deep generative network models

Limitations and applications of graph neural networks

Teaching Methodology

Lectures, Exercises

Bibliography

• Mark Newman, “Networks: An Introduction”, Oxford University Press, 2010, ISBN-10: 0199206651, ISBN-13: 978-0199206650
• Albert-László Barabási, “Network Science”, Cambridge University Press, 2015

Assessment

Combination of coursework and exam

Language

English