Mathematical Modeling of Propagation Phenomena

Course Overview

General Info:

CentraleSupélec
Dates: December '19 - January '20

Instructor: Fragkiskos Malliaros (John Cagnol, Sarah Lemler and Véronique Letort also participate at the thematic sequence ST2)
Email: fragkiskos.me [at] gmail.com
Office hours: Right after class (or send me an email and we will find a good time to meet)

TA: Abdulkadir Çelikkanat
Email: abdcelikkanat [at] gmail.com

Piazza: piazza.com/centralesupelec/winter2020/st2/home

Which people should we immunize, to prevent an epidemic (e.g., Ebola) as fast as possible? Which users should we target to in order to achieve an effective promotion campaign for our product? How do opinions or rumors get formed and propagate in social media (e.g., Twitter)? The modeling of propagation in various contexts (populations, materials, computer networks, social networks) has seen great progress in its formalization in recent decades. The goal of this class is to familiarize students with the classic techniques that will allow them to reproduce, predict and anticipate the effects of a virus or information propagation in real-life situations. Two main approaches will be considered in this course: propagation in a homogeneous population, leading to continuous modeling; propagation in a structured population with an underlying graph layer. In the latter case, the properties of the propagation phenomenon depend on the graph structure.

Schedule and Lectures

The slides for each lecture will be posted on piazza just before the start of the class.

	Date	Topic	Material	Structure
1	December 10	Introduction to propagation modeling and graph analysis	Topic 1	Lecture
2	December 13	Centrality criteria and link analysis algorithms	Topic 2	Lecture + Lab
3	December 18	Models of information propagation on graphs	Topic 3	Lecture + Lab
4	December 20, January 7	Identification of influential spreaders on graphs	Topic 4	Lecture + Lab, Lab
5	December 10	Influence maximization in social networks	Topic 5	Lecture + Lab

[December 10] Topic 1: Introduction to propagation modeling and graph analysis

Introduction to propagation modeling and graph analysis. Administrivia and course structure. Presentation of basic concepts in graph theory, linear algebra and spectral graph theory that will be used throughout the course. Basic network properties: degree distribution, clustering coefficient and shortest path length.

Reading:

Networks, crowds, and markets (Chapter 1, 2 and 13)
The structure and function of complex networks (Sections I and II)
Social media mining (Chapters 2 and 5)
Notes in linear algebra, probability, and proof techniques, by Jessica Su (Stanford University)

Additional:

Networks: An Introduction (Chapters 6, 8 and 9)
SVD and Low Rank Matrix Approximations, lecture notes by Tim Roughgarden and Gregory Valiant (Stanford University)
Lectures on Spectral Graph Theory, by Fan Chung (Chapter 2: Eigenvalues and the Laplacian of a graph)
J. Leskovec and E. Horvitz. Planetary-Scale Views on a Large Instant-Messaging Network. In WWW, 2008

[December 13] Topic 2: Centrality criteria and link analysis algorithms

Centrality criteria in graphs (degree, closeness, betweenness, eigenvector, Katz). Core decomposition on graphs. Link analysis ranking algorithms (HITS and PageRank).

Reading:

Social media mining (Chapters 2 and 5)
Networks, crowds, and markets (Chapter 1)
S. Brin and L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. In Proc. of the 7th International World Wide Web Conference (WWW), 1998
J. Kleinberg. Authoritative sources in a hyperlinked environment. In Proc. of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1998
S.B. Seidman. aNetwork Structure and Minimum Degree. Social Networks, 1983

Additional:

Networks: An Introduction (Chapter 7, Sections 7.1 - 7.7)
F. Bonchi, G. De Francisci Morales, and M. Riondato. Centrality Measures on Big Graphs: Exact, Approximated, and Distributed Algorithms. Tutorial at WWW, 2016.
U Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25(2), 163-177, 2001
F.D. Malliaros, A.N. Papadopoulos, and M. Vazirgiannis. Core Decomposition in Graphs: Concepts, Algorithms and Applications. In EDBT, 2016
V. Batagelj and M. Zaversnik. Generalized Cores. arXiv, 2002
T. H. Haveliwala. Topic-Sensitive PageRank. In Proc 11th International World Wide Web Conference, 2002
G. Jeh and J. Widom. Scaling Personalized Web Search. In Proc. roceedings of the 12th international conference on World Wide Web (WWW), 2003
A. Borodin, J. S. Rosenthal, G. O. Roberts, and P. Tsaparas. Finding Authorities and Hubs From Link Structures on the World Wide Web. In Proc. 10th International World Wide Web Conference, 2001
P. Berkhin. A Survey on PageRank Computing. Internet Mathematics 2(1), pages 73-120, 2005

[December 18] Topic 3: Models of information propagation on graphs

Cascading behavior on graphs. Models of virus and information propagation.

Reading:

Networks, crowds, and markets (Chapter 21)
J. Leskovec, M. McGlohon, C. Faloutsos, N. Glance, and M. Hurst. Cascading Behavior in Large Blog Graphs. In SDM, 2007
J. Leskovec, L. Adamic, and B. Huberman. The Dynamics of Viral Marketing. TWEB, 2007

Additional:

Networks: An Introduction (Chapter 17: 17.1 - 17.4)
Network science (Chapter 10)
D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec, and C. Faloutsos. Epidemic thresholds in real networks. ACM Trans. Inf. Syst. Secur. 10(4): 1:1-1:26, 2008
B.A. Prakash, D. Chakrabarti, N.C. Valler, M. Faloutsos, and C. Faloutsos. Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and Information Systems 33 (3), 2012
M. Goetz, J. Leskovec, M. Mcglohon, and C. Faloutsos. Modeling blog dynamics. In ICWSM, 2009
E. Adar and L. Adamic. Tracking information epidemics in blogspace. In Web Intelligence, 2005
J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. Structural Diversity in Social Contagion. PNAS 109 (16), 2012
A. Goyal, F. Bonchi, and L.V.S. Lakshmanan. Learning influence probabilities in social networks. In WSDM, 2010

[December 20, January 7] Topic 4: Identification of influential spreaders on graphs

Core decomposition and algorithms. Applications in dense subgraph detection, community detection, identification of influential spreaders.

Reading:

M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse. Identification of influential spreaders in complex networks. Nature Physics 6, 888-893, 2010
F.D. Malliaros, M.-E.G. Rossi, and M. Vazirgiannis. Locating Influential Nodes in Compex Networks. Scientific Reports 6(19307), 2016
L. Lu, D. Chen, X.-L. Ren, Q.-M. Zhang, Y.-C. Zhang, and T. Zhou. Vital nodes identification in complex networks. Physics Reports, 2016.
S. Pei and H. A. Makse. Spreading dynamics in complex networks. Journal of Statistical Mechanics: Theory and Experiment, 2013
M.E.J. Newman. Modularity and community structure in networks. PNAS, 2006

Additional:

S.B. Seidman. aNetwork Structure and Minimum Degree. Social Networks, 1983
F.D. Malliaros, A.N. Papadopoulos, and M. Vazirgiannis. Core Decomposition in Graphs: Concepts, Algorithms and Applications. In EDBT, 2016
V. Batagelj and M. Zaversnik. Generalized Cores. arXiv, 2002
C. Giatsidis, D. Thilikos, and M. Vazirgiannis. D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy. In ICDM, 2011
J. Wang and J. Cheng. Truss decomposition in massive networks. Proc. VLDB Endow., 5(9):812-823, 2012
J.I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. Large scale networks fingerprinting and visualization using the k-core decomposition. In NIPS, 2006

[January 10] Topic 5: Influence maximization

Influence maximization in social networks. The Greedy algorithm. Outbreak detection in networks.

Reading:

D. Kempe, J. Kleinberg, and E. Tardos. Maximizing the Spread of Influence through a Social Network. In KDD, 2003

Additional:

A. Goyal, W. Lu, and L. S.V. Lakshmanan. SIMPATH: An Efﬁcient Algorithm for Inﬂuence Maximization under the Linear Threshold Model. In ICDM, 2011
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective Outbreak Detection in Networks. In KDD, 2007
W. Chen, Y. Wang, and S. Yang. Efficient Influence Maximization in Social Networks. In KDD, 2009
W. Chen, Y. Yuan, and L. Zhang. Scalable Influence Maximization in Social Networks under the Linear Threshold Model. In ICDM, 2010
A. Goyal, W. Lu, and L. V.S. Lakshmanan. CELF++: optimizing the greedy algorithm for influence maximization in social networks. In WWW, 2011
E. Cohen, D. Delling, T. Pajor, and R.F. Werneck. Sketch-based Influence Maximization and Computation: Scaling up with Guarantees. In CIKM, 2014
Y. Wang, G. Cong, G. Song, and K. Xie. Community-based greedy algorithm for mining top-K influential nodes in mobile social networks. In KDD, 2010
M. Richardson and P. Domingos. Mining the Network Value of Customers. In KDD, 2001
M. Richardson and P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In KDD, 2002
J. Leskovec, L. Adamic, and B. Huberman. The Dynamics of Viral Marketing. TWEB, 2007
A. Goyal, F. Bonchi, and K. V.S. Lakshmanan. A Data-Based approach to Social Influence Maximization. In PVLDB, 2012

Course Structure

Learning objectives

Introduce students to the field of graph analysis for propagation modeling by:

Covering a wide range of topics, methodologies and applications related to information spreading over networks.
Giving the students the opportunity to obtain hands-on experience on dealing with graph data analysis for propagation phenomena.

We expect that by the end of the course, the students will have a thorough understanding of various data analysis tasks related to graphs and information spreading, and will be able to formulate and solve problems that involve propagation phenomena on networks.

Prerequisites

There is no official prerequisite for this course. However, the students are expected to:

Have basic knowledge of graph theory and linear algebra.
Be familiar with at least one programming language (e.g., Python or any language of their preference).

In the first lecture, we will review basic concepts in graph theory and linear algebra.

Reading material

Most of the material of the course is based on the books shown below. Some of the topics covered in the course are also based on research articles.

David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
Mark E.J. Newman. Networks: An Introduction. Oxford University Press, 2010.
Deepayan Chakrabarti and Christos Faloutsos. Graph Mining: Laws, Tools, and Case Studies. Synthesis Lectures on Data Mining and Knowledge Discovery, Morgan and Claypool Publishers, 2012.
Reza Zafarani, Mohammad Ali Abbasi and Huan Liu. Social Media Mining. Cambridge University Press, 2014.
Albert-Laszlo Barabasi. Network Science. Cambridge University Press, 2016.

Resources

Software tools

NetworkX: Python software package for graph analytics
igraph: collection of software packages for graph theory and network analysis (Python, C++ and R)
SNAP: high performance system for the analysis of large network (C++ and Python)
seaborn: statistical data visualization based on matplotlib
scikit-learn: Machine Learning library in Python
pandas: Python data analysis library
Gephi: graph visualization and exploration software

ST2: Mathematical Modeling of Propagation Phenomena

Propagation on Graphs

Course Overview

Schedule and Lectures

[December 10] Topic 1: Introduction to propagation modeling and graph analysis

[December 13] Topic 2: Centrality criteria and link analysis algorithms

[December 18] Topic 3: Models of information propagation on graphs

[December 20, January 7] Topic 4: Identification of influential spreaders on graphs

[January 10] Topic 5: Influence maximization

Course Structure

Resources