Teacher(s)
Language
English
> French-friendly
> French-friendly
Prerequisites
This course assumes the student already masters the discrete mathematical skills targeted by the course LINFO1114
The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.
The prerequisite(s) for this Teaching Unit (Unité d’enseignement – UE) for the programmes/courses that offer this Teaching Unit are specified at the end of this sheet.
Main themes
- Graphs (basic concepts, paths and connectivity)
- Applications of graphs, for example, to model social networks (links, homophilia, closing)
- Discrete structures on the Internet: graphs and properties of graphs, giant components, strong and weak links, triadic closure, structural equilibrium, equilibrium theorem, web structure, PageRank, power laws, the long tail
- Introduction to game theory
Learning outcomes
At the end of this learning unit, the student is able to : | |
Given the learning outcomes of the "Bachelor in Engineering" program, this course contributes to the development, acquisition and evaluation of the following learning outcomes:
Students completing successfully this course will be able to
|
|
Content
- Introduction to graph theory (basic concepts, paths and connectivity, giant components).
- Applications of graph theory for modeling social networks (strong and weak ties, homophily, triadic closure, structural balance, balance theorem).
- Introduction to game theory (dominant strategies, pure and mixed strategies, Nash equilibrium, coordination and competition games, Pareto optimum and social optimum).
- Applications of game theory for modeling interactions on networks (traffic networks, auctions, markets, markets with intermediaries, negotiation on networks, information cascades, direct-benefit cascades, structural cascades).
- Network science: Web, search algorithms, PageRank, matrix representation, Web spam, power laws, small world phenomenon, long tail.
- Markov chains and random walk on a graph.
Teaching methods
- Weekly lectures (in auditorium or online, according to university requirements).
- Practical lab sessions in the computer room every week, to solve simplified problems using concepts explained during the lectures.
- One major design and programming project to apply these concepts to a more complex application.
Evaluation methods
- Project 25%
- Final written exam 75%
Other information
With respect to the AA benchmark of the programme "Bachelier en sciences informatiques", this course contributes to the development, acquisition, and evaluation of the following learning outcomes:
- S1.I1, S1.G1
- S2.2
- precisely identify and define basic concepts of graphs and trees with contextual examples that illuminate them,
- make explicit diverse methods of graph traversal,
- model various problems of the real world encountered in information technology using the appropriate graphs and trees, for example in social networks and the Web,
- make explicit the principal concepts of game theory (form of game, form of agent strategy) by means of appropriate examples,
- apply these concepts to Internet structures,
- define and interpret rigorously the concepts,
- avoid wrong interpretations and detect reasoning errors.
Online resources
LINFO1115 Moodle.
Bibliography
• David Easley and Jon Kleinberg (2010), Networks, Crowds and Markets: Reasoning About a Highly Connected World, Cambridge University Press.
• François Fouss, Marco Searens and Masashi Shimbo (2016), Algorithms and Models for Network Data Analysis and Link Analysis. Cambridge University Press.
• François Fouss, Marco Searens and Masashi Shimbo (2016), Algorithms and Models for Network Data Analysis and Link Analysis. Cambridge University Press.
Teaching materials
- Reasoning about a highly connected world (lecture slides)
Faculty or entity