[Spring 2013] Information in Networks: Theory, Algorithms, and Applications
|Instructor: Tina Eliassi-Rad
||Office hours: Mondays 2:00 PM - 3:00 PM in CBIM 08
|Lecture Time: Mondays 3:20 PM - 6:20 PM
||Lecture Place: CBIM, Room 22
|Course number: 16:198:672
This graduate seminar will survey recent work in network science and computational social science from a machine learning and data mining perspective, covering topics such as: properties of real-world networks, graph models, network dynamics, information diffusion, collective classification, and community detection. Application domains discussed will range from social networks (coauthorship graphs) to information networks (the Web) to communication networks (email graphs, retweet graphs), and so on.
Prerequisites: Background in data mining and machine learning suggested. A basic course in probability and statistics required.
- Class participation (15%)
- Reaction notes (35%) -- due prior to class -- 1 to 2 pages per assigned reading, answering these three questions:
- What are the main technical contributions?
- What are the weakness, and how could they be improved?
- What are some of the promising research questions, and how could they be pursued?
Class project (50%) -- involving an exploratory data analysis of a novel data set, or creation of a novel model for constructing a network, or design of a novel algorithm
- Proposal report & pitch (10%) -- 2 pages plus 5-minute pitch -- due March 25th class time
Should include answers to the following questions:
- What is the problem?
- Why is it interesting and important?
- Why is it hard? Why have previous approaches failed?
- What are the key components of your approach?
- What data sets and metrics will be used to validate the approach?
Class presentation (15%) -- 25 minutes presentation -- due May 6th class time
Final report (25%) -- 6 to 8 pages -- due May 15th at 11:59 PM Eastern
- Check the Resources folder of the class sakai site (16:198:672:01 Sp13) if you cannot find a resource on the Web.
- Upload your contributions (reaction notes, proposal report, presentation, final report, etc) to the class sakai site (16:198:672:01 Sp13).
These textbooks are recommended and not required.
- Albert-László Barabási.
Network Science Book Project. 2012.
- Deepayan Chakrabarti and Christos Faloutsos. Graph Mining: Laws, Tools, and Case Studies. Morgan and Claypool Publishers, 2012.
- David Easley and Jon Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
- Matthew O. Jackson. Social and Economic Networks. Princeton University Press, 2008. (TOC and Introductory Chapter)
- Mark Newman. Networks: An Introduction. Oxford University Press, 2010.
- Stanley Wasserman and Katherine Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994 (first printing), 2009 (19th printing).
Schedule / Syllabus (subject to change)
- January 28: Introduction & Descriptive Analysis
- Chapter 1 of Eric Kolaczyk: Statistical Analysis of Network Data. Springer, 2009.
- Chapter 1 of Albert-László Barabási: Network Science Book Project. 2012.
- Chapter 2 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.
- Chapter 2 of Matthew Jackson: Social and Economic Networks. Princeton University Press, 2008.
- C. T. Butts: Revisiting the Foundations of Network Analysis. Science, 325, 2009:414-416.
- February 4: Network Patterns and Laws
- Chapters 1 through 7 of D. Chakrabarti and C. Faloutsos: Graph Mining: Laws, Tools, and Case Studies. Morgan and Claypool Publishers, 2012.
- February 11: Strong and Weak Tie
Chapter 3 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.
- M. Granovetter: The Strength of Weak Ties. American Journal of Sociology, 78(6), 1973:1360-1380. (requires reaction notes)
- R. Burt: Structural Holes and Good Ideas. American Journal of Sociology, Vol. 110, No. 2 2004. (requires reaction notes)
- J.-P. Onnela, J. Saramaki, J. Hyvonen, G. Szabo, D. Lazer, K. Kaski, J. Kertesz, A.L. Barabasi: Structure and Tie Strengths in Mobile Communication Networks. PNAS, 2007. Supporting information. (requires reaction notes)
- February 18: Link Analysis and Prediction I
- February 25: Link Analysis and Prediction II
- March 4: Link Analysis and Prediction III and Social Theories
- March 11: Axiomatic Approaches & Theoretical Justifications
- March 18: Spring Break
- March 25: Graph Models & Project Pitches
- Chapters 8 through 13 of D. Chakrabarti and C. Faloutsos: Graph Mining: Laws, Tools, and Case Studies. Morgan and Claypool Publishers, 2012.
- April 1: Community Discovery
- J. Leskovec, K. Lang, M. Mahoney: Empirical
Comparison of Algorithms for Network Community Detection. WWW 2010. (requires reaction notes)
- B. Abrahao, S. Soundarajan, J. Hopcroft, R. Kleinberg: On the Separability of Structural Classes of Communities. KDD 2012. (requires reaction notes)
- K. Henderson, T. Eliassi-Rad, S. Papadimitriou, C. Faloutsos: HCDF: A Hybrid Community Discovery Framework. SDM 2010. (requires reaction notes)
- Optional reading: S. Fortunato: Community Detection in Graphs,
arXiv:0906.0612, 2009. (A survey of
- April 8: Role Discovery
- April 15: Relational Learning and Collective Classification
- B. Gallagher, H. Tong, T. Eliassi-Rad, C. Faloutsos: Using Ghost Edges for Classification in Sparsely Labeled Networks. KDD 2008. (requires reaction notes)
- P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, T. Eliassi-Rad: Collective Classification in Network Data. AI Magazine, 29(3), 2008. (requires reaction notes)
- D. Koutra, T.-Y. Ke, U. Kang, D. H. Chau, H.-K. Kenneth Pao, C. Faloutsos: Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms. ECML PKDD 2011. (requires reaction notes)
- Optional reading: J. Neville, B. Gallagher, T. Eliassi-Rad, T. Wang:
Correcting Evaluation Bias of Relational Classifiers with Network Cross Validation. Knowledge and Information Systems (KAIS), Springer, January 2012.
- April 22: Privacy
- April 29: Re-Identification
- May 6: Project Presentations