Scribd
Upload
32 views3 pages

Girman Newman Algorithm

The document explains the Girvan–Newman algorithm for detecting communities in a network. It describes the structure of a given network with two dense groups and identifies important edges based on betweenness. The algorithm removes the edge with the highest betweenness, effectively splitting the network into two distinct communities.

Uploaded by

shaiksharmila185
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views3 pages

Girman Newman Algorithm

The document explains the Girvan–Newman algorithm for detecting communities in a network. It describes the structure of a given network with two dense groups and identifies important edges based on betweenness. The algorithm removes the edge with the highest betweenness, effectively splitting the network into two distinct communities.

Uploaded by

shaiksharmila185
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Let’s break down the graph clearly and see how the Girvan–Newman algorithm works on it.

🔹 Given Network
A—B—C D—E—F

\ /
G—H

🔸 Connections (Edges)
 A–B
 B–C
 B–G

 G–H
 H–D
 D–E
 E–F

🔹 Step 1: Understand the Structure


This network actually has two dense groups:
Left group
 A, B, C
 connected internally
Right group

 D, E, F
 connected internally
Bridge between groups
 B→G→H→D
Nodes G and H act like intermediaries between the two communities.

🔹 Step 2: Identify Important (High Betweenness) Edges


Remember:
Edge betweenness = number of shortest paths passing through an edge.

🔸 Which edges carry most shortest paths?


Edges in the middle:
 B–G

 G–H
 H–D
These lie between the two clusters.
Many shortest paths from left side to right side must pass through them.

🔹 Step 3: First Edge Removal


The algorithm removes the edge with highest betweenness.
Usually the most central bridge is:
G—H
Why?
 Almost every path from left community to right community passes through it.

 It is the narrowest bottleneck.

🔹 Step 4: After Removing G—H


Graph becomes:
Left part:
A—B—C

|
G
Right part:
H—D—E—F
now the network splits into two communities.

🔹 Final Communities Detected


Community 1
 A, B, C, G
Community 2
 H, D, E, F

Because Girvan–Newman assumes:


Edges connecting communities have high betweenness.
In your graph:
 Internal edges (like A–B, D–E) are used by fewer shortest paths

 Bridge edges (B–G, G–H, H–D) are used by many shortest paths
So removing them separates the network naturally.

You might also like