Girvan–Newman algorithm: Difference between revisions

Revision as of 15:12, 15 June 2008

Revision as of 15:13, 15 June 2008

Line 1:

The '''Girvan-Newman algorithm''' is one of the methods used to detect communities in complex systems.<ref name=newman>Girvan M. and Newman M. E. J., Proc. Natl. Acad. Sci. USA '''99''', 7821-7826 (2002)</ref> The notion of a "community structure" is related to that of clustering, though it isn't quite the same. A community consists of a subset of nodes within which the node-node connections are dense, and the edges to nodes in other communities are less dense.<ref name=newman/> A simplified version of a network containing communities is shown in Fig. 1. There are numerous alternative method for detecting communities in networks. These include [[Hierarchical Clustering | hierarchical clustering]], partitioning graphs to maximize quality functions such as [[modularity]], k-clique percolation, etc.

== Edge betweenness and community structure ==