# Mining Large Graphs: Laws and Tools

Posted in Science on September 07, 2008

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
• Motivation: New approach
• Graphs and networks
• Small-world effect
• Degree distributions
• Poisson vs. Scale-free network
• Network resilience
• Community structure
• Spectral properties
• 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