Identifying structure in large social and information networks

I got the following from Aapo Kyrola:

Regarding partitioning, I recommend reading Stanford's Prof Mahoney's tutorial
about real-world graphs: http://cs.stanford.edu/people/mmahoney/icml10-tut/
Here is a link to the video of the tutorial: http://videolectures.net/kdd2010_mahoney_gtgm/

Basically he argues that although, for example, social network graphs have
local structure (such as your friend network in facebook might be nicely clustered),
they lack any global structure. This makes at least current methods of graph partitioning useless on such graphs.