Predavatelj: Jure Leskovec

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.