Girvan–Newman algorithm: Difference between revisions

Revision as of 15:04, 26 February 2007

Revision as of 03:47, 24 May 2007

Line 1:

The '''Newman-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 different than that of clustering. The latter refers to the "small-world" property of a certain group of nodes within a network, where the [[Average Path Length | average path length]] <math>\ell</math> among the nodes is relatively small. A community instead, is a subset of nodes within which the node-node connections are dense, and the edges among communities are less dense.<ref name=newman/> A simplified version of a network containing communities in it is shown in Fig. 1. An alternative method for the detection of communities within networks is the [[Hierarchical Clustering | hierarchical clustering]].

== Edge betweenness and community structure ==

Line 5:

The hierarchical clustering method is based on assigning a weight for every edge and placing these edges into an initially empty network, starting from edges with strong weights and progressing towards the weakest ones. The edges with the greatest weights within the community are the most central ones. Although traditional in community detection, the method presents some pathologies. One of them for instance, is the inability to classify in a community a node which is connected to the network with only one edge.

The Newman-Girvan-Newman algorithm works the opposite way. Instead of trying to construct a measure that tells us which edges are the most central to communities, it focuses on these edges that are least central, the edges that are most "between" communities. The communities are detected by progressively removing edges from the original graph, rather than by adding the strongest edges to an initially empty network.

Vertex betweenness has been studied in the past as a measure of the [[Centrality | centrality]] and influence of 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 a measure of the influence of a node over the flow of information between other nodes, especially in cases where information flow over a network primarily follows the shortest available path. The Newman-Girvan-Newman algorithm extends this definition to the case of edges, defining the "edge betweenness" of an edge as the number of shortest paths between pairs of nodes that run along it. If there is more than one shortest path between a pair of nodes, each path is assigned equal weight such that the total weight of all of the paths is equal to unity. If a network contains communities or groups that are only loosely connected by a few intergroup edges, then all shortest paths between different communities must go along one of these few edges. Thus, the edges connecting communities will have high edge betweenness (at least '''one''' of them). By removing these edges, the groups are separated from one another and so the underlying community structure of the network is revealed.

The algorithm's steps for community detection are summarized below

Line 18:

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.

The end result of the Newman-Girvan-Newman algorithm is a [[dendrogram]]. As the Newman-Girvan-Newman 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 dendrogram are individual nodes.

== See also ==