event thumbnail image
NIPS ´08 Workshop: Algebraic and combinatorial methods in machine learning

Algebraic statistics for random graph models: Markov bases and their uses

author: Stephen E. Fienberg, Carnegie Mellon University
author: Alessandro Rinaldo, Carnegie Mellon University
author: Sonja Petrović, The University of Illinois at Chicago

Description

We use algebraic geometry to study a statistical model for the analysis of networks represented by graphs with directed edges due to Holland and Leinhardt, known as p1, which allows for differential attraction (popularity) and expansiveness, as well as an additional effect due to reciprocation. In particular, we attempt to derive Markov bases for p1 and to link these to the results on Markov bases for working with log-linear models for contingency tables. Because of the contingency table representation for p1 we expect some form of congruence. Markov bases and related algebraic geometry notions are useful for at least two statistical problems: (i) determining condition for the existence of maximum likelihood estimates, and (ii) using them to traverse conditional (given minimal sufficient statistics) sample spaces, and thus generating ``exact'' distributions useful for assessing goodness of fit. We outline some of these potential uses for the algebraic representation of p1.

You might be experiencing some problems with Your Video player.
Slides
0:00 Algebraic Statistics of p1 Network Models: Markov Bases and Their Uses
1:03 Context (1)
1:28 Context (2)
1:48 Context (3)
1:51 Context (4)
2:38 Context (4)
2:52 Context (6)
3:02 General framework for networks evolving over time (1)
3:20 General framework for networks evolving over time (2)
3:50 General framework for networks evolving over time (3)
4:07 General framework for networks evolving over time (4)
4:15 General framework for networks evolving over time (5)
4:23 General framework for networks evolving over time (6)
4:48 Example: The Framingham "Obesity" Study (1)
6:29 Example: The Framingham "Obesity" Study (2)
7:08 Example: The Collective Dynamics of Smoking in a Large Social Network
7:38 Example: Monks in a Monastery
8:33 Holland and Leinhardt's p1 model (1)
9:20 Holland and Leinhardt's p1 model (2)
9:38 Holland and Leinhardt's p1 model (3)
10:25 Holland and Leinhardt's p1 model (4)
11:10 Estimation for p1
13:36 Aside - The Normal Distribution was 275 Years Old
13:57 Hotteling and the Normal Distribution
14:13 p1 in Log-linear Form
15:49 Primer: Algebraic Representation and Computer Algebra Tools
17:20 Algebraic Version of p1 in Log-linear Form (1)
17:29 Algebraic Version of p1 in Log-linear Form (2)
17:35 Algebraic Version of p1 in Log-linear Form (3)
17:47 p1 as a toric variety (1)
17:51 p1 as a toric variety (2)
18:02 p1 as a toric variety (3)
18:11 p1 as a toric variety (4)
18:34 p1 as a toric variety (5)
18:39 p1 as a toric variety (6)
18:45 Toric ideal of simplification of p1 (1)
18:54 Toric ideal of simplification of p1 (2)
19:12 Toric ideal of simplification of p1 (3)
19:26 Main Theorem - toric ideal of p1 (1)
19:45 Main Theorem - toric ideal of p1 (2)
19:49 Main Theorem - toric ideal of p1 (3)
19:57 Main Theorem - toric ideal of p1 (4)
20:05 Example with 4 nodes (1)
20:25 Example with 4 nodes (2)
20:34 3-node network (1)
20:51 3-node network (2)
20:58 3-node network (3)
21:23 3-node network (4)
21:31 4-node network: constant (1)
21:48 4-node network: constant (2)
21:57 4-node network: constant (3)
22:03 4-node network: constant (4)
22:08 4-node network: constant (5)
22:28 4-node network: constant (6)
22:45 4-node network: edge-dependent (1)
22:50 4-node network: edge-dependent (2)
22:57 4-node network: edge-dependent (3)
23:00 4-node network: edge-dependent (4)
23:03 4-node network: edge-dependent (5)
23:05 4-node network: edge-dependent (6)
23:10 4-node network: edge-dependent (7)
23:15 4-node network: edge-dependent (8)
23:19 4-node network: edge-dependent (9)
23:24 4-node network: edge-dependent (10)
23:30 Summary
28:58 Questions

Lecture rating

People found this lecture:
Worth seeing
because it is:
 Valuable and informative
Well presented
Easily understandable
Acceptably recorded
You need to login to cast your vote.

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: