Statistical Relational Learning and Social Network Analysis

Simon Fraser University

Summer 2008

Instructor: Oliver Schulte

List of Readings

1. Week 1 and 2. Background: Relational Databases, Feature Vector Classification.

o Getoor on why relational learning cannot just "flatten" the relational database into a single table: From Dissertation, Stanford U 2002.

o Another introductory discussion of this point appears in "ILP for Knowledge Discovery in Databases", S. Wrobel, Sections 4.1-4.2, in "Relational Data Mining", Springer2 2001. I can't seem to find an electronic version of this piece.

a. Overheads on Relational Models and Notation.

2. Overheads on decision tree learning.
3. Software: CI Space, Decision Tree Applet or The AI Exploratorium. These are applets that allow you to run decision tree learner and explore datasets. I suggest you play around with at least one data set to get a feel for the learning algorithms.
1. Multi-relational Classification: Propositionalization and ILP.
1. The FOIL ILP system. Overview from Inductive Logic Programming, Techniques and Applications, Lavrac and Dzeroski, 1994. The whole book is available at http://www-ai.ijs.si/SasoDzeroski/ILPBook/. Software: FOIL .
2. Data Mining in Social Networks, Neville and Jensen. Symposium on Dynamic Social Network Modeling and Analysis. National Academy of Sciences. November 7-9, 2002. Washington, DC: National Academy Press. Software: PROXIMITY.
3. Multi-Relational Data Mining, An Introduction, Dzeroski, SigKDD 2003.
2. Multi-relational Model Building.
1. Background: Bayes Nets. Software: CIspace.

i. E. Charniak, 1991. "Bayesian Networks without Tears", AI magazine.

ii. Read through Kevin Murphy's Intro http://www.cs.ubc.ca/~murphyk/Bayes/bnintro.html . Don't worry if you don'•t understand all the details.

2. Learning Probabilistic Relational Models, Getoor et al., 2001.
3. Social Network Analysis: Introductions and Overview.
1. Software: JUNG-check out the demos, like the ranking demo. For other software, see http://en.wikipedia.org/wiki/Social_network_analysis_software . Pajek is a commonly used tool.
2. Intro on the Web: What is Social Network Analysis? and Basic Concepts in Social Network Analysis .
3. Introductory Survey: Different Aspects of Social Network Analysis, Mohsen Jamali and Hassan Abolhassani, IEEE/WIC/ACM conference on Web Intelligence 2006. Official Link is http://portal.acm.org/citation.cfm?id=1249050&dl=&coll=.
4. Computational Introduction to Basic Concepts: Introduction to the Formal Analysis of Social Networks Using Mathematica, Luis Izquierdo and Robert Hanneman, Wolfram Library Archive.
5. Introduction to Complex Networks: M. E. J. Newman, The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 Newman.pdf . Let's read Sections I,II and III and Section VII, pages 30-35 (total 26 pages).
4. Current Research in Network Analysis and Data Mining in Networks
1. D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, KDD'03.
2. J. Kleinberg. The small-world phenomenon: An algorithmic perspective. Proc. 32nd ACM Symposium on Theory of Computing, 2000. Also appears as Cornell Computer Science Technical Report 99-1776 (October 1999). I highly recommend that you watch at least part of his invited talk on SNA at http://videolectures.net/kdd07_kleinberg_cisnd/ .
3. Link Mining – a survey. Getoor and Diehl, SIGKDD 2005.
4. G.W. Flake, S. Lawrence, and C.L. Giles. Efficient identification of web communities. Proc. of the 6th International Conference on Knowledge Discovery and Data Mining (KDD), 2000.
   As a further reference (optional for this course), a more rigorous follow-up paper by Flake is available on-line:
   Graph Clustering and Minimum Cut Trees, Internet Mathematics Vol. 1, No. 4: 385-40. Gary William Flake, Robert E. Tarjan, and Kostas Tsioutsiouliklis, 2004.
5. General SR Framework: Markov Logic Networks: A Unifying Framework for SR learning. Software: ALCHEMY.