community_structure_in_social_and_biologial_newtworck英文资料.pdf

Community structure in social and biological networks M. Girvan*†‡ and M. E. J. Newman*§ *Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, NM 87501; †Department of Physics, Cornell University, Clark Hall, Ithaca, NY 14853-2501; and §Department of Physics, University of Michigan, Ann Arbor, MI 48109-1120 Edited by Lawrence A. Shepp, Rutgers, State University of New Jersey–New Brunswick, Piscataway, NJ, and approved April 6, 2002 (received for review December 6, 2001) A number of recent studies have focused on the statistical prop- In this article, we consider another property, which, as we will erties of networked systems such as social networks and the show, appears to be common to many networks, the property of Worldwide Web. Researchers have concentrated particularly on a community structure. (This property is also sometimes called few properties that seem to be common to many networks: the clustering, but we refrain from this usage to avoid confusion with small-world property, power-law degree distributions, and net- the other meaning of the word clustering introduced in the work transitivity. In this article, we highlight another property that preceding paragraph.) Consider for a moment the case of social is found in many networks, the property of community structure, networks—networks of friendships or other acquaintances be- in which network nodes are joined together in tightly knit groups, tween individuals. It is a matter of common experience that such between which there are only looser connections. We propose a networks seem to have communities in them: subsets of vertices method for detecting such communities, built around the idea of within which vertex–vertex connections are dense, but between using centrality indices to find community boundaries. We test our