In o ma ion Sciences 662 (2024) 120271
A ailable online 5 Feb ua y 2024
0020-0255/© 2024 The Au ho (s). Published by Else ie Inc. This is an open access a icle unde he CC BY license (h p://c ea i ecommons.o g/licenses/by/4.0/).
Con en s lis s a ailable a ScienceDi ec
In o ma ion Sciences
jou nal homepage: www.else ie .com/loca e/ins
A hie a chical o e lapping communi y de ec ion me hod based on
closed ail dis ance and maximal cliques
Pa la D áždilo á∗, Pe P okop, Jan Pla oš, Václa Snášel
Depa men o Compu e Science, VSB -Technical Uni e si y o Os a a, 708 00 Os a a-Po uba, Czech Republic
A R T I C L E I N F O A B S T R A C T
Da ase link: h p://
www -pe sonal .umich .edu /%7Emejn /ne da a/
Da ase link: h ps://anonymous .4open .
science / /g aph _hie a chical _agglome a i e _
clus e ing -C946 /README .md
Keywo ds:
O e lapping communi y de ec ion
Clique pe cola ion
Closed ail dis ance
And hie a chical agglome a i e clus e ing
An impo an ea u e o eal ne wo ks is hei hie a chy and he exis ence o o e lapping
communi ies. Hie a chical agglome a i e clus e ing is one way o de e mine he hie a chy o
a ne wo k. To ensu e he exis ence o o e lapping communi ies, i is app op ia e o choose
he base elemen s o clus e ing – edges, cliques, e c. These base elemen s can hen ha e
common e ices and na u ally p o ide he possibili y o o e lap. The p oposed communi y
de ec ion me hod uses hie a chical agglome a i e clus e ing on he 2-edge-connec ed componen
o he g aph. Communi ies a e cons uc ed om maximal cliques as base elemen s. No el
dissimila i ies o hie a chical agglome a i e clus e ing we e in oduced o he me ging o
cliques. The dissimila i ies use he size o he o e lapped cliques and closed ail dis ance o
exp ess dissimila i y be ween communi ies in ne wo ks. The single linkage app oach con ains
and ex ends he esul s o 𝑘-CPM. The p oposed algo i hm u ilizing de e minis ic dissimila i y
achie es compa able o supe io ou comes compa ed o s anda d algo i hms used o hie a chical
o o e lapping communi y de ec ion.
1. In oduc ion
Using g aph ep esen a ion and ne wo k analysis ools can be beneficial o s udying ela ionships be ween objec s. A gene al
desc ip ion o communi y is a se o diffe en objec s connec ed mo e equen ly among hemsel es in compa ison o he es o he
ne wo k. In case o he possible belonging o objec s o mul iple communi ies, we a e ocusing he e on o e lapping communi ies
[1]. Yang and Lesko ec [2,3] no iced ha he communi y o e laps a e dense. In some eal-wo ld da ase s, while mos clus e ing
algo i hms canno handle such dense o e lapping s uc u es, one e ex may belong o ens o communi ies simul aneously [4].
The ep esen a i e me hod o o e lapping clus e ing is he clique pe cola ion me hod (CPM o 𝑘-CPM) by Palla e al. [5,6]. The
de ec ion o communi ies is ealized ia finding maximal cliques, cons uc ion o a clique g aph wi h maximal cliques as e ices, and
weigh ed edges ep esen ing he size o cliques’ o e lap ha a e bigge han o equal o a specified 𝑘 −1. Communi ies a e connec ed
componen s in he clique g aph whe e de ec ed communi ies may no o m a ne wo k co e . Some algo i hms o o e lapping
communi y de ec ion a e based on clus e ing o mo e complex base elemen s han e ices – edges [7], cliques [8], weak-cliques [9],
e c.
The second poin o iew on algo i hms o communi y de ec ion can be ocused on he hie a chy o communi ies [1]: “Commu-
ni ies a e nes ed wi hin each o he as many imes as he e a e hie a chical le els.” Algo i hms o hie a chical communi y de ec ion
* Co esponding au ho .
E-mail add esses: [email p o ec ed] (P. D áždilo á), [email p o ec ed] (P. P okop), [email p o ec ed] (J. Pla oš), [email p o ec ed] (V. Snášel).
h ps://doi.o g/10.1016/j.ins.2024.120271
Recei ed 31 July 2023; Recei ed in e ised o m 30 Janua y 2024; Accep ed 30 Janua y 2024
In o ma ion Sciences 662 (2024) 120271
2
P. D áždilo á, P. P okop, J. Pla oš e al.
Table 1
No a ion used in he pape .
Symbol Desc ip ion
𝑉(𝐺)Se o e ices o g aph 𝐺
𝐸(𝐺)Se o edges o g aph 𝐺
𝑛,𝑚Numbe o e ices and edges o g aph
𝑑𝑒𝑔(𝑢)Deg ee o e ex 𝑢
⟨𝑑𝑒𝑔⟩A e age deg ee o e ices
𝐻𝐴𝐶 Hie a chical agglome a i e clus e ing
𝐺𝐻𝐴𝐶 G aph hie a chical agglome a i e clus e ing
𝑆𝐿,𝐶𝐿,𝐴𝐿 Single, comple e and a e age linkage app oach
𝐴,𝐴𝑖𝑗 Adjacency ma ix; one elemen om adjacency ma ix
𝑄,𝑄𝑘Clique and clique wi h 𝑘 e ices
𝑆𝑃(𝑥𝑖,𝑥
𝑗)The sho es pa h be ween e ices 𝑥𝑖, 𝑥𝑗
𝐶𝑇(𝑥𝑖,𝑥
𝑗),𝐶𝑇(𝑢, 𝑣, 𝑤, 𝑢)The sho es closed ail con aining e ices 𝑥𝑖, 𝑥𝑗; closed ail om 𝑢
ia 𝑣and 𝑤 o 𝑢
𝐶𝑖𝑖- h communi y
|𝐶𝑖|Size o 𝑖- h communi y
𝑑𝑆𝑃 ,𝑑𝐶𝑇 Sho es pa h and closed ail dis ance
𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 ,𝑑𝐶𝐿
𝐺𝐻𝐴𝐶 ,𝑑𝐴𝐿
𝐺𝐻𝐴𝐶 G aph hie a chical agglome a i e clus e ing dissimila i y wi h single,
comple e, and a e age linkage app oach
𝑁(𝑢),𝑁+(𝑢)𝑁(𝑢) ={𝑣 ∈𝑉(𝐺); 𝑑𝑆𝑃 (𝑢, 𝑣) =1},
𝑁+(𝑢) ={𝑣 ∈𝑉(𝐺); 𝑑𝑆𝑃 (𝑢, 𝑣) ≤1}
𝜆Le el o cu in dend og am
a e o en based on hie a chical agglome a i e clus e ing (HAC). Ahn e al. [7]used a single linkage app oach wi h Jacca d simila i y,
Shen e al. [10] agglome a e communi ies wi h he maximum simila i y, and Blondel e al. [11]used he hie a chical app oach based
on modula i y op imiza ion. Ano he agglome a i e me hod uses node influence and he simila i y o nodes o de ec non-o e lapping
communi ies [12]. Al e na i ely, di isi e clus e ing is used in [13]in he o m o a ecu si e pa i ioning algo i hm, s a ing wi h a
single communi y and sepa a ing he nodes in o wo communi ies by spec al clus e ing epea edly.
The main mo i a ion o de eloping a new communi y de ec ion me hod was o combine he sea ch o o e lapped communi ies
and he c ea ion o hei hie a chical s uc u e. HAC is a commonly used p ocedu e o de ec ing o e lapping communi ies when
he cliques a e used as bases, e.g. EAGLE [10]. In his cu en wo k, we a e in oducing a no el dissimila i y o he HAC based on
he s uc u al closeness o cliques and hei neighbo hood in a g aph. We designed new dissimila i ies be ween communi ies ha
a e de e minis ic and we used he closed ail dis ance be ween g aph nodes and he size o communi ies ha o e lap. Closed ail
dis ance (𝐶𝑇-dis ance) be ween e ices 𝑢, 𝑣in he unweigh ed, undi ec ed, connec ed g aph wi hou b idges (2-edge-connec ed) is
defined in he a icle [14]as he leng h o he sho es closed ail ha con ains e ices 𝑢, 𝑣(Table 1). The ex ension o 𝐶𝑇-dis ance
o undi ec ed and weigh ed g aphs was also lis ed in a icle [14]. The p ocessing s eps in he p oposed communi y de ec ion me hod
a e indica ed in he g aphical abs ac . The 𝐶𝑇-dis ance ma ix among pai s o e ices is calcula ed o he use in dissimila i ies
in he p oposed algo i hm. All maximal cliques a e de ec ed in he sou ce ne wo k and a e used as bases in he HAC. The p oposed
dissimila i ies se e o he agglome a ion o bases and he c ea ion o a hie a chy (dend og am). The alue o modula i y o each
possible le el is moni o ed. The bes alue o modula i y indica es he le el o cu in he hie a chy. This esul ep esen s he ne wo k
co e .
We would like o highligh he main con ibu ion o his pape as ollows:
•A hie a chical o e lapping communi y de ec ion me hod was p oposed. The p oposed me hod uses he HAC and maximal cliques
as base elemen s o clus e ing.
•The ela ion be ween he well-known 𝑘-CPM and he p oposed me hod was discussed. Due o he ex ended hie a chy, he
p oposed me hod allows he de ec ion o be e communi ies han he 𝑘-CPM.
•The p oposed me hod is no ocused on efficien compu a ion o la ge g aphs. Ins ead, i uses maximal cliques as building blocks.
The dissimila i ies a e based on 𝐶𝑇-dis ance and he size o cliques in he o e lap which allows he s udy o he hie a chical
s uc u e o communi ies in he ne wo k.
•Resul ing o e lapping communi y s uc u e depends on he sequen ial (g eedy) me ging o all maximal cliques and he al eady-
ound communi ies.
This a icle is o ganized as ollows. Sec ion 2in oduces he ela ed wo k o communi y de ec ion om hie a chical and ag-
glome a i e pe spec i es. Sec ion 3is ocused on he ela ion be ween he CPM and HAC used o communi y de ec ion wi h a single
linkage app oach. The sec ion desc ibes ou mo i a ion behind he p oposed me hod. Sec ion 4p esen s he algo i hm o communi y
In o ma ion Sciences 662 (2024) 120271
3
P. D áždilo á, P. P okop, J. Pla oš e al.
de ec ion and dissimila i ies be ween clus e s o e ices based on he 𝐶𝑇-dis ance be ween e ices ha a e no in he in e sec ion
o clus e s and akes in o accoun he size o his in e sec ion. The applied idea o clus e ing o mo e complex base elemen s han
e ices – maximal cliques – enables he o e lap be ween communi ies. Sec ion 5con ains he expe imen s demons a ing he se-
lec ion o cu s in he dend og am whe e he hie a chy o communi ies o he p oposed me hod is shown in a eal-wo ld ne wo k.
The empi ical e alua ion o he me hod is also included and he esul s a e compa ed wi h he selec ed well-known me hods. The
ad an ages o he p oposed me hods and u u e wo k a e discussed in he conclusion in sec ion 6.
2. Rela ed wo k
The e a e cu en ly many me hods ha pe o m hie a chical communi y de ec ion. Some me hods a e algo i hmically hie a chical
[10,11]and c ea e a hie a chy as a esul o he applied algo i hm. Ano he class o me hods in ol es fi ing a hie a chical model o
he analyzed ne wo k. Schaub e al. [15] in oduced a defini ion o hie a chy based on he concep o s ochas ic ex e nally equi able
pa i ions and hei ela ion o p obabilis ic models, such as he s ochas ic block model. They ocused on an agglome a i e p ocedu e
ha elies on accu a ely de ec ing he fines le el in he hie a chy.
The esul o HAC is ep esen ed by he p oximi y dend og am [16] which is a ee-like s uc u e whe e each node ep esen s a
clus e o a da a poin , and he b anches show he me ging o clus e s du ing he clus e ing p ocess.
The na u al o e lap can be cons uc ed by pa i ioning links [7]ins ead o nodes. A node in he o iginal g aph is called o e lapping
i he links connec ed o i a e pu in mo e han one clus e . The au ho s use HAC wi h he SL app oach and he simila i y be ween
links o build a dend og am whe e each lea is a link om he o iginal ne wo k and he b anches ep esen clus e s o he links.
A diffe en app oach o communi y de ec ion is applied in [17,5]. The au ho s de eloped he 𝑘-clique pe cola ion me hod (𝑘-
CPM) o communi y de ec ion. The communi y is c ea ed om 𝑘-cliques (𝑄𝑘) ha a e eached only om he 𝑘-cliques o he same
communi y h ough a se ies o adjacen 𝑘-cliques. Two 𝑘-cliques a e adjacen i hey sha e 𝑘 −1 e ices.
The ex ension o he CPM o he weigh ed ne wo k was p oposed in [8]as CPMw. The au ho s in oduced a module iden ifica ion
echnique o weigh ed ne wo ks based on 𝑘-cliques ha ing a subg aph in ensi y highe han a ce ain h eshold and allowing sha ed
nodes (o e laps) be ween modules.
A Sequen ial Clique Pe cola ion (SCP) algo i hm [18]was p oposed o as clique pe cola ion de ec ing 𝑘-clique communi ies in
a ne wo k by sequen ially inse ing i s edges and keeping ack o he eme ging communi y s uc u e. This algo i hm has specifically
been designed o (dense) weigh ed ne wo ks, whe e weigh -based h esholding o ei he he links o he cliques o med by hem
is necessa y o ob aining meaning ul in o ma ion on he s uc u e. Reid e al. [19] analyzed SCP and s a ed: “Howe e , hese
imp o ed me hods o en pe o m poo ly on ne wo ks wi h he kind o pe asi ely o e lapping communi y s uc u e we see in many
eal wo lds social ne wo ks – an a ea o inc easing in e es in he applied s udy o communi y s uc u e – and pa icula ly poo ly
when pe o ming pe cola ion wi h high alues o 𝑘.”
The au ho s in [20] p oposed he clique-based Lou ain algo i hm ha classifies he non-classified node ob ained a e finding
cliques in one o he communi ies by applying he Lou ain algo i hm.
One o he fi s algo i hms o he de ec ion o he o e lapping and hie a chical communi y s uc u e in complex ne wo ks is
desc ibed in [21]. The me hod is based on he local op imiza ion o a fi ness unc ion ( a io o he in e nal deg ee o he o al deg ee
o a module). The me hod co esponds o a so o g eedy op imiza ion o he fi ness unc ion. I c ea es na u al communi ies a ound
e ices and he esul is e ices’ co e , i.e., i depends on he esolu ion pa ame e o scale.
Algo i hm EAGLE [10] de ec s o e lapping and hie a chical communi y s uc u es in ne wo ks wi h a hie a chical agglome a i e
me hod. The simila i y be ween communi ies is based on modula i y and he maximal cliques a e i s base elemen s. This app oach
confi ms ha HAC is applicable o he hie a chy de ec ion among communi ies, and maximal cliques (as base elemen s) ensu e he
o e lap o communi ies.
Maximal cliques a e used in [22]. This pape p oposes a Maximal Clique-based Mul iobjec i e E olu iona y Algo i hm (MCMOEA)
o o e lapping communi y de ec ion. The ep esen a ion scheme is based on he maximal clique and he algo i hm can p o ide
hie a chical pa i ions o he gi en ne wo k.
A DOCNA [23]is an algo i hm o de ec ing o e lapping communi ies in ne wo ks based on maximal cliques whe e an imp o ed
e sion o he B on-Ke bosch Algo i hm is adop ed.
The eques o maximal cliques is qui e es ic i e. The e o e, in [9] hey used weak cliques as he base elemen s. The au ho s
p oposed a weak-CPM o o e lapping communi y de ec ion in a la ge-scale ne wo k.
The g eedy coupled-seeds expansion me hod [24] o he o e lapping communi y de ec ion used a fi ness unc ion ha is based
on he size o a common neighbo o wo e ices – simila o a weak clique pe cola ion.
The au ho s in [25] p opose an algo i hm MOKP ha uses 𝑘-plexes o gene a e communi y seeds om he whole ne wo k and
assigns he emaining nodes by modula i y op imiza ion. This algo i hm does no de ec o e lapping communi ies.
To iden i y he o e lapping communi y s uc u e, he au ho s in [26] cons uc ed a maximal clique ne wo k om he o iginal
ne wo k, and p o ed ha he op imiza ion o hei me ic on he o iginal ne wo k is equi alen o he op imiza ion o Newman’s
modula i y on he maximal clique ne wo k.
A use ul app oach o o e lapping communi y de ec ion is based on Nonnega i e Ma ix Fac o iza ion (NMF). Yang and Lesko ec
[27]used he NMF app oach o find he o e lapping communi ies in la ge-scale ne wo ks, Wang e al. [28] p oposed he Modula -
ized Nonnega i e Ma ix Fac o iza ion (MNMF) model o inco po a e he communi y s uc u e in o ne wo k embedding, and Ye e
al. [29] p oposed a model called Deep Au oencode -like NMF (DANMF) o communi y de ec ion, inspi ed by he unique ea u e
ep esen a ion lea ning capabili y o he deep au oencode .
In o ma ion Sciences 662 (2024) 120271
4
P. D áždilo á, P. P okop, J. Pla oš e al.
The o e iew o communi y de ec ion me hods wi h hie a chical agglome a i e clus e ing o o e lapping communi y de ec ion
can be ound in [21,30,31,1,32]. The su ey o communi y de ec ion using nonnega i e ma ix ac o iza ion (NMF) is in [33]. The
comp ehensi e su ey o communi y de ec ion ocused on deep lea ning is men ioned in [34].
The e alua ion o he app op ia eness o he de ec ed communi y s uc u e is a e y impo an pa o communi y analysis.
Me ics ela ed o all he classes o communi y s uc u es (disjoin , o e lapping, local, hie a chical, e c.) a e p esen ed in a su ey
[35]o he s a e-o - he-a me ics used o he de ec ion and e alua ion o communi y s uc u e in ne wo ks. The a icle [36] ocuses
on he quali y o communi y s uc u e and con ains a b oad o e iew and classifica ion o me hods o he e alua ion o de ec ed
communi ies.
The esul o HAC is a dend og am ha ep esen s he hie a chical s uc u e o communi ies. The de e mina ion o he dend o-
g am’s cu le el is a c ucial aspec ha plays a pi o al ole in unco e ing an op imal communi y s uc u e. To assess he efficacy o
he communi y s uc u e de i ed h ough HAC, he modula i y me ic se es as a aluable ool o e alua ion. One o he modula -
i ies o o e lapped communi ies can be ound in [10]. This wo k in oduces a belonging coefficien . The belonging coefficien o a
node 𝑖 o a gi en communi y is edefined as he numbe o communi ies 𝑂𝑖 o which i belongs.
3. Rela ion be ween HAC and clique pe cola ion
We would like o discuss a gene aliza ion o CPM o HAC. This gene aliza ion leads us o he heo e ical g ounding o he
p oposed dissimila i ies. The idea abou he clique’s hie a chy de ec ed by hie a chical clus e ing was s a ed in [37]. The au ho s
used a co-clique ma ix as an inpu o hie a chical clus e ing. This co-clique ma ix co esponds o he adjacency ma ix o he
weigh ed g aph o o e lapped maximal cliques.
As a as complexi y is conce ned, he CPM was designed o selec ed 𝑘, e y o en 𝑘 =3[17]. De enyi e al. in [17]and Yuan e
al. in [38]use o 𝑘-clique g aph a diffe en e minology and hey named i as, “𝑘-clique adjacency g aph.”
The s anda d 𝑘-CPM [17] can be desc ibed ia a 𝑘-clique g aph as ollows:
1. De ec 𝑘-cliques in he sou ce ne wo k and c ea e a 𝑘-clique g aph, whe e e ices a e 𝑘-cliques and he edges exis be ween
𝑘-cliques which ha e (𝑘 −1) e ices in he o e lap in he sou ce ne wo k.
2. Find he connec ed componen s in he clique g aph. These connec ed componen s in he clique g aph co espond o communi ies
in he sou ce ne wo k.
An effec i e algo i hm based on maximal cliques in 𝑘-CPM [19]builds a minimal spanning o es o e he maximal cliques,
using a simple da a s uc u e o educe unnecessa y clique in e sec ion es s. The Yuan e al. aim in [38] o find he denses clique
pe cola ion communi y which con ains a gi en se o que y nodes. They use a maximal clique adjacency g aph and a maximal clique
adjacency spanning ee wi h he maximum o al weigh o edges whe e he weigh o he edge in he maximal clique adjacency
g aph is equal o he size o o e lap be ween maximal cliques in he sou ce g aph.
Gene alized CPM inspi ed by he a icle [38] in oduces a connec ion be ween CPM and g aph hie a chical clus e ing wi h a
single linkage app oach:
1. De ec maximal cliques in he sou ce ne wo k and c ea e a weigh ed maximal clique g aph. The weigh s o edges in he maximal
clique g aph co espond o he size o he o e lap be ween maximal cliques in he sou ce ne wo k.
2. Use he HAC wi h he SL app oach on he maximal cliques o he c ea ion o a dend og am. The weigh o an edge is he
simila i y be ween e ices in he maximal clique g aph.
3. Fo a specified 𝑘, ob ain a le el o cu in he dend og am ha ep esen s he same esul as in he s anda d 𝑘-CPM. Clus e s om
he dend og am a e he connec ed componen s in he maximal clique g aph wi h he edge’s weigh bigge o equal o 𝑘 −1.
These ep esen o e lapped communi ies in he sou ce ne wo k. The minimal weigh in he maximal clique g aph equals 1 o
𝑘 =2and in his si ua ion, all e ices o he connec ed sou ce g aph a e in one communi y.
3.1. F om 𝑘-CPM o a no el dissimila i y o GHAC
The o ma ion o communi ies in he CPM can be na u ally desc ibed wi h he SL app oach (minimal dis ance o maximal
simila i y be ween wo elemen s which a e in diffe en clus e s) in a hie a chical agglome a i e clus e ing on he g aph (GHAC). The
size o he o e lap o he maximal cliques de e mines he deg ee o simila i y and hus allows he hie a chiza ion o he ob ained
communi ies wi h an o e lap g ea e o equal o wo. The o he condi ion is me ging he adjacen cliques, he e o e he 𝐶𝑇-dis ance
be ween a pai o nodes ( he leng h o he sho es closed ail con aining a pai o nodes) is he smalles . Fu he ex ension o his
hie a chy can be achie ed by in oducing a new dissimila i y based on a 𝐶𝑇-dis ance.
A fi s , we define he dissimila i y be ween he subg aphs 𝐶𝑖and 𝐶𝑗based on he 𝐶𝑇-dis ance and he SL app oach in he GHAC:
𝑑𝑆𝐿
𝐶𝑇 (𝐶𝑖,𝐶
𝑗)=𝑚𝑖𝑛(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣
𝑗).
The nex heo em shows he connec ion be ween he p oposed dissimila i y and he pe cola ion o he wo adjacen cliques in he
CPM.
In o ma ion Sciences 662 (2024) 120271
5
P. D áždilo á, P. P okop, J. Pla oš e al.
Fig. 1. Dissimila i y SL GHAC be ween communi ies depends di ec ly p opo ional o 𝐶𝑇-dis ance o e ices ou o o e lap (in diffe en communi ies) and is in e sely
p opo ional o he size o o e lap.
Theo em 1. The dissimila i y 𝑑𝑆𝐿
𝐶𝑇 (𝑄, 𝑄′)be ween he wo adjacen 𝑘-cliques in g aph 𝐺wi h 𝑘 ≥3based on he CT-dis ance and he SL
app oach equal o 3o 4.
P oo . Le 𝑄, 𝑄′be wo adjacen 𝑘-cliques and 𝑁(𝑢) ={𝑣 ∈𝑉(𝐺); 𝑑𝑆𝑃 (𝑢, 𝑣) =1}is a neighbo hood o a e ex 𝑢. Two 𝑘-cliques a e
adjacen i hey sha e 𝑘 −1 e ices [5]. The amalgama ion (gluing) o he wo cliques ha sha e 𝑘 −1 e ices o 𝑘 ≥3c ea e a
4 −𝐶𝑇 componen [39] because o all 𝑢 ∈𝑄and o all 𝑢′∈𝑄′, he ollowing si ua ions may occu :
•𝑢, 𝑢′∈𝑄 ∩𝑄′and (𝑢 =𝑢′) ⇒𝑑𝐶𝑇 (𝑢, 𝑢′) =0,
•𝑢, 𝑢′∈𝑄 ∩𝑄′and 𝑢 ≠𝑢′⇒∃𝑣 ∈𝑄 ∩𝑄′such ha 𝑣 ∈𝑁(𝑢)and 𝑣 ∈𝑁(𝑢′)⇒|𝐶𝑇(𝑢, 𝑣, 𝑢′, 𝑢)| =3 =𝑑𝐶𝑇 (𝑢, 𝑢′),
•𝑢, 𝑢′∉𝑄 ∩𝑄′and 𝑢′∉𝑁(𝑢)⇒∃𝑣, 𝑤 ∈𝑄 ∩𝑄′such ha 𝑣, 𝑤 ∈𝑁(𝑢)and 𝑣, 𝑤 ∈𝑁(𝑢′)⇒|𝐶𝑇(𝑢, 𝑣, 𝑢′, 𝑤, 𝑢)| =4 =𝑑𝐶𝑇 (𝑢, 𝑢′),
•𝑢, 𝑢′∉𝑄 ∩𝑄′and 𝑢′∈𝑁(𝑢)⇒∃𝑣 ∈𝑄 ∩𝑄′such ha 𝑣 ∈𝑁(𝑢)and 𝑣 ∈𝑁(𝑢′)⇒|𝐶𝑇(𝑢, 𝑣, 𝑢′, 𝑢)| =3 =𝑑𝐶𝑇 (𝑢, 𝑢′).□
The abo e desc ip ion o dissimila i y (𝑑𝑆𝐿
𝐶𝑇 ) does no dis inguish be ween he smalle and he bigge o e lap o cliques. The
modifica ion o he dissimila i y ha inco po a es he size o o e lap be e desc ibes he ela ion be ween he o e lapping cliques
and he o ma ion o hie a chical s uc u e de ec ed communi ies.
The size o o e lap be ween communi ies 𝐶𝑖and 𝐶𝑗is defined as he numbe o e ices in he maximal sha ed clique o
communi ies 𝐶𝑖, 𝐶𝑗. I is a diffe en defini ion han ha in [6], whe e he size o o e lap is defined as he numbe o sha ed nodes
in 𝐶𝑖and 𝐶𝑗.
The newly p oposed dissimila i y 𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 (𝐶𝑖, 𝐶𝑗)be ween communi ies 𝐶𝑖and 𝐶𝑗is di ec ly p opo ional o he node dis ance
(𝐶𝑇-dis ance) ou side o he o e lap o 𝐶𝑖and 𝐶𝑗, in e sely p opo ional o o e lap size, uses he SL app oach, and hen cap u es
he hie a chy o he de ec ed communi ies as well as he hie a chy o he pe cola ed cliques:
𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 (𝐶𝑖,𝐶
𝑗)=
𝑚𝑖𝑛(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣
𝑗)
1+𝑎𝑟𝑔𝑚𝑎𝑥𝑄∈𝐶𝑖∩𝐶𝑗|𝑄|.
The SL app oach o GHAC and he inco po a ion o he size o he o e lap on base elemen s (cliques) ensu es ha he cliques
wi h he bigges o e lap a e amalgama ed a fi s – hey ha e he smalles dissimila i y.
Fig. 1shows he diffe en si ua ions o wo communi ies (cliques 𝐶𝑖, 𝐶𝑗) ha diffe in he size o he o e lap.
The maximal o e lapping cliques in Fig. 1a a e edges (𝑣𝑖, 𝑤), (𝑣𝑗, 𝑤)wi h a common e ex 𝑤. Fig. 1b ep esen s he si ua ion ou
o he clique pe cola ion bu wi h wo 4-cliques wi h an o e lap. Figs. 1c and 1d co espond o he 3-clique pe cola ion ( he size o
o e lap equal o 2) and he 4-clique pe cola ion ( he size o o e lap equal o 3). Fig. 1e co esponds o he 6-cliques amalgama ion
wi h a size o he o e lap equal o 3and he dense neighbo hood (𝑑𝐶𝑇 (𝑣𝑖, 𝑣𝑗) =3).
The 𝑘-CPM uses only he in o ma ion abou he size o he o e lap o he wo adjacen 𝑘-cliques. This size is equal o (𝑘 −1).
The 𝐶𝑇-dis ance be ween e ices in he adjacen clique ( ha a e no in o e lap) is mos ly equal o 4. These wo aspec s o he
sugges ed dissimila i y, yield iden ical ou comes o he clique pe cola ion. Howe e , in dense ne wo k egions ( e e o Fig. 1e),
he 𝐶𝑇-dis ance can be educed o 3(Theo em 1). In such cases, he p oposed dissimila i y employing he SL app oach cap u es
addi ional in o ma ion ega ding he ne wo k’s densi y a he in e sec ion o he wo cliques. This dissimila i y shows o be mo e
accu a e in ex emely dense pa s o he ne wo k han he CPM does. The HAC wi h he p oposed dissimila i y finds a hie a chical
s uc u e o e he communi ies de ec ed by CPM wi h an a bi a y 𝑘. The usage o 𝐶𝑇-dis ance in he p oposed dissimila i y eflec s
he ela ion, no only among cliques, bu also o he no -so-dense communi ies.
4. Hie a chical clus e ing based on 𝑪𝑻-dis ance
In his a icle, we p opose new 𝐶𝑇-dis ance based dissimila i ies o hie a chical agglome a i e clus e ing on g aphs. We ha e
o malized he basic idea o ou me hod as an ex ension o gene alized CPM om he p e ious sec ion. The idea o he use o no el
dissimila i y 𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 wi h GHAC ( he e o e SL GHAC) and he specifica ion o he le el o cu in he dend og am can be summa ized
as a sequence o p ocessing s eps:
1. De ec he maximal cliques as base elemen s in he sou ce ne wo k.
2. Calcula e he 𝐶𝑇-dis ance among e ices in he sou ce ne wo k.
3. Use he SL GHAC o clus e cons uc ion.

In o ma ion Sciences 662 (2024) 120271
6
P. D áždilo á, P. P okop, J. Pla oš e al.
4. The lowe pa o a esul ing dend og am mos ly co esponds o he dend og am in gene alized CPM. Then, he hie a chy
con inues and connec s he communi ies wi h he size o he o e lap ( he size o he bigges common clique) equal o one.
5. Use e alua ion o quali y o communi y de ec ion o de e mine he bes le el o cu in he dend og am o speci y he numbe
o communi ies om he dend og am.
The SL GHAC a he cu le el wi h a alue equal o 4∕𝑘co esponds o he esul o he 𝑘-CPM. I is a consequen o he Theo em 1
whe e 𝑑𝑆𝐿
𝐶𝑇 (𝑄, 𝑄′) o adjacen cliques is mos ly equal o ou and, in an ex emely dense pa o he ne wo k, can be equal o h ee.
The si ua ion wi h 𝑑𝑆𝐿
𝐶𝑇 (𝑄, 𝑄′) =3is inco po a ed in o he le el o he cu wi h he alue 𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 (𝑄, 𝑄′) =4∕(1 +(𝑘 −1)), whe e
(𝑘 −1)is he size o he o e lap be ween he wo cliques.
The SL GHAC amewo k will be u he ex ended in he ollowing subsec ion. The in oduc ion o o he dissimila i ies will modi y
he idea o he pe cola ion o adjacen cliques when he single linkage app oach is used.
4.1. Addi ional dissimila i ies o he GHAC based on he 𝐶𝑇-dis ance
The s anda d linkage me hods o he HAC [40]ha e diffe en p ope ies. The SL HAC ends o p oduce unbalanced and s aggly
clus e s (chaining), especially in la ge da a se s. I does no ake in o accoun he clus e s uc u e. The CL HAC ends o find compac
clus e s wi h equal diame e s (maximum dis ance be ween objec s). I does no ake in o accoun he clus e s uc u e. The AL HAC
ends o join clus e s wi h small a iances and akes in o accoun he clus e s uc u e.
The e alua ion o he o he HAC me hods [41]shows ha mo e success ul me hods han he SL a e CL, AL, o Wa d’s me hods.
Ou expe imen s empowe he GHAC wi h mul iple dissimila i ies based on he 𝐶𝑇-dis ance, and he size o o e lap. Apa om
he SL, we ha e defined he app oaches based on he CL and he AL as:
𝑑𝐶𝐿
𝐺𝐻𝐴𝐶 (𝐶𝑖,𝐶
𝑗)=
𝑚𝑎𝑥(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣
𝑗)
1+𝑎𝑟𝑔𝑚𝑎𝑥𝑄∈𝐶𝑖∩𝐶𝑗|𝑄|,
and
𝑑𝐴𝐿
𝐺𝐻𝐴𝐶 (𝐶𝑖,𝐶
𝑗)= ∑(𝑣𝑖∈𝐶𝑖⧵𝐶𝑗),(𝑣𝑗∈𝐶𝑗⧵𝐶𝑖)𝑑𝐶𝑇 (𝑣𝑖,𝑣
𝑗)
|(𝐶𝑖∪𝐶𝑗)⧵(𝐶𝑗∩𝐶𝑖)|(1 + 𝑎𝑟𝑔𝑚𝑎𝑥𝑄∈𝐶𝑖∩𝐶𝑗|𝑄|).
Fo he cu en wo k, we ha e deno ed he use o he GHAC me hod wi h dissimila i y 𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 as SL GHAC. The o he ma kings
o AL GHAC and CL GHAC a e applied as well.
4.2. Communi y de ec ion compu a ion p ocedu e
The p oposed communi y de ec ion me hods as GHAC amewo k a e summa ized in compu a ion s eps in Algo i hm 1. The
p oposed me hods diffe in he used dissimila i ies.
Algo i hm 1: P oposed communi y de ec ion me hod based on he GHAC and dissimila i y le e aging 𝐶𝑇-dis ance.
Inpu :The bigges connec ed componen o a ne wo k wi hou b idges
Ou pu :Ne wo k co e
S ep 1: Calcula e 𝐶𝑇-dis ance ma ix among e ices in a inpu g aph.
S ep 2: Find maximal cliques (B on-Ke bosch alg.).
S ep 3: G aph hie a chical agglome a i e clus e ing:
S ep 3.1: Agglome a e communi ies acco ding o p oposed dissimila i y wi h maximal cliques as base elemen s.
S ep 3.2: Map me ged clus e s o base elemen s o sou ce g aph e ices.
S ep 3.3: E alua e he s uc u al quali y o ne wo k co e by modula i y.
S ep 3.4: Repea he algo i hm om S ep 3.1 un il all he clus e s a e me ged.
S ep 4: Choose he bes le el o a cu o a dend og am.
Suu balle’s algo i hm [42]is used o calcula e he 𝐶𝑇-dis ances among e ices. The 𝐶𝑇-dis ances a e one pa o used dissimi-
la i ies in he GHAC. Ano he pa o dissimila i ies akes he size o he o e lap in o accoun .
The Maximal cliques a e used as bases in he GHAC and he me ged clus e s o maximal cliques a e mapped o e ices wi h a
ew pos -p ocessing s eps. Fi s ly, he non-agglome a ed bases o size 2 (edges) a e no conside ed in he final communi ies and hey
a e fil e ed ou . The e ices, ha a e no pa o any communi y, a e added as sepa a e communi ies. These pos -p ocessing s eps
allow us o compa e he ne wo k co e o he diffe en communi y de ec ion me hods wi h espec o he need o some modula i y
measu e o con ain all e ices.
The modula i ies o he o e lapping ne wo k co e s a e used as quali y e alua ion c i e ia o he selec ion o he le el o he cu
in a dend og am.
In o ma ion Sciences 662 (2024) 120271
7
P. D áždilo á, P. P okop, J. Pla oš e al.
Table 2
Cha ac e is ics o he gian connec ed componen o ne wo k used in expe imen s. Numbe o nodes (𝑛), numbe o edges (𝑚), densi y
(𝑑𝑒𝑛𝑠), clus e ing coefficien (𝐶𝐶), a e age deg ee (⟨𝑑𝑒𝑔⟩), maximal deg ee (𝑑𝑒𝑔𝑚𝑎𝑥), sho es pa h dis ance diame e (𝑑𝑖𝑎𝑚𝑆𝑃 ), closed
ail dis ance diame e (𝑑𝑖𝑎𝑚𝐶𝑇 ), and numbe o maximal cliques (#𝑐𝑙𝑖𝑞𝑢𝑒𝑠).
Ne wo k 𝑛𝑚 𝑑𝑒𝑛𝑠𝐶𝐶⟨𝑑𝑒𝑔⟩𝑑𝑒𝑔𝑚𝑎𝑥 𝑑𝑖𝑎𝑚𝑆𝑃 𝑑𝑖𝑎𝑚𝐶𝑇 #𝑐𝑙𝑖𝑞𝑢𝑒𝑠
Zacha y’s ka a e club 33 77 0.15 0.26 4.7 17 5 11 35
Ame ican college oo ball 115 613 0.09 0.41 10.7 12 4 8 281
Coau ho ships in ne wo k science 340 865 0.015 0.45 5.1 32 16 39 169
High-ene gy heo y collabo a ions 4557 12399 0.001 0.30 5.4 50 16 41 3976
The implemen a ion o he GHAC me hod is w i en in Py hon 3.11. The agglome a ion me hod is e-implemen ed o he p oposed
dissimila i ies calcula ion. The commonly used lib a ies a e used o he g aph- ela ed ope a ions.1
5. Expe imen s
The sugges ed communi y de ec ion me hods a e compa ed o o he known me hods o e he selec ion o eal-wo ld ne wo ks.
Acco ding o he 𝐶𝑇-dis ance defini ion equi emen , only he gian connec ed componen o each ne wo k a e b idge emo al was
used in he expe imen s. A summa y o he p e-p ocessed ne wo ks is gi en in Table 2.
The p oposed communi y de ec ion me hods based on he SL (CL, AL) GHAC offe se e al diffe en le els o dend og am cu o
p o ide communi y de ec ion esul s. The e is a need o e alua e he quali y o he de ec ed communi ies in agglome a i e s uc u es
o selec he bes cu in he dend og am. Modula i y can be used o ha , which explains he eason o he EAGLE algo i hm o
employ i [10]. To ensu e he co esponding modula i y e alua ion o he de ec ed componen s o a ious communi y de ec ion
me hods and he modula i y measu es used in his pape , e e y node has o be assigned o a leas one communi y; hence, a node
no assigned o any communi y is ea ed as a communi y o a single node.
5.1. Quali y e alua ion o o e lapping communi ies
Th ee diffe en defini ions o modula i y [10,43,44] o o e lapping communi ies a e applied in he agglome a i e p ocess o
he GHAC me hod o de e mine he bes ne wo k co e when using he p oposed communi y de ec ion me hod. The ex ensions o
modula i y o o e lapping communi ies a e based on he adi ional Newman app oach in [45].
Shen’s modula i y ex ension [10] o o e lapping communi ies conside s e ex membe ship in mul iple communi ies. I is di ec ly
equi alen o Newman’s modula i y when e ices belong o jus one communi y. This is defined as ollows:
𝑀𝑒=1
2𝑚
𝑐
∑
𝑘=1 ∑
𝑖,𝑗∈𝐶𝑘
1
𝑂𝑖𝑂𝑗[𝐴𝑖𝑗 −𝑑𝑒𝑔(𝑖)𝑑𝑒𝑔(𝑗)
2𝑚],
whe e 𝑂𝑣is he numbe o communi ies o which e ex 𝑣belongs, 𝑐is he numbe o communi ies.
The o he measu e o quan i ying clus e s uc u es in g aphs was in oduced by Laza in [43]. I is based on wo assump ions:
one, he edges o a node should be p ima ily inside he communi y, and wo, he clus e s (communi ies) should be dense. The
measu e is defined as:
𝑀𝑜𝑣 =1
𝑐
𝑐
∑
𝑘=1 ⎛⎜⎜⎝∑
𝑖∈𝐶𝑘
∑𝑗∈𝐶𝑘,𝑖≠𝑗𝑎𝑖𝑗 −∑𝑗∉𝐶𝑘𝑎𝑖𝑗
𝑑𝑒𝑔(𝑖)𝑂𝑖
𝑛𝑒
𝐶𝑘
|𝐶𝑘|(|𝐶𝑘|
2)⎞⎟⎟⎠
,
whe e 𝑐is he numbe o clus e s, 𝑂𝑖is numbe o clus e s he 𝑖belongs o, whe e |𝐶𝑘|is he numbe o nodes and 𝑛𝑒
𝐶𝑘is he numbe
o edges ha he 𝑘 h clus e 𝐶𝑘con ains.
The hi d modula i y o he o e lapping communi ies is defined by Cao in [44]and le e ages he weigh ed edges by cosine
simila i y o he node’s neighbo hood o ackle he p oblem o esolu ion limi . Resolu ion limi means a o ing la ge communi ies
by a modula i y measu e. This disad an age can be limi ed by p ope ly weigh ed edges [44]. The modula i y is defined as ollows:
𝑀𝑤=1
2𝑊
𝑐
∑
𝑘=1 ∑
𝑖,𝑗∈𝑉
(𝑤𝑖𝑗 −𝑠𝑖𝑠𝑗
2𝑊)𝑢𝑘𝑖𝑢𝑘𝑗 ,
whe e 𝑈=[𝑢𝑘𝑖]and he alue ep esen s he deg ee o which node 𝑣𝑖is in he 𝑘 h communi y, he edge weigh is 𝑤𝑖𝑗 =|𝑁(𝑖)∩𝑁(𝑗)|
√|𝑁(𝑖)||𝑁(𝑗)|,
he s eng h o node 𝑣𝑖is 𝑠𝑖=∑𝑗∈𝑁(𝑖)𝑤𝑖𝑗 and 𝑊is he o al weigh o he edges.
1The code o he me hod is a ailable online h ps://anonymous .4open .science / /g aph _hie a chical _agglome a i e _clus e ing -C946 /README .md.
In o ma ion Sciences 662 (2024) 120271
8
P. D áždilo á, P. P okop, J. Pla oš e al.
Fig. 2. Dend og ams o GHAC me hod wi h he p oposed dissimila i ies 𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 and 𝑑𝐶𝐿
𝐺𝐻𝐴𝐶 o Zacha y’s ka a e club ne wo k, whe e all maximal cliques a e he inpu
bases o he GHAC. The ne wo k co e in each agglome a i e s ep is e alua ed and he alues a e gi en in line plo s. The bo om axis illus a es he agglome a i e
s eps in he GHAC me hod, and he op axis po ays he espec i e dissimila i ies.
5.2. Indica ion o he cu le el in dend og am by modula i y
Zacha y’s ka a e club ne wo k is used in his sec ion o demons a e he p ocess o choosing he bes le el o a cu in a dend og am.
Fig. 2p esen s a dend og am ha isually ep esen s he agglome a i e p ocess o he p oposed me hod, e ealing he agglom-
e a ion o maximal cliques and clus e s, and p o iding insigh s in o he unde lying s uc u e. The bo om axis o he dend og am
demons a es he agglome a i e s eps o he algo i hm, while he op axis co esponds o he le el o cu s based on dissimila i y
alue.
Th oughou he agglome a ion p ocess, he quali y o ne wo k co e is assessed using modula i ies as a s uc u al quali y measu e.
The p og ess o he modula i ies alues du ing he agglome a i e s age o he GHAC me hod can be obse ed in Fig. 2 h ough he
h ee line plo s displayed on he op.
The highes modula i y alue o each line plo is selec ed and depic ed as a do ed line, indica ing a cu in he dend og am. In
ou p oposed communi y de ec ion algo i hm, his do ed line ep esen s he cu in he dend og am, whe e he bases a e me ged and
mapped o nodes o he ne wo k. I is no ewo hy ha he 𝑀𝑒and 𝑀𝑤exhibi he same cu le el in he dend og am, while 𝑀𝑜𝑣
indica es a diffe en cu le el.
By compa ing he co esponding dend og ams (illus a ed in Fig. 2) ob ained o me hods SL GHAC and CL GHAC, we obse e
significan diffe ences in he hie a chical s uc u e. The highe o e all modula i y alues 𝑀𝑒and 𝑀𝑤a e achie ed as seen in Fig. 2b,
while Fig. 2a shows a highe modula i y alue o 𝑀𝑜𝑣.
Each highligh ed cu wi hin he dend og am co esponds o a ne wo k co e ha is u he isualized in Fig. 3in he o iginal
ne wo k.
Du ing he analysis o he SL GHAC me hod, we can obse e he equi alen esul o he 𝑘-CPM me hod (wi h 𝑘 =3) as he
cu in he dend og am occu ed a s ep 27, ep esen ed by a g ey do ed line wi h a dissimila i y alue o a cu 𝑑𝑆𝐿
𝐻𝐴𝐶 =4∕3 on
he op axis. SL GHAC con inues wi h he de ec ion o la ge clus e s -o e and abo e he clus e s de ec ed ia clique pe cola ion.
The modula i y measu es 𝑀𝑒and 𝑀𝑤indica ed he bes cu o he agglome a i e s ep 11. Diffe en op imal cu a le el 32 was
iden ified by modula i y 𝑀𝑜𝑣. The ne wo k co e s ob ained om he SL GHAC me hod can be obse ed in Fig. 3b and Fig. 3e. I
is wo h men ioning ha none o hese ne wo k co e s exhibi in ui i ely meaning ul communi ies o he main ac o s o he social
ne wo k.
The au ho in [46] discussed he difficul ies wi h he 𝑘-CPM in Zacha y’s ka a e ne wo k, whe e he communi y de ec ion me hod
is no able o dis inguish be ween communi ies associa ed wi h wo key indi iduals (node 0and 33) who played pi o al oles in he
di ision o he ka a e club. The ob ained communi ies o he 𝑘-CPM me hod can be obse ed in Fig. 3a and Fig. 3d.
In o ma ion Sciences 662 (2024) 120271
9
P. D áždilo á, P. P okop, J. Pla oš e al.
Fig. 3. Illus a ion o he ne wo k co e s de ec ed by diffe en me hods o Zacha y’s ka a e club ne wo k. The g ey colo is used o communi ies wi h single nodes.
The dend og am in Fig. 2b shows a diffe en hie a chical s uc u e o he CL GHAC me hod. The co esponding ne wo k co e ,
as displayed in Fig. 3c, e eals he p esence o sepa a e communi ies specifically o med o nodes 0and 33 wi hin he ka a e club.
These communi ies a e isually ep esen ed by he colo s blue and o ange, espec i ely. Addi ionally, he e is a pu ple communi y
ha exhibi s o e laps and sha ed e ices be ween bo h main ac o s in he ka a e club.
5.3. Hie a chical aspec s o he p oposed me hods
The hie a chical aspec s o he p oposed me hods a e s udied o Coau ho ships in ne wo k science. The diffe en hie a chical
s uc u es o he p oposed me hods a e isualized by dend og ams. The ela ion be ween he hie a chy and he de ec ed o e lapping
communi ies is discussed o SL GHAC and CL GHAC.
One o he p ima y ad an ages o he p oposed me hod is i s abili y o e eal he hie a chical s uc u e o maximal cliques
wi hin a ne wo k. A single cu in a dend og am yields communi ies bu offe s a limi ed pe spec i e o he communi y s uc u e.
Ne e heless, he sequence o he ne wo k co e s displayed in Figs. 5b, 5d, and 5 demons a e he agglome a i e p ocess o he
CL GHAC ac oss a ious s eps and e eal a hie a chy o some communi ies. Fo ins ance, ocusing on he node ep esen ing M.
Newman in he ne wo k (deno ed in he op igh co ne ), we obse e he node’s assignmen o fi e communi ies in Fig. 5b. His wo
communi ies in s ep 141 o Fig. 4b a e colo ed in ligh khaki and ligh pu ple in Fig. 5d, which a e subsequen ly me ged in o a single
pu ple communi y as po ayed in Fig. 5 .
The cu le el indica ed by modula i ies 𝑀𝑒and 𝑀𝑤 o he SL GHAC equa es o 𝑘-CPM, due o he dissimila i y alue 𝑑𝑆𝐿
𝐺𝐻𝐴𝐶 =
4∕3. The comple e hie a chical s uc u e c ea ed by SL GHAC is isualized as a dend og am in Fig. 4a. This dend og am allows us
o examine he ou comes o he me hod beyond he pe cola ion o he 𝑘-CPM me hod o 𝑘 =3. This dend og am also p o ides a
isual ep esen a ion o he hie a chical s uc u e, enabling manual inspec ion. The o ma ion o long and connec ed s uc u es is
e iden in he SL GHAC dend og am in Fig. 4a. A le el 136, app oxima ely 50% o he bases a e inco po a ed in o a single clus e
du ing agglome a ion which is he effec o chaining cha ac e is ic o he SL app oach. This cu ’s ou come is isualized in Fig. 5c,
whe e he communi y highligh ed by blue colo co esponds o he agglome a ion in he bo om hal o he dend og am. In con as ,
he hie a chical communi y s uc u e o CL GHAC is mo e balanced, me ging simila numbe s o bases o o m clus e s a diffe en
hie a chical le els. The ne wo k co e s o CL GHAC con ain mo e locally-cen e ed communi ies compa ed o SL GHAC. Figs. 5c and
5d illus a e simila numbe s o de ec ed communi ies, bu wi h ma kedly dis inc communi y s uc u es.
5.4. Empi ical e alua ion o he p oposed communi y de ec ion me hods o selec ed eal-wo ld ne wo ks
We ha e examined he ou comes o ou p oposed me hods by applying hem o a selec ion o eal-wo ld ne wo ks. The subsequen
sec ions will p o ide a de ailed analysis o he esul s ob ained o selec ed ne wo ks.