Girvan–Newman algorithm: Difference between revisions

Revision as of 12:29, 27 April 2019

Revision as of 15:43, 27 April 2019

Line 2:

== Edge betweenness and community structure ==

The Girvan–Newman algorithm detects communities by progressively removing edges from the original network. The connected components of the remaining network are the communities. heyInstead of trying to construct a measure that tells us which edges are the most central to communities, the Girvan–Newman algorithm focuses on edges that are most likely "between" communities.

Instead of trying to construct a measure that tells us which edges are the most central to communities, the Girvan–Newman algorithm focuses on edges that are most likely "between" communities.

[[Betweenness centrality|Vertex betweenness]] is an indicator of highly [[centrality|central]] nodes in networks. For any node <math>i</math>, vertex betweenness is defined as the number of shortest paths between pairs of nodes that run through it. It is relevant to models where the network modulates transfer of goods between known start and end points, under the assumption that such transfer seeks the shortest available route.