TF1 - Tools for large networks: Structure and diffusion

Time: Monday, April 21 (full-day, 8:30am to 5:00pm)
Location: Room 201C (Level 2)

Abstract:

How do graphs look like? How do they evolve over time? How can we find patterns, anomalies and regularities in them? How to find influential nodes in the network? The tutorial has four parts. In the first, we review some static and temporal 'laws', like the 'six degrees of separation', and we also describe several models and graph generators that try to match properties of real graphs. Second part deals with the diffusion and cascading behavior in networks, where a virus or a piece of information spreads through the network. Here we present models and properties of information propagation on the web and in the viral marketing domains and design algorithms to find influential nodes and detect outbreaks quickly. In the third part, we present powerful tools for the analysis of static and dynamic graphs, like the Singular Value Decomposition, the CUR decomposition, tensors, community detection and graph partitioning, and related tools. We show how they can be used for community and topic detection on real datasets, for discovery of important nodes and important connections on social networks, computer networks, and the web. In the last part we focus on case studies, where we cover communication patterns of MSN Instant Messenger, how to find fraudsters on eBay, how to predict quality of web search results from the properties of web graph, Internet traffic analysis, and virus propagation results.

The emphasis is on the intuition behind all these tools, and on their practical impact for the analysis of large, real datasets. The more theoretical aspects and proofs are delegated to the bibliography that the tutorial will provide.

More details about this tutorial.

Presenters:

Jure Leskovec and Christos Faloutsos, Carnegie-Mellon University (USA)

Inquiries can be sent to: