Complex Networks

Credits
5
Types
Elective
Requirements
This subject has not requirements , but it has got previous capacities
Department
URV;CS
Complex networks are everywhere in the world around us: communication networks, transportation networks, social 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. We will also 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

Others

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: CB6, CEP2, CG3,
    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: CB6, CT7,
    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-Rényi random networks, Barabási-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
    Objectives: 1
    Contents:
    Theory
    2h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Structure of complex network

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

    Complex network models

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

    Dynamics on complex networks

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

    Project

    Complex networks project
    Objectives: 1 2 3 4 5 6
    Contents:
    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
    Objectives: 2
    Week: 4
    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
    Objectives: 3
    Week: 8
    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
    Objectives: 2
    Week: 11
    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
    Objectives: 4 5
    Week: 15
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Interview of the project

    Interview of the project
    Objectives: 1 6
    Week: 18
    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