ITAT 2016 Proceedings, CEUR Workshop Proceedings Vol. 1649, pp. 200–205
http://ceur-ws.org/Vol-1649, Series ISSN 1613-0073, c 2016 J. Coroničová Hurajová, T. Madaras
Revising the Newman-Girvan algorithm
Jana Coroničová Hurajová1 ∗ Tomáš Madaras2
1 The Faculty of Business Economics with seat in Košice,
The University of Economics in Bratislava,
Tajovského 13, 041 30 Košice, Slovakia
jana.coronicova.hurajova@euke.sk
2 The Faculty of Sciences,
P.J. Šafárik University in Košice,
Jesenná 5, 040 01 Košice, Slovakia,
tomas.madaras@upjs.sk
WWW home page: umv.science.upjs.sk
Abstract: One of the common approaches for the commu- the edge betweenness as an amount of information flow
nity detection in complex networks is the Girvan-Newman being propagated through a link between actors of a com-
algorithm [5] which is based on repeated deletion of edges plex network (and assuming that the information exchange
having the maximum edge betweenness centrality. Al- takes place mainly on shortest paths), one may argue that
though widely used, it may result in different dendrograms distinct communities within a network are mutually con-
of hierarchies of communities if there are several edges nected (and, hence, communicating) with relatively few
eligible for removal (see [6]) thus leaving an ambiguous edges whose edge betweenness is higher than of those
formation of network subgroups. We will present possible ones between the actors of the same community. When
ways to overcome these issues using, instead of edge be- deleting those edges, the network tends to simplify, even-
tweenness computation for single edges, the group edge tually breaking into smaller subnetworks (note, however,
betweenness for subsets of edges to be subjects of re- that after each deletion, edge betweenness centralities of
moval. the resulting network shall be recalculated again). Thus,
we obtain a sequence of graphs starting from the origi-
nal one and ending with an edgeless graph, along with
1 Introduction the sequence of partitions the vertex set (the initial par-
tition is the whole set, the final one consists of isolated
One of fundamental analyses performed in the exploration vertices); when two consecutive graphs differ in their con-
of complex networks concerns the detection of their com- nected components, we record the splitting (refining) of
munity structure, which means to find, within a graph rep- the partition of the predecessing graph. In this way, the se-
resenting the network, certain clusters of vertices which quence of partitions forms a dendrogram showing the hi-
are, at one side, sparsely interconnected and, on the other erarchy of communities within the graph (the choice of the
side, they have dense in-cluster links by many edges. The appropriate level describing, in the best way, the commu-
vertices within a cluster show a kind of similarities and nity structure of the graph, is a matter of external decision
form functionally compact units. As there is no general and does not follow from algorithm).
definition of cluster, there are many ways to obtain collec-
tions of network communities; a comprehensive overview Despite the elegancy of Girvan and Newman approach
of contemporary state-of-art in this area can be found in and the popularity of their algorithm, an attention recently
[3]. turns to other methods, mainly due to the fact that they are
Among the approaches that determine the graph com- quicker (the Girvan-Newman algorithm has, in general,
munities by breaking it into smaller parts, an important the complexity O(m2 · n), thus can be effectively used on
role plays the Girvan-Newman algorithm described first graphs up to n ∼ 10000, see [3]). Furthermore, it seems
in [5]. It is based on successive deletion of edges which that many implementations of community detection
have the maximum edge betweenness centrality which is algorithms which are based on recursive edge deletion do
the quantity measuring the frequency of appearance of an not make difference when equivalent edges (for example,
edge on geodesic paths in a graph. Formally, it is defined with the same edge betweenness) are considered for
σu,v (e) deletion. This issue was adressed in [6] where it was
as the sum B(e) = ∑ where σu,v is the num- demonstrated how the random deletion of different edges
σu,v
u,v∈V (G) with the same maximum edge betweenness centrality
ber of shortest u − v-paths and σu,v (e) is the number of results in different hierarchies of partitions, when used
shortest u − v-paths which contain the edge e. Interpreting on the wheel graph W6 . A possible obvious suggestion to
∗ Research supported by the project for young teachers, researchers remove all such edges at once (as discussed, for example,
and PhD. students No. I-16-104-00 in [1] in the connection with possible speeding up the
Revising the Newman-Girvan Algorithm 201
original Girvan-Newman algorithm) would, however, σu,v (A)
G, as the sum B(A) = ∑ where σu,v (A) is the
individualize all the vertices (thus producing no rea- u,v∈V (G)
σu,v
sonable hierarchy) – even at the very beginning of the number of shortest u − v-paths which contain at least one
process – of edge transitive graphs, and, more generally, edge from A. Note that if |A| = 1 then we obtain the stan-
of so called edge betweenness-uniform graphs (that is, dard edge betweenness as in [5]. The revised Newman-
the graphs whose edges have the same value of edge Girvan algorithm on a graph G then proceeds as follows:
betweenness centrality). Such graphs are not so rare: in starting with G0 = G, a sequence {Gi }ki=0 (where Gk is
[4], it was shown that each strongly regular graph (that is, edgeless graph) is constructed in such a way that, if there
an n-vertex k-regular graph with the property that any pair appears, during the computation of edge betweennesses of
of its adjacent vertices has λ common neighbours, and any Gi , a set Mi of mi ≥ 2 edges all of them having the maxi-
pair of its nonadjacent vertices has µ common neighbours, mum betweenness among the edges of Gi , then determine
for certain n, k, λ , µ) is edge betweenness-uniform; since the smallest ℓi such that there is unique subset Ebi ⊆ Mi of
it is also known that, for particular n, k, λ , µ, the number ℓi edges with the property that the group edge between-
of nonisomorphic strongly regular graphs is at least expo- ness centrality of Ebi is the maximal among all subsets of
nential in terms of number of vertices (see [2]). We tested Mi consisting of ℓi edges (note that ℓi ≤ mi , thus it is well
all edge betweenness-uniform graphs on 3–10 vertices defined). The graph Gi+1 is then obtained from Gi by re-
(their list was published first in [6]) for communities using moving all edges from Ebi ; if Gi+1 has more components
the procedures FindGraphCommunities[...,Method than Gi , the vertex sets of its components forms the new
-> "Centrality"] (to obtain the list of sets of vertices level in hierarchy of partitions of V (G). The pseudocode
forming communities) and CommunityGraphPlot[...] for this process is given in Algorithm 1; the used notation
(to visualize communities within a graph) of follows the common standards of graph theory, the partic-
Wolfram Mathematica, or using the procedure ular specialized symbols are b0 (G) (the zeroth Betti num-
IGCommunitiesEdgeBetweenness[...] from the ber of G, that is, the number of its connected components),
Wolfram Mathematica third-party package IgraphM hVi i (the subgraph of G induced by the set Vi ⊆ V (G)) and
(see [7]). The results for graphs on 3–9 vertices G \ Ei (the subgraph of G obtained by deleting all edges of
are shown in Figure 1 (the brown clusters corre- Ei ).
spond to graph communities based on partition-
We have implemented the key elements of the algo-
ing by FindGraphCommunities[...,Method ->
rithm in Wolfram Mathematica 10 along with the algo-
"Centrality"] procedure, the yellow clusters to the
rithm for edge group betweenness calculation. Since
ones based on IGCommunitiesEdgeBetweenness pro-
the latter algorithm is – according to our knowl-
cedure); one can see that, on some graphs, the community
edge – not yet known to have effective implementa-
structure is different although the underlying algorithm
tion, we used the straightforward approach which de-
should be the same (the most remarkable difference can be
termines, for each pair u, v of vertices of a graph
observed on the blue-highlighted 9-vertex graph of Figure
G, all shortest u − v-paths (in Wolfram language, this
2 obtained from two 6-cycles by identifying the corre-
can be done by calling procedure FindPath[G, u, v,
sponding vertices of their maximum independent sets).
GraphDistance[G, u, v], All] and then checks how
Also, for many of these graphs it seems that they have
many of them passes through an edge of the given edge
no community structure (as both built-in and IGraphM
group. Our implementation of the edge group between-
community finding procedure aggregate all vertices
ness algorithm – when being called on a single edge – is
into a single cluster); hence, when being processed by
also useful as an alternative for built-in Wolfram Math-
algorithm of [1], one would have only two possibilities for
ematica procedure EdgeBetweennessCentrality[..]
communities: either the whole vertex set or the partition
which returns numerical approximations (although with
consisting of singletons (and the more reasonable choice
high precision) of edge betweenness centralities whereas
would be the single community). Nevertheless, our results
our version returns exact values in the form of fractions.
show that there are also edge betweenness-uniform graphs
for which both procedures (as well as other community Let us note that our approach may lead, in particu-
detection methods, like modularity maximization) return lar cases, to much worse performance of the correspond-
non-trivial community structure which, however, cannot ing algorithm when compared with the original Newman-
be obtained by the algorithm of [1]. Girvan algorithm; this is caused mainly by large number of
subsets of edges with the same maximum edge between-
ness which have to be checked to select the unique one
2 The revised Newman-Girvan algorithm with the maximum group edge betweenness. This is, how-
In order to overcome – at least, on theoretical basis – the ever, the trade-off for getting rid of uncertainties in edge
problem to decide which edge has to be removed if there removal.
are several ones with the same maximal edge between- To show the difference of behaviour of our algo-
ness, we will utilize the concept of group edge between- rithm in comparison with the original one or the one
ness which is defined, for a subset A of edge set of a graph of [1], consider the graph of Figure 3. It contains
202 J. Coroničová Hurajová, T. Madaras
1 4 6
1 5
1 3 1 5
3 5
5
5
5 2
2 6
1
1 2 3 4
6 2 4
2 6
2 1 3 4
1 3 2 3 3
4
2 4
3
{{1, 2, 3}} {{1, 2, 3, 4, 5}} {{1, 2, 3, 4, 5, 6}}
2 3 1 1 4
3 5
{{1, 2, 3, 4, 5, 6}}
1 5
{{1, 2, 3}} 2
1
5
2 6
6
4
2 3
{{1, 2, 3, 4, 5, 6}} 3 4
{{1, 2, 3, 4, 5}} {{1, 2, 3, 4, 5, 6}}
3 3 2
6
2 2
5
4 1 5 1 4
1 1
5 2
5
1 2 1 4
3 7
3 2 4 3 6
1 2 6 7 5 3 4
1 2 3 4 5 6
{{1, 2, 3}} {{1, 2, 3, 4, 5}} 3
3 2 2
{{1, 2, 3, 4, 5, 6, 7}}
5
{{2, 4, 6}, {1, 3, 5}} 1 2 6 7 5 3 4
1
1 4
{{1, 2, 3, 4, 5, 6, 7}}
5 2
4
3
1
3 6
{{1, 2, 3, 4, 5}}
{{1, 2, 3}} {{1, 3, 5}, {2, 4, 6}}
5 2
1 1
5 1 5
4 3
5 2
3 7 4
1 7
1 4 1
6 2 6 3
4 5
6 6
1 2 3 4
4
3 2 3
2 2 4 1 5
3 4
2 3
{{1, 2, 3, 4}} {{1, 2, 3, 4, 5, 6}} {{1, 2, 3, 4, 5, 6, 7}}
Out[166]= 1 {{2, 3, 5}, {1, 4}} 2 6
2
3
1
3 7 4
5
4
4 1 6
4
3 2 2
5 3
1 5
{{1, 2, 3, 4}} {{1, 4}, {2, 3, 5}}
{{1, 5}, {2, 6}, {3, 4}} {{1, 2, 3, 4, 5, 6, 7}}
5 1 4 3
7
6 2
4 3 1 1
3 2
5
1 4 2 2 1 5
1
6 6 5 6
1 3
1 4 4 3
4 7
2 3 3 5 4 2
3 5
2 4
2
{{1, 2, 3, 4, 5}} {{1, 2, 3, 4, 5, 6}} {{1, 2, 3, 4, 5, 6, 7}}
1 3 7
{{1, 2, 3, 4}} 1 2
3 1
5
2 1 5
6
6
2 4 4 3
4 5
3 4 2
{{1, 4}, {2, 3}}
{{1, 2, 3, 4, 5}} {{1, 2, 3, 4, 5, 6}} {{1, 2, 3, 4, 5, 6, 7}}
4 1 2
2 7 4
4 7
1 6 1
2 6
1 5
6
1 3
5
6 5 6
1 2 3 4 5 2 5
4 3
2
3 4 3
2 3 4 2 1
3 4 6
1
{{1, 2, 3, 4}} {{1, 2, 3, 4, 5, 6}} 5
3
{{1, 2, 5}, {3, 6}, {4, 7}}
1 2 2 4
{{1, 2, 3, 4, 5, 6}} 1
7
1 5 2 6
6 5
3
1
2
5 4
3
3 4 3 4
6
{{1, 4, 6}, {2, 3, 5}}
{{1, 2, 3, 4, 5, 6}} {{1, 2, 5}, {3, 6}, {4, 7}}
{{1, 2, 3, 4}}
Figure 1: The communities in edge betweenness-uniform graphs detected on basis of edge betweenness
Revising the Newman-Girvan Algorithm 203
8 6
8 8 1
5 1 3
1 7 1 7
3 5
7 5 2 9 6
4 2 6 8
1
1
6 2 6 2 6 5 3
8 6 4
7 7 3 9
1 5 7 2
4 3 5 7
3 5 3 5
4 8
2 4 4 2 4
3 2 1
6 7
4
{{1, 3, 6, 8}, {2, 4, 5, 7}} {{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}}
{{1, 3, 5, 7}, {2, 4, 6}} 2 7 8 6 1
5 4
4
1
8 6
7 5
1 5 3
5 7 2
9
3 4 3
6 8
1 2 4
7
3 2
{{1, 3, 5, 7}, {2, 4, 6}} 6
{{1, 6}, {2, 5}, {3, 8}, {4, 7}} {{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}}
4 2
2 3
7
9 5 1
1 6 3 8 1 8
9 6
1 7 4 6 9 9
1 4 2 7 4 2
5
1 2 3 4 5 6 7 8
2 5 7 1 6 5
6 4 5 3 7
8 2
3 6
3 4 7 6 1
3 7 8
5 4 5 3
2 8
{{1, 2, 3, 4, 5, 6, 7}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}}
{{1, 2, 5, 6}, {3, 4, 7, 8}} 4 2
{{1, 2, 6, 7}, {4, 5, 9}, {3, 8}}
2 3
4 5 1
6
9 6
7 1 3 8
8 2 4 2
1 4
5 9
3 7
5
6 5
7 6 {{1, 2, 5, 6}, {3, 4, 7, 8}} 8
3
1 7
{{1, 2, 3, 4, 5, 6, 7}} {{1, 2, 6, 7}, {3, 8}, {4, 5, 9}}
{{1, 2, 3, 4, 5, 6, 7, 8, 9}}
7
7 7 6
2 5 7
5 1 5 3 8
9
6
3 2 1
8 5 6 3
1 5
2 3 1 5
8 1
8 4 9 8 9 8
1 2 3 4 5 6 7 6 2 7
8 9
6 1 6
7 3 6
3 1 4
4 7
3 4 5 4
4 8 2 2 4 2
{{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}} {{2, 4, 7}, {3, 6, 8}, {1, 5, 9}}
Out[35]=
7 7 6
7 8
5 9
5 1 1 3
6 6
5
5 3
2
1 8 9
8 4
6 2
3 1 4 7
4 2
3 4 8 2
{{1, 2, 3, 4, 5, 6, 7, 8, 9}} {{1, 5, 9}, {2, 4, 7}, {3, 6, 8}}
{{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8}}
5 3
6 4 7
3 4 3
6 3 7 4 9 9
2
8 4
5 2 4 3 5 6 6
3
7 7 1
7 2 8
7 5 9 6 3
5 1 3 4 1
2 8 8 7
8 7
1 8
1 6
2
6 2 9 5
1 4 8 1 4 2
6 2 5 1 5 8
{{1, 2, 3, 4, 5, 6, 7, 8}} {{2, 4, 7}, {3, 6, 8}, {1}, {5}} {{1, 5, 6, 8, 9}, {2, 3, 4, 7}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}}
3 4 6 5 3
1
4
2
8
3 9
7
7 6
5 2
1 8
8 8
7 1
6
5 7
6 2 1 3
5 4
9
4 2
{{1, 2, 3, 4, 5, 6, 7, 8}} {{1}, {2, 4, 7}, {3, 6, 8}, {5}} {{1}, {2, 3, 4, 7}, {5, 6, 8, 9}}
{{1, 2, 3, 4, 5, 6, 7, 8, 9}}
3 2 8 7
4
2 9
8 3 3 2
5 3 1 8
6
1 5 9
4 8 5
8
8 4 5 2 7
1 7 6
6 1 2 8 8 9 4
1 6
2
9 7
7 6 7 1 3
6 3 3 6
7
5 2
4 7
3 6 4 4 5
5 1 5 1 2 4
{{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}}
3 2 3 2 8 7
4
6
1 8 5 9
8
4 6
4 5
7 7 6
8 9
6 3 1 3
7
2
5 1
5 1 2 4
{{1, 2, 3, 4, 5, 6, 7, 8, 9}}
{{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8}} {{1, 2, 3, 4, 5, 6, 7, 8, 9}}
Figure 2: The communities in edge betweenness-uniform graphs detected on basis of edge betweenness (continued)
204 J. Coroničová Hurajová, T. Madaras
RevisedNewmanGirvan(G)
Data: a graph G
Result: the hierarchy of nested partitions of V (G)
G0 := G ;
P0 := {V (G)} ;
i := 0 ;
c := 0 ;
while E(Gi ) 6= 0/ do
Si := {B(e) : e ∈ E(Gi )} ;
mx := max Si ;
Mi := {e ∈ E(Gi ) : B(e) = mx} ;
Ebi := Mi ;
ℓi := 1 ;
while |Ebi | > 1 do
ℓi := ℓi + 1;
Uℓi := {B(A) : A ⊂ Mi ∧ |A| = ℓi } ;
gmx := maxUℓi ; Figure 3: The example of a graph where revised Newman-
Ebi := {A ⊂ Mi : |A| = ℓi ∧ B(A) = gmx} ; Girvan algorithm behaves differently than the original one
end or the one of [1]
Gi+1 := Gi \ Ebi ;
if b0 (Gi+1 ) > b0 (Gi ) then [1] is used on the same graph, first, five edges
c := c + 1 ; {8, 11}, {6, 9}, {3, 10}, {3, 9}, {2, 11} are removed at
Pc := {V1 , . . . ,Vrc : once, followed by sequential removals of {3, 12}, {7, 8}
hV1 i, . . . , hVrc i are connected components of Gi+1 } and {8, 12} where the graph splits into two components,
; one of them being the single edge {3, 8}. Therefore,
end we see that the hierarchies of nested partitions produced
i := i + 1 ; by our algorithm and the one of [1] differ already at the
end highest level. In addition, a particular run of the original
return {Pi : i = 0, . . . , c} Newman-Girvan algorithm (using random selection of
an edge from the set of several edges with the same
Algorithm 1: The group edge-centrality based Newman- maximum edge betweenness) on this graph may produce
Girvan algorithm for community detection. yet another hierarchy: if the edge {3, 9} is removed first,
then the edges {3, 12}, {3, 8} and {3, 10} are removed
sequentially, thereby separating the single vertex 3 from
five edges with the maximum edge betweenness, namely the rest of the graph.
{8, 11}, {6, 9}, {3, 10}, {3, 9} and {2, 11}. Now, these five Note also that the existence of unique set of edges which
edges form ten 2-element subsets with group edge be- have to be removed depends heavily also on the edge auto-
tweenness centralities 52 52 52 49 52 49 52 52 52
3 , 3 , 3 , 3 , 3 , 3 , 3 , 16, 3 , 3 , morphism group Aut ∗ of a graph. It is easy to see that, for
and ten 3-element subsets with group edge between- any edge automorphism ϕ of a graph G and any A ⊂ E(G),
ness centralities 26, 25, 25, 74 71 74
3 , 25, 25, 3 , 26, 25, 3 ; we B(A) = B(ϕ(A)) holds; consequently, if Aut ∗ (G) is non-
see that, among these subsets, the uniqueness with trivial and the edge automorphisms do not fix A, then there
respect to the maximum group edge betweenness are several different subsets of edges with the same group
is not preserved. But, for five 4-element sub- edge betweenness as A. Thus the uniqueness of the edge
sets of {{8, 11}, {6, 9}, {3, 10}, {3, 9}, {2, 11}}, the group subset of particular size with the maximal group edge be-
edge betweenness centralities are 97 101 98 97 97
3 , 3 , 3 , 3 , 3 , tweenness cannot be guaranteed for graphs possessing a
thus there is unique 4-element subset – the set lot of symmetries. Some particularly bad examples occur
{{8, 11}, {6, 9}, {3, 10}, {2, 11}} – reaching the maxi- among edge betweenness uniform graphs – in the wheel
mum value 101 3 . Hence, the edges of this 4-element set are W6 , among all sets of edges of cardinality i ≤ 9, there
removed, and the sequence of single edge removals con- are always at least two distinct sets whose group edge be-
tinues with {1, 12}, {6, 7}, {4, 9} after which there are de- tweenness is maximal among all i-sets, hence, the unique
tected two edges ({4, 7} and {1, 7}) with the same highest maximum group edge betweenness set coincides with the
edge betweenness. After they are removed, the edge re- whole edge set of W6 , and the revised Newman-Girvan al-
moval continues with {2, 12} and then with {2, 5} where gorithm breaks the vertex set of W6 into six singletons.
the graph splits, for the first time, into two components Unfortunately, similar issues may appear also in real
with vertex sets {1, 2, 4, 6, 10, 11} and {3, 5, 7, 8, 9, 12}. networks. We illustrate this on the example of the
On the other hand, when the algorithm of network of Zachary karate club [8] shown at Figure 4.
Revising the Newman-Girvan Algorithm 205
is the maximal among all i-subsets. For these graphs, the
hierarchy of communities produced by our revised algo-
rithm collapses into singletons although their trivial auto-
morphism group should prevent easy replication of subsets
of edges with high group edge betweenness. At the mo-
ment, no infinite family of such graphs is known; neverthe-
less, we believe that the candidate graphs might be found
among strongly regular graphs, where are known exam-
ples with trivial vertex automorphism group, and, possibly,
also ones having trivial edge automorphism group.
Figure 4: The Zachary karate club network
References
The standard Newman-Girvan algorithm removes the
[1] Despalatović, L., Vojković, T., Vukičevič: Community struc-
edges with the maximum edge betweenness in the order
ture in networks: Girvan-Newman algorithm improvement.
{32, 1}, {3, 1}, {9, 1}, {34, 14}, {34, 20}, {33, 3}, {31, 2},
MIPRO, Opatija, Croatia, May 26-30, 2014, 997–1002.
{3, 2}, {4, 3} after which two edges with the same max-
[2] Fon-der-Flaass, D.G.: New prolific constructions of strongly
imum edge betweenness are detected, namely {14, 3}
regular graphs. Adv. Geom. 2 (2002) 301—306
and {8, 3}. After their simultaneous removal, the graph
[3] Fortunato, S.: Community detection in graphs.
splits into two components and the sequence of re-
arXiv:0906.0612 [physics.soc-ph]
moved edges continues with {34, 10}, {34, 28}, {10, 3}
[4] Gago, S., Coroničová Hurajová, J., Madaras, T.: Between-
after which again two maximum betweenness edges,
ness centrality in graphs. In: Quantitative graph theory:
{7, 1} and {6, 1}, are detected; their removal yields mathematical foundations and applications (Dehmer, M. and
another pair of edges with the same maximum edge Emmert-Streib, F., eds.), CRC Press, 2015
betweenness, namely {1, 5} and {1, 11}. The se- [5] Girvan, M., Newman, M. E. J.: Community structure in so-
quence of single edge removals continues with edges cial and biological networks. Proc. Natl. Acad. Sci. USA 99
{34, 32}, {33, 32}, {34, 29}, {26, 24}, {28, 24}, {9, 3} fol- (2002) 7821-–7826
lowed by simultaneous removal of {34, 27} and {1, 12}, [6] Coroničová Hurajová, J., Madaras, T.: The edge between-
then by single removals of {30, 27}, {13, 1}, {13, 4}. ness centrality – theory and applications. Journal of innova-
Now here appears the situation when the graph con- tions and applied statistics 5 (1) (2015) 20–29
tains even 10 edges of maximum edge betweenness, [7] https://github.com/szhorvat/IGraphM
namely {34, 23}, {34, 21}, {34, 19}, {34, 16}, {34, 15}, [8] Zachary, W. W.: An information flow model for conflict and
{33, 23}, {33, 21}, {33, 19}, {33, 16} and {33, 15} (which fission in small groups. Journal of Anthropological Research
are all contained in the same star-like connected com- 33 (4) (1977) 452—473
ponent). However, the computation of group edge
betweenness for subsets of this edge set reveals that the
whole set has to be removed as there are always many
proper subsets of smaller sizes having the same maximum
group edge betweenness (this is most likely also caused
by symmetries of that particular connected component).
Hence, for the network of Zachary karate club, the revised
algorithm just confirms that the order of edge removal
as obtained by the version of Newman-Girvan algorithm
from [1] is probably optimal; nevertheless, it would be
interesting to find an example of real network where the
revised algorithm would lead to different sequence of
removed edges, or even a different hierarchy of graph
communities.
An area where the revised Newman-Girvan algorithm
would apply concerns the looking for "null models",
that is, the graphs without community structure (see [3],
pages 90–91). Based on the above considerations, we
propose to take, for such graphs, the ones which are
edge betweenness-uniform, have trivial edge automor-
phism group and, moreover, for each i which is less than
the number of edges, there are always at least two sets con-
sisting of i edges such that their group edge betweenness