Algorithm AntiDifferentiation and A case study with PageRank, mincuts, and flow
David F. Gleich
Michael W. Mahoney
Contents
These are the computational codes and data that go along with the ICML 2014 paper
David F. Gleich and Michael Mahoney
Algorithm AntiDifferentiation: A case study with mincuts, spectral, and flow
In Proceedings of the International Conference on Machine Learning, 2014.
Downloads
 l1pagerankicml.tar.gz The ICML version of the l1 pagerank codes
Files
Demos
figure_1_example.m
Produce the vectors for Figure 1 in the ICML paperexample_netscience.m
Produce the netscience Figures for the ICML paperdemos/simple_example.m
A simple example suitable for live demos
Algorithms

acl_method.m
An implementation of the AndersenChungLang push method to compute a PageRank vector 
flow_improve.m
An algorithm for the FlowImprove method of Andersen and Lang 
prl1_gurobi.m
Use gurobi to solve an l1PageRank problem prcut_gurobi.m
Use gurobi to solve a mincut on the PageRank cut graph
Helpers
cut_graph.m
Construct the cutgraph for FlowImiprovegeneral_cut_graph.m
Construct the PageRank cutgraph for general constructions.gmatrices.m
Return a struct of all the matrices associated with a graph.igraph_draw.m
Use igraph via python to layout a graphincidence_matrix.m
Create the nodeedge indicence matrix for a graphlaplacian.m
Consruct the Laplacian matrix of a graphload_graph.m
Load one of the datasets and avoid icky path problemsnlaplacian.m
Construct the normalized Laplacian of a graphnormout.m
Compute a rowstochastic matrix from an adjacency matrix.set_figure_size.m
The most useful script to make Matlab figures look goodsetup_paths.m
Add all the required libraries to the matlab path, and the code itselfwadjacency.m
Construct the weighted adjacency matrix of a graph
Testing
test_prcut_gurobi.m
Make sure gurobi and CVX agree for the prcut problemtest_prl1_gurobi.m
Make sure gurobi and CVX agree for the prl1 problem
Exploration
This directory contains a whole bunch of scripts that we developed while working out the theory. Think of this as a labnotebook for what we looked at before the full picture came together.