Large Networks, Clusters and Kronecker Products

author: Jure Leskovec, Computer Science Department, Stanford University
published: Sept. 18, 2009,   recorded: July 2009,   views: 1557
Categories
You might be experiencing some problems with Your Video player.

Slides

Slides
0:00 Data as Networks
0:17 Many data ARE networks
1:13 Statistical properties of networks
2:42 Networks: A matter of scale
3:20 Scaling of networks
5:06 Properties and models of networks
6:05 Plan for the talk
7:21 Group information in networks
8:48 Group growth as diffusion
9:34 P(join) vs. # friends in the group
10:45 Groups: More subtle features
11:19 Connectedness of friends - 1
12:31 Connectedness of friends - 2
13:00 Network communities
13:50 Finding network communities
14:24 Social network data
15:28 Micro-markets in sponsored search
16:11 Clustering and community finding
16:46 Algorithm of Girvan-Newman - 1
17:55 Algorithm of Girvan-Newman - 2
18:18 Girvan-Newman: Results
19:06 Small vs large networks - 1
19:34 How expressed are communities?
20:50 Community score (quality) - 1
20:54 Community score (quality) - 2
21:01 Community score (quality) - 3
21:05 Community score (quality) - 4
21:14 Network community profile plot - 1
22:17 Network community profile plot - 2
22:47 Probing networks
24:36 NCP plot: Meshes
25:52 NCP plot: Manifold dataset
26:11 NCP plot: Zachary´s karate club
26:38 NCP plot: Network science
27:08 NCP plot: Hierarchical networks
28:03 Natural hypothesis
29:36 Large networks: Very different
30:07 More NCP plots of networks
30:44 NCP: LiveJournal
31:13 Explanation: Upward part
32:51 Explanation: Downward part
33:45 Community size is independent of the network size
35:02 Whiskers shapes
35:23 Whiskers: Results of edge sparsity?
36:19 What if we remove whiskers? - 1
37:12 What if we remove whiskers? - 2
38:02 Nested core-periphery
38:45 Caveat: How do we cut?
40:05 NCP: Complete picture
42:26 "Regularization" and spectral methods
43:20 Regularized and non-regularized cuts - 1
44:48 Regularized and non-regularized cuts - 2
45:21 Are we really computing what we think?
47:26 Structure of large networks
47:33 Modeling nested core-periphery
49:14 Forest Fire model works
51:43 Forest Fire NCP plot
51:58 Kronecker graphs
53:37 Kronecker and network structure - 1
54:26 Kronecker and network structure - 2
55:44 Small vs large networks - 2
56:23 Cluster structure of large networks
56:41 Comparison with "Ground truth" - 1
57:16 Comparison with "Ground truth" - 2
57:58 Implications
58:58 Connections
59:47 - Questions

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
 
    Delicious Bibliography

Description

Emergence of the web and online computing applications gave rich data on human social activity that can be represented in a form of an interaction graph. One of the principal challenges then is to build models and understanding of the structure of such large networks. In this talk I will present our work on the cluster or community structure in large networks, where clusters are thought of as sets of nodes that are better connected internally than to the rest of the network. We find that large networks have very different clustering structure from well studied small social networks and graphs that are well-embeddable in a low-dimensional structure. In networks of millions of nodes tight clusters exist at only very small size scales up to around 100 nodes, while at large size scales networks becomes expander like. As this behavior is not explained, even at a qualitative level, by any of the commonly-used network generation models I will then present a network model based on Kronecker products that is able to produce graphs exhibiting a network structure similar to our observations.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: