Detecting community structure in networks英文资料.pdf

Eur. Phys. J. B 38, 321–330 (2004) THE EUROPEAN DOI: 10.1140/epjb/e2004-00124-y PHYSICAL JOURNAL B Detecting community structure in networks M.E.J. Newmana Department of Physics and Center for the Study of Complex Systems, University of Michigan, Ann Arbor, MI 48109–1120, USA Received 10 November 2003 c Published online 14 May 2004 – EDP Sciences, Societ`a Italiana di Fisica, Springer-Verlag 2004 Abstract. There has been considerable recent interest in algorithms for finding communities in networks— groups of vertices within which connections are dense, but between which connections are sparser. Here we review the progress that has been made towards this end. We begin by describing some traditional methods of community detection, such as spectral bisection, the Kernighan–Lin algorithm and hierarchical clustering based on similarity measures. None of these methods, however, is ideal for the types of real-world network data with which current research is concerned, such as Internet and web data and biological and social networks. We describe a number of more recent algorithms that appear to work well with these data, including algorithms based on edge betweenness scores, on counts of short loops in networks and on voltage differences in resistor networks. PACS. 89.75.Hc Networks and genealogical trees – 87.23.Ge Dynamics of social systems – 89.20.Hh World Wide Web, Internet – 05.10.-a Computational methods in statistical physics and nonlinear dynamics 1 Introduction In the continuing flurry of research activity within ph