Webpage for CMPT 880

Statistical Relational Learning and Social Network Analysis


Simon Fraser University


Summer 2008


Instructor: Oliver Schulte



List of Readings


Presentation Schedule


















Bayes Nets/PRMs





Jung/SNA Intro





Complex Networks





Maximizing Spread of Influence in SN





J. Kleinberg. The small-world phenomenon: An algorithmic perspective.






Link Mining





Markov Logic, Alchemy






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 multi-relational 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 trust-based 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 run-time 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.