Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Testing Girvan-Newman Algorithm

No description
by

Min Hyung Kang

on 4 December 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Testing Girvan-Newman Algorithm

Girvan-Newman Algorithm
Background
Background
Testing Girvan-Newman Algorithm
Daniel Kang
Plots and
Results

Results
Code
Python
Source Code

1. Setup testbed
Girvan-Newman
Algorithm
Modularity of
Network

Topic
Implement the Girvan-Newman Algorithm
Test on classical test set
Evaluate its performance

Repeat until no edges remain :
1. Compute edge betweenness for (all / affected) edges
2. Delete an edge with maximum betweenness
(from lecture 7)
Modularity
Overview
- When z_in < 8 : both approaches perform poorly

- Performance of GN-algorithm drastically increases around z_in = 8 ~ 10

- When z_in> 10, algorithm shows near-perfect classification

Conclusion
1. Generate Testbed
2. GN Algorithm
- Until four communites
- Best modularity
3. Find Optimal Matching
Results - Classification
Results - Accuracy
Results - Accuracy
Optimal cut
Two Methods
1. GN algorithm until we have four communities

2. GN algorithm until we have individual nodes.
Choose partition with highest modularity
2. GN Algorithm
3. Find Optimal Matching
Classical Testbed
1. 4 communities, each consisting 32 nodes

2. Z_in : average number of links from a node to another node within the same community <=> Z_out

3. Z_in + Z_out = 16 = <k> of whole network
Z_in=14
Full transcript