I will discuss a set of algorithms for discovering community structure in networks natural divisions of network nodes into densely connected subgroups. These algorithms all share two definitive features: first, they involve iterative removal of edges from the network to split it into communities, the edges removed being identified using one of a number of possible "betweenness" measures, and second, these measures are, crucially, recalculated after each removal. I will also discuss a measure for the strength of the community structure found by the algorithms, which gives an objective metric for choosing the number of communities into which a network should be divided. 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.
Michelle Girvan is an assistant professor at the University of Maryland, joint between the department of physics and the Institute for Physical Sciences and Technology. Her research exists at the intersection of statistical physics, nonlinear dynamics, computer science, and the social sciences. She applies techniques from these areas toward the understanding of complex network problems. These involve systems for which the intricate tangle that connects interacting elements must explicitly be taken into account. Girvan's research addresses interdisciplinary, network-related problems by tackling broad theoretical issues, like the optimal deconstruction of complex networks and the detection of communities in overlapping networks, and then applying these insights toward the understanding of problems like social network construction, contagion processes, norm formation, and community fission.
Girvan did her undergraduate work at MIT, majoring in math and physics. From there, she went on to Cornell where she got her Ph.D in theoretical physics. She then took a postdoctoral fellowship at the Santa Fe Institute. Following that, she joined the faculty at the University of Maryland.
This talk is part of the CLIP Colloquium Series, organized by Jimmy Lin (jimmylin -at- umd .dot. edu). For the complete schedule, please visit http://www.umiacs.umd.edu/research/CLIP/colloq/.