computer science

Girvan–Newman algorithm

Girvan–Newman algorithm is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Girvan–Newman algorithm rather than just read about it. In short: The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems. Edge betweenness and community structure The Girvan–Newman algorithm detects communities by progressively removing edges from the original network.

Key takeaways

Girvan–Newman algorithm belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Girvan–Newman algorithm to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Girvan–Newman algorithm from memory before moving on to harder problems.

Reference excerpt

The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems.

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. 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. Vertex betweenness is an indicator of highly central nodes in networks. For any node i {\displaystyle i} , vertex betweenness is defined as the fraction 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. The 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 inter-group 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

The betweenness of all existing edges in the network is calculated first. The edge(s) with the highest betweenness are removed. The betweenness of all edges affected by the removal is recalculated. Steps 2 and 3 are repeated until no edges remain. 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 Girvan–Newman algorithm is a dendrogram. As the Girvan–Newman algorithm runs, the dendrogram is produced from the top down (i.e. the network splits up into different communities with the successive removal of links). The leaves of the dendrogram are individual nodes.

See also Closeness Hierarchical clustering Modularity

References

Worked examples

Example 1 — a first encounter with Girvan–Newman algorithm

Start with the simplest possible case. Write down what Girvan–Newman algorithm claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Girvan–Newman algorithm before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Girvan–Newman algorithm ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Girvan–Newman algorithm

In research: Girvan–Newman algorithm appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Girvan–Newman algorithm in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Girvan–Newman algorithm is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph algorithms, Network analysis, Networks, so understanding it makes those chapters shorter.
In everyday life: Look for Girvan–Newman algorithm outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Girvan–Newman algorithm” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Girvan–Newman algorithm in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Girvan–Newman algorithm means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Girvan–Newman algorithm out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Girvan–Newman algorithm in simple terms?

The Girvan–Newman algorithm (named after Michelle Girvan and Mark Newman) is a hierarchical method used to detect communities in complex systems. Edge betweenness and community structure The Girvan–Newman algorithm detects communities by progressively removing edges from the original network.

Why does Girvan–Newman algorithm matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Girvan–Newman algorithm?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Girvan–Newman algorithm.