Information in Networks: Theory, Algorithms, and Applications

[Spring 2013] Information in Networks: Theory, Algorithms, and Applications

General Information

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	Credits: 3

Overview

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.

Grading

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

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

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

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

Textbooks

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

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 (not an exhaustive list)

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

D. Liben-Nowell, J. Kleinberg: The Link Prediction Problem for Social Networks. CIKM, 2003. (requires reaction notes)
L. Katz: A New Status Index Derived from Sociometric Analysis. Psychometrika, 1953. (requires reaction notes)
L. A. Adamic, E. Adar: Friends and neighbors on the web. Social Networks, 25(3):211-230, 2003. (requires reaction notes)

February 25: Link Analysis and Prediction II

Chapter 14 of David Easley and Jon Kleinberg: Networks, Crowds, and Markets. Cambridge University Press, 2010.
H. Tong, C. Faloutsos, J.-Y. Pan: Fast Random Walk with Restart and Its Applications. ICDM 2006. (requires reaction notes)
J. Tang, T. Lou, J. Kleinberg: Inferring Social Ties across Heterogenous Networks. WSDM 2012. (requires reaction notes)

March 4: Link Analysis and Prediction III and Social Theories

J. Travers and S. Milgram: An Experimental Study of the Small World Problem. Sociometry 32(1969). (requires reaction notes)
T. Schelling: Micromotives and Macrobehavior. Norton, 1978. (Demo: Schelling segregation model.) (requires reaction notes)
A.L Barabasi, R. Albert: Emergence of Scaling in Random Networks. Science, 286, 1999. (requires reaction notes)
N. Contractor, S. Wasserman, K. Faust: Testing Multi Theoretical, Multilevel Hypotheses about Organizational Networks: An Analytic Framework and Empirical Example. Academy of Management Review, 31(3):681-703, 2006. (requires reaction notes)

March 11: Axiomatic Approaches & Theoretical Justifications

M. Gupte, T. Eliassi-Rad: Measuring Tie Strength in Implicit Social Networks. WebSci 2012. (requires reaction notes)
P. Sarkar, D. Chakrabarti, A. W. Moore: Theoretical Justification of Popular Link Prediction Heuristics. IJCAI 2011. (requires reaction notes)
A. Altman, M. Tennenholtz: Axiomatic Foundations for Ranking Systems. Journal of Artificial Intelligence Research 31 (2008) 473-495. (requires reaction notes)
R. Jin, V. E. Lee, Hui Hong: Axiomatic Ranking of Network Role Similarity. KDD 2011. (requires reaction notes)
D. Koutra, J.T. Vogelsteiny, C. Faloutsos: DELTACON: A Principled Massive-Graph Similarity Function. SDM 2013. (requires reaction notes)

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 different approaches)

April 8: Role Discovery

K. Henderson, et al: It's Who You Know: Graph Mining Using Recursive Structural Features. KDD 2011. (requires reaction notes)
K. Henderson, et al: RolX: Structural Role Extraction & Mining in Large Graphs. KDD 2012. (requires reaction notes)
A. Anderson, D. Huttenlocher, J. Kleinberg: The Effects of User Similarity in Social Media WSDM 2012. (requires reaction notes)

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

M. Hay, G. Miklau, D. Jensen, D. Towsley, C. Li: Resisting Structural Re-identification in Anonymized Social Networks. VLDB Journal 19(6):797-823 (2010). (requires reaction notes)
Pedram Pedarsani, Matthias Grossglauser: On the Privacy of Anonymized Networks. KDD 2011. (requires reaction notes)
P. Boldi, F. Bonchi, A. Gionis, T. Tassa: Injecting Uncertainty in Graphs for Identity Obfuscation. PVLDB 5(11):1376-1387 (2012). (requires reaction notes)

April 29: Re-Identification

A. Narayanan, V. Shmatikov: Robust De-anonymization of Large Sparse Datasets, or How to Break Anonymity of the Netflix Prize Dataset. S&P (Oakland) 2008. (requires reaction notes)
A. Narayanan, V. Shmatikov: De-anonymizing Social Networks. S&P (Oakland) 2009. (requires reaction notes)
Y. Zhu, L. Qin, J. Xu Yu, Y. Ke, X. Lin: High Efficiency and Quality: Large Graphs Matching. CIKM 2011. (requires reaction notes)

May 6: Project Presentations