General Info:

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

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/winter2019/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.

Date | Topic | Material | ||
---|---|---|---|---|

1 | December 10 | Introduction to propagation modeling and graph analysis | Lecture 1 | |

2 | December 12 | Centrality criteria and link analysis algorithms | Lecture 2 | |

3 | December 17 | Models of information propagation on graphs | Lecture 3 | |

4 | December 19 | Identification of influential spreaders on graphs | Lecture 4 | |

5 | January 7 | Influence maximization in social networks | Lecture 5 |

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)

- 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

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

- 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

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

- 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

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

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

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.

**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).

**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.

**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