Tim Finin of the UMBC ebiquity research group blogs :
[thanks Tim !]
Standard algorithms that extract the community structure from a large social network can be prohibitively expensive. Akshay Java has been exploring an idea that exploits the core-periphery structure of social networks to approximate communities in the graph.
The intuition behind his method is really quite simple: “The core of the social network typically defines the communities present in it. By looking at the link structure of the core and identifying how the rest of the network connects to the core we can efficiently compute communities in large graphs.” See his post on Approximating
the community structure of the long tail for a summary and links to a paper.