Community structure in social and biological networks

Community structure in social and biological networks

December 7, 2001 | Michelle Girvan and M. E. J. Newman
This paper introduces a method for detecting community structure in social and biological networks. Community structure refers to the tendency of network nodes to form tightly-knit groups with loose connections between them. The authors propose a new method based on edge betweenness, which identifies edges that are most "between" communities. By iteratively removing these edges, the method reveals the underlying community structure of the network. The method was tested on both computer-generated graphs and real-world networks. In computer-generated graphs, the algorithm reliably detected known community structures, even when the number of inter-community connections was high. In the Zachary's karate club study, the algorithm correctly identified the two main factions in the network, with only one node misclassified. In the college football network, the algorithm successfully identified conference structures, with only a few exceptions. The method was also applied to a collaboration network of scientists at the Santa Fe Institute and a food web of marine organisms in the Chesapeake Bay. In both cases, the algorithm detected clear community structures that corresponded to meaningful divisions in the data. In the collaboration network, communities were formed based on research topics and methodologies. In the food web, communities were formed based on ecological roles, with pelagic and benthic organisms separated into distinct groups. The authors conclude that their method is a sensitive and accurate way to detect community structure in both real and artificial networks. They suggest that the method could be extended to handle weighted and directed graphs, and that further improvements could be made to increase its efficiency. The method has potential applications in various fields, including the analysis of neural networks, the World-Wide Web, and other complex systems.This paper introduces a method for detecting community structure in social and biological networks. Community structure refers to the tendency of network nodes to form tightly-knit groups with loose connections between them. The authors propose a new method based on edge betweenness, which identifies edges that are most "between" communities. By iteratively removing these edges, the method reveals the underlying community structure of the network. The method was tested on both computer-generated graphs and real-world networks. In computer-generated graphs, the algorithm reliably detected known community structures, even when the number of inter-community connections was high. In the Zachary's karate club study, the algorithm correctly identified the two main factions in the network, with only one node misclassified. In the college football network, the algorithm successfully identified conference structures, with only a few exceptions. The method was also applied to a collaboration network of scientists at the Santa Fe Institute and a food web of marine organisms in the Chesapeake Bay. In both cases, the algorithm detected clear community structures that corresponded to meaningful divisions in the data. In the collaboration network, communities were formed based on research topics and methodologies. In the food web, communities were formed based on ecological roles, with pelagic and benthic organisms separated into distinct groups. The authors conclude that their method is a sensitive and accurate way to detect community structure in both real and artificial networks. They suggest that the method could be extended to handle weighted and directed graphs, and that further improvements could be made to increase its efficiency. The method has potential applications in various fields, including the analysis of neural networks, the World-Wide Web, and other complex systems.
Reach us at info@study.space
[slides] Community structure in social and biological networks | StudySpace