Three-Toed Sloth

"Inferring Hierarchical Structure in Networks and Predicting Missing Links" (Next Week at the [Special Summer Bonus] Statistics Seminar)

Attention conservation notice: Only of interest if you are (1) in Pittsburgh next Tuesday, and (2) care about statistical network modeling and community discovery. Also, the guest is a friend, collaborator and mentor; but, despite his undiscriminating taste in acquaintances, an excellent speaker and scientist.

Usually, during the summer the CMU statistics seminar finds a shaded corner and drowses through the heat, with no more activity than an occasional twitch of its tail. Next week, however, it rouses itself for an exceptional visitor:

Cristopher Moore, "Inferring Hierarchical Structure in Networks and Predicting Missing Links"

Abstract: Given the large amounts of data that are now becoming available on social and biological networks, we need automated tools to extract important structural features from this data. Moreoever, for many networks, observing their links is a costly and imperfect process — food webs require field work, protein networks require combining pairs of proteins in the laboratory, and so on. Based on the part of the network we have seen so far, we would like to make good guesses about what pairs of vertices are likely to be connected, so we can focus limited resources on those pairs.

I will present a Bayesian approach to this problem, where we try to infer the hierarchical structure of the network, with communities and subcommunities at multiple levels of organization. We start with a rich model of random networks of this type, and then use a Monte Carlo Markov Chain to explore the space of these models. This approach performs quite well on real networks, often outperforming simple heuristics such as assuming that two vertices with neighbors in common are likely to be connected. In particular, it can handle both "assortative" behavior like that seen in many social networks, and "disassortative" behavior as in food webs.

Joint work with Aaron Clauset and Mark Newman.

Place and time: Tuesday, July 13, 2010, 4:00--5:00 p.m. in Porter Hall 125B

As usual, the seminar is free and open to the public.

Networks; Enigmas of Chance; Incestuous Amplification