Webpage for CMPT 880
Statistical Relational Learning and Social Network Analysis
Simon Fraser University
Summer 2008
Instructor: Oliver Schulte
Presentation Schedule
Week 
Topic 
Presenter 







4 
Proximity 
Chiraq 


5 
Bayes Nets/PRMs 
Jacinthe 


7 
Jung/SNA Intro 
Mohsen 


8 
Complex Networks 
Philippe 


9 
Maximizing Spread of Influence in SN 
Brittany 


10 
J. Kleinberg. The smallworld
phenomenon: An algorithmic perspective. 
Amir 


10 
Link Mining 
Ashgan 


11 
Markov Logic, Alchemy 
Gustavo 


Suggested
Projects
I'm
open to suggestions based on student interest as long as they are related to
the course content. Some general ideas from me.
Empirical
Work: Comparing Different Algorithms. Tracking statistical or learning
issues.

Compare different algorithms that are doing similar things. For example:
o
FOIL and Progol learn classification rules.
o
Warmr, Safarii, Claudien learn multirelational association rules.
o
Proximity and Tilde learn decision trees.
o
Jung and Igraph perform network analysis.
If
you go with a project of this type, we should discuss evaluation methodology.
Applications
of SR learning algorithms to other projects, problems or datasets.
This
type of project applies an SR learning algorithm to data or problems you are
interested in. For example, you may have medical data with relations and want
to predict patients with a certain illness. Or you may be interested in
extracting relationships from text. Perhaps you can apply SR learning to
improve trustbased recommender systems.
A
concrete suggestion: How about applying SR algorithms to social network data
with attributes? E.g.
á
Take
data with attributes and links.
á
Maybe
add interesting attributes like betweenness, indegree etc.
á
See
if you can find relationships, e.g. Òrich people have high centralityÓ etc.
Improvements
to existing algorithms.
This
type of project pursues an idea of your own for an existing algorithm. For
example, perhaps you have an idea for addressing the locality problems in FOIL
and other learning algorithms based on local heuristics. Or you can suggest a
new way to do statistical inference. To evaluate your idea, we would need the
source or at least clean APIs for implementation.
Theoretical
Work: Relate different definitions (e.g. game theory and SNA). Apply theorems
to derive interesting conclusions or new algorithms.
This
is for the more theoretically inclined. It can be interesting to relate
definitions and theorems from different but intersecting areas, like statistics
and social network analysis, or game theory. A new algorithm would be
acceptable too, but it should come with pseudocode, some kind of correctness
proof and runtime analysis, especially if you don't implement it. I don't have
any particular theoretical projects in mind but I'm open to discussing some if
there is interest.
A concrete suggestion: Investigate defining a similarity/distance measure between objects that takes into account the objects they are related to. As we discussed in class, one approach is to define a (possibly recursive) similarity measure between sets like the Hausdorff metric or an average version of Hausdorff (the distance between set A and B is the average over the distance of points x in A from set B). You could work out details, compare it with other suggestions in the literature and maybe suggest a kernel based on your similarity measure.