Complex Networks

You are here

Credits
5
Types
Elective
Requirements
This subject has not requirements, but it has got previous capacities
Department
URV
Mail
Complex networks are everywhere in the world around us: communication networks, transportation networks, networks of friends and acquaintances, and biological networks, to name a few. In this course, students will learn the similarities and mathematical abstractions that lie beneath these examples. Other examples drawn from molecular biology (gene regulation and protein interaction networks), economics (trade networks, relationships between companies and the strategic interactions on networks), computer networks (Internet, world wide web), and ecology (food webs). In the last decade there has been an explosion of work in the theory and applications of networks to a vast range of problems. Students who complete this course will receive a broad introduction to recent work in this area, understand the strengths and weaknesses of modeling the network, and may apply networks and their analysis in a variety of configurations.

In the first part of the course we focus on the empirical description of the network structure. Then, we turn our attention to the dynamics of networks: how networks are formed and grow, and how these rules of growth are related to the overall structure. Finally, we consider algorithms and dynamics on top of networks. In the latter part of the course we will present issues related to the spread of diseases and viruses in the network, how to detect the community structure in networks, and for example, how it works the Google PageRank algorithm.

Teachers

Person in charge

  • Sergio Gómez Jiménez ( )

Others

  • Alexandre Arenas ( )

Weekly hours

Theory
2
Problems
0
Laboratory
0.5
Guided learning
0.5
Autonomous learning
5.33

Competences

Generic Technical Competences

Generic

  • CG3 - Capacity for modeling, calculation, simulation, development and implementation in technology and company engineering centers, particularly in research, development and innovation in all areas related to Artificial Intelligence.

Technical Competences of each Specialization

Academic

  • CEA11 - Capability to understand the advanced techniques of Computational Intelligence, and to know how to design, implement and apply these techniques in the development of intelligent applications, services or systems.

Professional

  • CEP2 - Capability to solve the decision making problems from different organizations, integrating intelligent tools.

Transversal Competences

Information literacy

  • CT4 - Capacity for managing the acquisition, the structuring, analysis and visualization of data and information in the field of specialisation, and for critically assessing the results of this management.

Reasoning

  • CT6 - Capability to evaluate and analyze on a reasoned and critical way about situations, projects, proposals, reports and scientific-technical surveys. Capability to argue the reasons that explain or justify such situations, proposals, etc..

Analisis y sintesis

  • CT7 - Capability to analyze and solve complex technical problems.

Basic

  • CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.

Objectives

  1. Detection of systems which may be represented using complex networks
    Related competences: CG3, CEP2, CB6,
  2. To know how to study and characterize the structure of complex networks
    Related competences: CT4, CT7, CEA11,
  3. To know models of complex networks and their implementation
    Related competences: CT7, CB6,
  4. To know the main dynamics on top of complex networks
    Related competences: CT4, CT7,
  5. To know how to perform and validate Monte Carlo simulations
    Related competences: CT7,
  6. To know how to apply the knowledge in complex networks to extract information of systems which can be described using this framework
    Related competences: CT4, CT6, CEA11, CEP2,

Contents

  1. Introduction
    Examples of complex networks in many knowledge fields. Complex network types.
  2. Structure of complex network
    Main topological and structural characteristics of complex networks: degree distribution, small-world, transitivity, assortativity, community structure, centrality. Community detection algorithms.
  3. Complex network models
    Erdös-Renyi random networks, Barabasi-Albert model, Watts-Strogatz model, configuration model.
  4. Dynamics on complex networks
    Most important dynamics on complex networks: epidemic spreading, synchronization, diffusion, evolutionary games, percolation. Monte Carlo simulations. Phase transitions.

Activities

Activity Evaluation act


Introduction

Introduction
Contents:
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Structure of complex network

Development of the topic
Contents:
Theory
12h
Problems
0h
Laboratory
2.5h
Guided learning
2h
Autonomous learning
10h

Complex network models

Development of the topic
Contents:
Theory
6h
Problems
0h
Laboratory
2h
Guided learning
2h
Autonomous learning
20h

Dynamics on complex networks

Development of the topic
Contents:
Theory
10h
Problems
0h
Laboratory
2h
Guided learning
2h
Autonomous learning
10h

Theory
0h
Problems
0h
Laboratory
1h
Guided learning
1h
Autonomous learning
40h

Delivery of practical exercises about structure of complex networks

Delivery of practical exercises about structure of complex networks
Week: 4
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Delivery of practical exercises about complex networks models

Delivery of practical exercises about complex networks models
Week: 8
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Delivery of practical exercises about community detection

Delivery of practical exercises about community detection
Week: 11
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Delivery of practical exercises about simulation of dynamics

Delivery of practical exercises about simulation of dynamics
Week: 15
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Interview of the project

Interview of the project
Week: 18
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
0h

Teaching methodology

Master classes, practice with computers, resolution of practical exercises

Evaluation methodology

Resolution of practical exercises
Development of a complex networks project

Bibliography

Basic:

Web links

Previous capacities

Prior skills on Algorithmics and Programming:
- Abstract data types and computational cost
- Graphs, trees and algorithms