Graduate Seminar on Graph Mining and Network Analysis

Spring 2011: Graduate Seminar on Graph Mining and Network Analysis

General Information

Instructor: Tina Eliassi-Rad	Office hours: Tuesdays 2:30-4:30 PM in CBIM 08
Time: Tuesdays 5:00-8:00 PM	Place: Hill Center 254
Course number: 16:198:672	Credits: 3

Overview

This graduate seminar will survey recent work in network 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.

Grading

Class participation (15%)

Reaction notes (25%) -- 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 (60%)

Proposal report (10%) -- 2 pages plus 5-minute pitch -- due March 1st

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 -- April 19th & 26th

Final report (35%) -- 8 to 10 pages -- due May 3rd

For guidance on writing the final report, see slide 70 of Eamonn Keogh's KDD'09 Tutorial on How to do good research, get it published in SIGKDD and get it cited!
Follow ACM formatting guidelines

Notes

Upload your contributions (reaction notes, proposal report, presentation, final report, etc) to the class sakai site.

Resources

Eamonn Keogh's KDD'09 Tutorial on How to do good research, get it published in SIGKDD and get it cited!
Software, tools, and data

Schedule / Syllabus (Subject to Change)

January 18: Introduction and Overview

Chapter 1

January 25: Descriptive Analysis

C. T. Butts: Revisiting the Foundations of Network Analysis. Science, 325, 2009:414-416. (requires reaction notes)
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.

February 1: Strength of Weak Ties

Chapter 3 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets . Cambridge University Press, 2010.

B.A. Huberman, D.M. Romero, F. Wu. Social Networks that Matter: Twitter under the Microscope. First Monday, 14(1), 2009. (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)
M. Granovetter: The Strength of Weak Ties. American Journal of Sociology, 78(6), 1973:1360-1380. (requires reaction notes)

February 8: Economics of Attention & Community Discovery

F. Wang, B. Huberman: Novelty and Collective Attention. PNAS, 104(45), 2007:17599-17601. (requires reaction notes)
S. Asur, B. Huberman: Predicting the Future With Social Media. arXiv:1003.5699v1, 2010. (requires reaction notes)
S. Fortunato: Community Detection in Graphs. Physics Reports, 486(3-5), 2010:75-174. (requires reaction notes)

February 15: Community Discovery

J. Leskovec, K. Lang, M. Mahoney: Empirical Comparison of Algorithms for Network Community Detection. WWW 2010:631-640. (requires reaction notes)
K. Henderson, T. Eliassi-Rad, S. Papadimitriou, C. Faloutsos: HCDF: A Hybrid Community Discovery Framework. SDM 2010:754-765. (requires reaction notes)

February 22: Random Walks

L. Backstrom and J. Leskovec: Supervised Random Walks: Predicting and Recommending Links in Social Networks , WSDM 2011. (requires reaction notes)

Chapter 14 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets . Cambridge University Press, 2010.

H. Tong, C. Faloutsos, and J.-Y. Pan: Fast Random Walk with Restart and Its Applications. ICDM 2006:613-622. (requires reaction notes)

March 1: Graph Mining & Proposal Pitches

C. Chen, C. X. Lin, M. Fredrikson, M. Christodorescu, X. Yan, J. Han: Mining Graph Patterns Efficiently via Randomized Summaries. PVLDB 2(1), 2009:742-753. (requires reaction notes)
Y. Tian, R.A. Hankins, J.M. Patel: Efficient Aggregation for Graph Summarization. SIGMOD Conference 2008: 567-580.
N. Zhang, Y. Tian, J. M. Patel: Discovery-Driven Graph Summarization. ICDE 2010: 880-891.
D. Chakrabarti, C. Faloutsos: Graph Mining: Laws, Generators, and Algorithms. ACM Comput. Surv., 38(1), 2006. (Slides from 2009) (requires reaction notes)
J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos, Z. Ghahramani: Kronecker Graphs: An Approach to Modeling Networks. Journal of Machine Learning Research (JMLR), 11, 2010.

March 8: 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:256-264. (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:93-106. (requires reaction notes)
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 2011.

March 15: No Class (Spring Break)

March 22: Network Dynamics

Chapters 16, 17, and 19 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets . Cambridge University Press, 2010.

March 29: No Class (Tina on travel)

April 5: Homophily and Social Influence

Chapter 4 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets . Cambridge University Press, 2010.

S. Aral, L. Muchnika, A. Sundararajan: Distinguishing Influence-Based Contagion from Homophily-Driven Diffusion in Dynamic Networks. PNAS, 106(51), 2009: 21544-21549. (requires reaction notes)
A. Anagnostopoulos, R. Kumar, M. Mahdian: Influence and Correlation in Social Networks. KDD 2008: 7-15. (requires reaction notes)

April 12: Networks with Positive and Negative Edges

Chapter 5 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets . Cambridge University Press, 2010.

Jure Leskovec, Daniel P. Huttenlocher, Jon M. Kleinberg: Predicting Positive and Negative Links in Online Social Networks. WWW 2010:641-650. (requires reaction notes)
M. Szell, R. Lambiotte, S. Thurner: Multirelational Organization of Large-scale Social Networks in an Online World. PNAS, 2010. (requires reaction notes)
J. Kunegis, A. Lommatzsch, C. Bauckhage: The Slashdot Zoo: Mining a Social Network with Negative Edges. WWW 2009:741-750. (requires reaction notes)

April 19: Project Presentations

April 26: Project Presentations

May 3: No Class -- Final reports are due.