03-25

Unveiling Isolated and Layered Communities in Complex Networks

In the past decade, a number of studies have focused on the statistical properties of networked systems such as social networks and the World-Wide Web. Researchers have focused on properties common to many real-world networks such as small-world properties, power-law degree distributions and network transitivity.

In this talk, I will focus on another property found in many networks, that of community structure, in which network nodes are joined together in tightly knit groups, between which there are only looser connections. I will discuss algorithms for discovering community structure in networks, beginning with methods that strictly partition the nodes into non-overlapping groups. These methods work by detecting the boundaries between communities and do not require the user to input the number of desired communities a priori.

I will also discuss methods for finding highly overlapping or "layered" community structure in networks. In this case, using a combination of the aforementioned techniques, simulated annealing, and other tools borrowed from statistical physics, it is possible to find multiple possible divisions of the network into different communities. I'll demonstrate that the algorithms are highly effective at discovering community structure in both computer-generated and real-world network data, and show how they can be used to shed light on the sometimes dauntingly complex structure of networked systems.