Hi all, Our colloquia speaker this week, Michelle Girvan, will be talking about clustering and networks. Beyond being a high school and college friend of mine, Michelle is a statistical physicist by training (her PhD at Cornell was with Steve Strogatz and postdoc at the Sante Fe Institute), but has been venturing into problems of interest to computer scientists, applied mathematicians, and sociologists. Michelle is an assistant professor at University of Maryland, but has been visiting IAS for the past year. The colloquia will be help at 4:15pm in the small lecture room (105). --mike ---- Unveiling Isolated and Layered Communities in Complex Networks Michelle Girvan, University of Maryland, IAS 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.