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