**Statistical Relational Learning and Social Network
Analysis**

Simon Fraser University

Summer 2008

Instructor: Oliver Schulte

**List of Readings**

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

- Overheads on decision tree learning.
- 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.
- Multi-relational Classification: Propositionalization and ILP.
- 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 . - 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. - Multi-Relational Data Mining, An Introduction, Dzeroski, SigKDD 2003.
- Multi-relational Model Building.
- 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.

- Learning Probabilistic Relational Models, Getoor et al., 2001.
- Social Network Analysis: Introductions and Overview.
- 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.
- Intro on the Web: What is Social Network Analysis? and Basic Concepts in Social Network Analysis .
- 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=.
- Computational Introduction to Basic Concepts: Introduction to the Formal Analysis of Social Networks Using Mathematica, Luis Izquierdo and Robert Hanneman, Wolfram Library Archive.
- 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).
- Current Research in Network Analysis and Data Mining in Networks
- D. Kempe, J.
Kleinberg, E. Tardos, Maximizing the spread of influence through a social
network, KDD'03.
- 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/ .
- Link Mining – a survey. Getoor and Diehl, SIGKDD 2005.
- 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. - General SR Framework: Markov Logic Networks: A Unifying Framework for SR learning. Software: ALCHEMY.