• PNAS Alerting Services
  • Science Sessions: The PNAS Podcast Program

Community structure in social and biological networks

  1. M. E. J. Newman*§
  1. *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

  1. Edited by Lawrence A. Shepp, Rutgers, State University of New Jersey–New Brunswick, Piscataway, NJ, and approved April 6, 2002

  1. Figure 1
    View larger version:
    Figure 1

    A schematic representation of a network with community structure. In this network there are three communities of densely connected vertices (circles with solid lines), with a much lower density of connections (gray lines) between them.

  2. Figure 2
    View larger version:
    Figure 2

    An example of a small hierarchical clustering tree. The circles at the bottom represent the vertices in the network, and the tree shows the order in which they join together to form communities for a given definition of the weight Wij of connections between vertex pairs.

  3. Figure 3
    View larger version:
    Figure 3

    The fraction of vertices correctly classified in computer-generated graphs of the type described in the text, as the average number of intercommunity edges per vertex is varied. The circles are results for the method presented in this article; the squares are for a standard hierarchical clustering calculation based on numbers of edge-independent paths between vertices. Each point is an average over 100 realizations of the graphs. Lines between points are included solely as a guide to the eye.

  4. Figure 4
    View larger version:
    Figure 4

    (a) The friendship network from Zachary's karate club study (26) as described in the text. Nodes associated with the club administrator's faction are drawn as circles, those associated with the instructor's faction are drawn as squares. (b) Hierarchical tree showing the complete community structure for the network calculated by using the algorithm presented in this article. The initial split of the network into two groups is in agreement with the actual factions observed by Zachary, with the exception that node 3 is misclassified. (c) Hierarchical tree calculated by using edge-independent path counts, which fails to extract the known community structure of the network.

  5. Figure 5
    View larger version:
    Figure 5

    Hierarchical tree for the network reflecting the schedule of regular-season Division I college football games for year 2000. Nodes in the network represent teams, and edges represent games between teams. Our algorithm identifies nearly all of the conference structure in the network.

  6. Figure 6
    View larger version:
    Figure 6

    The largest component of the Santa Fe Institute collaboration network, with the primary divisions detected by our algorithm indicated by different vertex shapes.

  7. Figure 7
    View larger version:
    Figure 7

    Hierarchical tree for the Chesapeake Bay food web described in the text.

Online Impact