Fall 2013

Practice is Better than Theory: Using Approximate Counting to Mine Large Graphs

Monday, November 18th, 2013 9:35 am10:00 am

Add to Calendar

Algorithms developed in the last decade to analyze large networks (centrality, neighbourhood functions, distance distributions) use approximate set representations. The ways in which these approximate set representation are used give no theoretical guarantee, yet the computations are extremely precise (when compared with a ground truth) and even outperform the theoretical precision of the set representations themselves. It would be interesting to understand why.