Condensed Matter Seminar

Communities and the large-scale structure of networks

Prof. Mark Newman
University of Michigan

Friday, October 27, 2006 - 4:00 P.M., NSH 184

Many systems of interest to science can be represented as networks. One of the challenges in recent studies of these systems has been to find ways to detect meaningful structure in large network data sets such as web and internet data or biochemical networks. We consider the particular problem of finding "communities" -- tightly-knit groups of nodes within larger networks. We show how the problem can be reformulated in terms of the spectral properties of graphs, leading to fast and effective computer algorithms based on eigenvector decompositions. The same methods also lead to a number of interesting new insights concerning network structure in general, revealing connections between community structure in networks and centrality and correlation measures of network structure.