Evaluating Communities Problem Solution-Mohammed Abdullah.pdf

This document provides a comprehensive guide to solving the Girvan–Newman algorithm step by step, a prominent method for detecting communities within networks. It starts with a detailed explanation of how to implement the algorithm, focusing on the step-by-step process of calculating and recalculating betweenness centrality, identifying and removing edges, and progressively dividing the network into distinct communities.

To aid in understanding, the document includes a section on evaluating communities, discussing various methods and metrics used to assess the quality of the detected communities, with a particular emphasis on modularity.

Additionally, the document features several examples that illustrate the application of the Girvan–Newman algorithm on different types of networks. These examples provide practical insights into each step of the process, helping readers grasp the nuances of the algorithm and its effectiveness in uncovering community structures.

By the end of this document, readers will have a thorough understanding of the Girvan–Newman algorithm, from its theoretical foundations to practical implementation, including community evaluation techniques and illustrative examples.

1. Evaluating Communities
Mohammed Abdullah



1

2. Extended definition
The Girvan–Newman algorithm:
Hierarchical method used to detect communities
2

3. Extended definition
"edge betweenness" of an edge:
The number of shortest paths between pairs of nodes that run
along it.
3

4. Modularity
4

5. Modularity
5
m is the total number of edges of the network

6. Modularity
6
m is the total number of edges of the network
A is the adjacency matrix

7. Modularity
7
m is the total number of edges of the network
A is the adjacency matrix
function yields 1 if vertices i and j
are in the same community, 0
otherwise.

8. Modularity
8
m is the total number of edges of the network
A is the adjacency matrix
function yields 1 if vertices i and j
are in the same community, 0
otherwise.
ki is the degree of vertex i

9. Modularity
9

10. Modularity
10
Total number of edges joining vertices of
community s
sum of the degrees of the vertices of s

11. Modularity
11
Total number of edges joining vertices of
community s
sum of the degrees of the vertices of s
number of communities,

12. Modularity
12
Fraction of edges of the network inside the
community
Expected fraction of edges that would be there
if the network were a random network with the
same degree for each vertex. T

13. Algorithm
13
The algorithm's steps for community detection:

1.The betweenness of all existing edges in the
network is calculated first.

14. Algorithm
14
The algorithm's steps for community detection:

1.The betweenness of all existing edges in the
network is calculated first.
2.The edge(s) with the highest betweenness are
removed.

15. Algorithm
15
The algorithm's steps for community detection:

1.The betweenness of all existing edges in the
network is calculated first.
2.The edge(s) with the highest betweenness are
removed.
3.The betweenness of all edges affected by the
removal is recalculated.

16. Algorithm
16
The algorithm's steps for community detection:

1.The betweenness of all existing edges in the
network is calculated first.
2.The edge(s) with the highest betweenness are
removed.
3.The betweenness of all edges affected by the
removal is recalculated.

4.Steps 2 and 3 are repeated until no edges
remain.

17. Problem
17

18. Problem
18
Shortest path — Breadth First Search (BFS)

19. Shortest path — Breadth First Search (BFS)
19

20. Options
20

21. Options
21

22. BFS Traversal
22

23. Neighbours of A
23

24. Neighbours of C
24

25. Neighbours of C
25

26. Neighbours of B
26

27. Level Order Traversal
27

28. No of Inputs to each node (Indegree)
28

29. No of Inputs to each node (Indegree)
29

30. Divide the weights
30

31. Divide the weights
31

32. Divide the weights
32

33. Divide the weights
33

34. Update Table
34

35. Node B
35

36. Update Table
36

37. Update Table
37

38. Update Table
38

39. Node E
39

40. Update Table
40

41. Node D
41

42. Update Table
42

43. Node C
43

44. Update Table
44

45. Edge Betweenness Value (1st iter)
45

46. Highest
46

47. Remove Highest
47

48. Remove Highest
48

49. Iter 2
49

50. Graph for Iter 2
50

51. Graph for Iter 2
51

52. Node A
52

53. Update Table
53

54. Node B
54

55. Update Table
55

56. Node E
56

57. Update Table
57

58. Node D
58

59. Update Table
59

60. Node C
60

61. Update Table
61

62. Edge Betweenness Value (2st iter)
62

63. Remove Highest
63

64. Remove Highest
64

65. Remove Highest
65

66. Remove Highest
66

67. Stop Algorithm
67

68. Partitioned Communities
68

69. Modularity
69

70. Scenario - Symmetry
70

71. Scenario- Communities Formed
71