Girvan–Newman algorithm: Difference between revisions

Revision as of 23:50, 13 March 2012

Revision as of 10:32, 30 March 2012

Line 1:

The '''Girvan–Newman algorithm''' (named after Michelle Girvan and [[Mark Newman]]) is one of the methods used to detect [[Community_structure | communities]] in [[complex system]]s.<ref name=newman>Girvan M. and Newman M. E. J., [http://dx.doi.org/10.1073/pnas.122653799 Community structure in social and biological networks], 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/> There are numerous alternative methods for detecting communities in networks. These include [[Hierarchical Clustering | hierarchical clustering]], partitioning graphs to maximize [[quality function]]s such as [[Modularity (networks)|network modularity]], [[surprise (networks)|surprise]] maximization, [[clique percolation method|''k''-clique percolation]], etc.

== Edge betweenness and community structure ==

Line 22:

== See also ==

* [[Betweenness]]

* [[Closeness (mathematics)|Closeness]]

* [[Hierarchical clustering]]

* [[Modularity (networks)|Modularity]]

* [[Surprise (networks)|Surprise]]

== References ==