Mining Large Graphs: Laws and Tools

Posted in Science on September 07, 2008


Mining Large Graphs: Laws and Tools

Lecture slides:

  • Mining Large Graphs
  • Networks –Social and Technological
  • Examples of Networks
  • Networks of the Real-world
  • Mining Social Network Data
  • Networks as Phenomena
  • Models and Laws of Networks
  • Networks: Rich Data
  • Networks: A Matter of Scale
  • Networks: Scale Matters
  • Structure vs. Process
  • Structure of Networks
  • Diffusion in Networks
  • Tutorial outline
  • Mining Large GraphsPart 1: Structure and models of networks
  • Part 1: Outline
  • Part 1.1: Structural properties
  • Traditional approach
  • Motivation: New approach
  • Graphs and networks
  • Small-world effect
  • Degree distributions
  • Poisson vs. Scale-free network
  • Network resilience
  • Community structure
  • Spectral properties
  • What about evolving graphs?
  • Networks over time: Densification
  • Densification & degree distribution
  • Shrinking diameters
  • Properties hold in many graphs
  • Part 1.2: Models
  • 1.2 Models: Outline
  • (Erdos-Renyi) Random graph
  • Properties of random graphs
  • Evolution of a random graph
  • Subgraphs in random graphs
  • Random graphs: conclusion
  • Exponential random graphs (p* models)
  • Exponential random graphs
  • Small-world model
  • Preferential attachment
  • Edge copying model
  • Community guided attachment
  • Forest Fire Model
  • Forest Fire: Phase transitions
  • Kronecker graphs
  • Idea: Recursive graph generation
  • Kronecker product: Graph
  • Kronecker product: Definition
  • Kronecker graphs
  • Stochastic Kronecker graphs
  • Kronecker graphs: Intuition
  • Properties of Kronecker graphs
  • 1.3: Fitting the models to real graphs
  • The problem
  • Model estimation: approach
  • Fitting Kronecker graphs
  • Challenges
  • Challenge 1: Node correspondence
  • Challenge 2: calculating P(G|Θ,σ)
  • Model estimation: solution
  • Solution 1: Node correspondence
  • Sampling node correspondences
  • Solution 2: Calculating P(G|Θ,σ)
  • Experiments: Synthetic data
  • Convergence of properties
  • Experiments: real networks
  • AS graph (N=6500, E=26500)
  • AS: comparing graph properties
  • Epinions graph (N=76k, E=510k)
  • Scalability
  • Conclusion
  • Why should we care?
  • Reflections
  • References
  • Coming up next…

Author: Jure Leskovec, Condensed Matter Physics, Jožef Stefan Institute

Watch Video

Tags: Science, Lectures, Math, Computer Science, VideoLectures.Net, Graph Theory, Network Analysis