Large Networks, Clusters and Kronecker Products
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.
| 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 |
Lecture rating
| People found this lecture: | ||
| Worth seeing | ||
| because it is: | ||
| Valuable and informative | ||
| Well presented | ||
| Easily understandable | ||
| Acceptably recorded | ||
| You need to login to cast your vote. | ||
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.
Related content
Link this page
Would you like to put a link to this lecture on your homepage?Go ahead! Copy the HTML snippet !





Jure Leskovec, zagovor diplome