Revision as of 18:49, 10 December 2006 edit Gmagkots (talk \| contribs) 5 edits ←Created page with 'The Newman-Girvan 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. Sc...'		Revision as of 19:52, 21 December 2006 edit undo TheParanoidOne (talk \| contribs) Extended confirmed users 23,582 edits rm speedily deleted image with no copyright status Next edit →
Line 21: The fact that the only betweennesses being recalculated are only the ones which are affected by the removal, may lessen the running time of the process' simulation in computers. However, the betweenness centrality must be recalculated with each step, or severe errors occur. The reason is that the network adapts itself to the new conditions set after the edge removal. For instance, if two communities are connected by more than one edge, then there is no guarantee that '''all''' of these edges will have high betweenness. According to the method, we know that '''at least one''' of them will have, but nothing more than that is known. By recalculating betweennesses after the removal of each edge, it is ensured that at least one of the remaining edges between two communities will always have a high value. [[Image:Dendrogram.gif\|thumb\|right\|'''Fig.[2]''' A sample dendrogram. As edges are removed, the network breaks apart. At any given point during the execution of the algorithm, the number of different communities can be found by taking a horizontal slice through the dendrogram.]] The end result of the Newman-Girvan algorithm is a dendrogram as shown in at the right. As the Newman-Girvan algorithm runs, the dendrogram is produced from the top down (ie. the network splits up into different communities with the successive removal of links). The leaves of the tree are individual nodes. == See also ==

Girvan–Newman algorithm: Difference between revisions