Modula i y spec a, eigen-subspaces,
and s uc u e o weigh ed g aphs
Ma ianna Bolla ∗
Ins i u e o Ma hema ics, Budapes Uni e si y o Technology and Economics and
In a-Uni e si y Cen e o Telecommunica ions and In o ma ics, Deb ecen
Abs ac
The ole o he no malized modula i y ma ix in inding homogeneous cu s will be
p esen ed. We also discuss he es abili y o he s uc u al eigen alues and ha
o he subspace spanned by he co esponding eigen ec o s o his ma ix. In he
p esence o a spec al gap be ween he k−1 la ges absolu e alue eigen alues and
he emainde o he spec um, his in u n implies he es abili y o he sum o
he inne a iances o he kclus e s ha a e ob ained by applying he k-means
algo i hm o he app op ia ely chosen e ex ep esen a i es.
Key wo ds: No malized modula i y, Volume egula i y, Spec al clus e ing,
Tes able weigh ed g aph pa ame e s, S uc u al eigen alues, Spec al subspaces
1 In oduc ion
The pu pose o his pape is o summa ize he spec al p ope ies and es a-
bili y o he spec um and spec al subspaces o he no malized modula i y
ma ix in oduced in [9] o ind egula e ex pa i ions. We will gene alize
he Laplacian based spec al clus e ing me hods o eco e so-called olume
egula clus e pai s such ha he in o ma ion low be ween he pai s and
wi hin he clus e s is as homogeneous as possible. Fo his pu pose, we ake
in o conside a ion bo h ends o he no malized Laplacian spec um, i.e., la ge
absolu e alue, so-called s uc u al eigen alues o ou no malized modula i y
ma ix in oduced jus o his con enience.
∗Resea ch suppo ed by he Hunga ian Na ional Resea ch G an OTKA-KTIA
77778 and by he T´
AMOP-4.2.2.C-11/1/KONV-2012-0001 p ojec , suppo ed by
he Eu opean Union, co- inanced by he Eu opean Social Fund.
Email add ess: [email p o ec ed] (Ma ianna Bolla).
P ep in submi ed o Else ie 30 Ap il 2013
In Theo em 3, we es ima e he cons an o olume egula i y in e ms o he
gap be ween he s uc u al and o he eigen alues, and he k- a iance o he op-
imal e ex ep esen a i es cons uc ed by he eigen ec o s co esponding o
he s uc u al eigen alues. He e we gi e a mo e de ailed p oo o his s a emen
han in [10]. This heo em implies ha o a gene al edge-weigh ed g aph, he
exis ence o k−1 s uc u al eigen alues o he no malized modula i y ma ix,
sepa a ed om 0, is indica ion o a k-clus e s uc u e such ha he clus e -
pai s a e olume egula wi h cons an depending on he spec al gap and he
abo e k- a iance. The clus e s hemsel es can be eco e ed by applying he
k-means algo i hm o he e ex ep esen a i es. Hence, Theo em 3 implies
ha spec al clus e ing o he e ices in o kpa s gi es sa is ac o y pa i ion
in he sense o olume egula i y.
Fu he mo e, in Theo ems 8 and 10, we p o e he es abili y o he s uc u al
eigen alues and he co esponding eigen-subspace o he no malized modula -
i y ma ix in he sense o [12]. In iew o his, spec al clus e ing me hods
can be pe o med on a smalle pa o he unde lying g aph and gi e good
app oxima ion o he clus e s uc u e.
2 P elimina ies
Th oughou he pape , we use he gene al amewo k o an edge-weigh ed
g aph. Le G=Gn= (V, W) be an edge-weigh ed g aph on e ex-se V
(|V|=n) and n×nsymme ic weigh -ma ix Wo non-nega i e eal en ies
and ze o diagonal. We will call he numbe s di=Pn
j=1 wij (i= 1, . . . , n)
gene alized deg ees, and he diagonal ma ix D=diag (d1, . . . , dn)deg ee
ma ix. In his and he nex sec ion, wi hou loss o gene ali y, Vol(V) = 1
will be assumed, whe e he olume o he e ex-subse U⊆Vis Vol(U) =
Pi∈Udi. In he sequel, we only conside connec ed g aphs, which means ha
Wis i educible.
In [9], we de ined he no malized e sion o he modula i y ma ix (in oduced
in [21]) as MD=D−1/2WD−1/2−√d√dT, whe e √d= (√d1,...,√dn)T,
and we called i no malized modula i y ma ix. The spec um o his ma ix is
in he [-1,1] in e al, and 0 is always an eigen alue wi h uni -no m eigen ec o
√d. Indeed, in [5] we p o ed ha 1 is a single eigen alue o D−1/2WD−1/2wi h
co esponding uni -no m eigen ec o √d, p o ided ou g aph is connec ed.
This becomes a ze o eigen alue o MDwi h he same eigen ec o , whence 1
canno be an eigen alue o MDi Gis connec ed. In ac , he in oduc ion
o his ma ix is a he echnical, he spec al gap, u he , Lemma 1 and
Theo em 3 can be e be o mula ed wi h i . I can also be ob ained om he
no malized Laplacian by sub ac ing i om he iden i y and dep i ing o i s
i ial ac o . No malized Laplacian was used o spec al clus e ing in se e al
2
pape s (e.g., [3,5,6,14,20]), he idea o which can be summa ized by means o
he spec al decomposi ion o he no malized modula i y ma ix. We in oduce
he ollowing no a ion: he weigh ed cu be ween he e ex-subse s X, Y ⊆V
is w(X, Y ) = Pi∈XPj∈Ywij. We will equen ly e e o he ollowing ac s.
(a) The spec al decomposi ion o MDsol es he ollowing quad a ic placemen
p oblem. Fo a gi en posi i e in ege k(1 < k < n), we wan o minimize
Qk=Pi<j wijk i− jk2on he condi ions
n
X
i=1
di i T
i=Ik−1and
n
X
i=1
di i=0(1)
whe e he ec o s 1,..., na e (k−1)-dimensional ep esen a i es o he
e ices, which o m he ow ec o s o he n×(k−1) ma ix X. Deno e he
eigen alues o MD, in dec easing o de , by 1 > λ1≥ ··· ≥ λn≥ −1 wi h co -
esponding uni -no m, pai wise o hogonal eigen ec o s u1,...,un. In [5],
we p o ed ha he minimum o Qksubjec o (1) is k−1−Pk−1
i=1 λiand is a -
ained by he ep esen a ion such ha he op imum e ex ep esen a i es
∗
1,..., ∗
na e ow ec o s o he ma ix X∗= (D−1/2u1,...,D−1/2uk−1).
Ins ead o X, he augmen ed n×kma ix ˜
Xcan as well be used, which
is ob ained om Xby inse ing he column x0=1o all 1’s. In ac ,
x0=D−1/2u0, whe e u0=√dis he eigen ec o co esponding o he
eigen alue 1 o D−1/2WD−1/2. Then
Qk= (D1/2˜
X)T(In−D−1/2WD−1/2)(D1/2˜
X),
and minimizing Qkon he cons ain (1) is equi alen o minimizing he
abo e exp ession subjec o ˜
XTD˜
X=Ik. This p oblem is he con inuous
elaxa ion o minimizing
Qk(Pk) = (D1/2˜
X(Pk))T(In−D−1/2WD−1/2)(D1/2˜
X(Pk))
o e he se o k-pa i ions Pk= (V1, . . . , Vk) o he e ices such ha Pkis
plan ed in o ˜
Xin he way ha he columns o ˜
X(Pk) a e so-called no mal-
ized pa i ion- ec o s belonging o Pk. Namely, he coo dina es o he i h
column a e ze os, excep hose indexing e ices o Vi, which a e equal o
1
√Vol(Vi)(i= 1, . . . , k). In ac , his is he no malized cu p oblem, which is
discussed in [20] o k= 2, u he , in [3] and [6] o a gene al k, and he
solu ion is based on he abo e con inuous elaxa ion.
(b) Now, le us maximize he no malized Newman–Gi an modula i y o Gin-
duced by Pk, de ined in [9] as
Mk(Pk) =
k
X
a=1
1
Vol(Va)X
i,j∈Va
(wij −didj) =
k
X
a=1
w(Va, Va)
Vol(Va)−1
o e he se Pko he k-pa i ions o V. I is easy o see ha Mk(Pk) =
3
k−1−Qk(Pk), and hence, he abo e ask has he same spec al elaxa ion
as he no malized cu p oblem. Le Mk= maxPk∈PkMk(Pk) deno e he
maximum k-way no malized Newman-Gi an modula i y o he weigh ed
g aph G.
(c) Finally, om he abo e conside a ions i is s aigh o wa d ha Mk≤
Pk−1
i=1 λi, o equi alen ly, he minimum no malized k-way cu is a leas he
he sum o he k−1 smalles posi i e no malized Laplacian eigen alues.
As o he minimum no malized k-way cu , in [6] we also ga e an uppe
es ima e by cons an imes he sum o he k−1 smalles posi i e no malized
Laplacian eigen alues, which cons an depends on he so-called k- a iance
o he e ex ep esen a i es de ined in he ollowing way.
S2
k(X) = min
Pk∈Pk
S2
k(X, Pk) = min
Pk=(V1,...,Vk)
k
X
a=1 X
j∈Va
djk j−cak2(2)
whe e ca=1
Vol(Va)Pj∈Vadj jis he weigh ed cen e o clus e Vaand 1,
. . . , n∈Rk−1a e ows o X. (The augmen ed ˜
Xwould gi e he same k-
a iance.) The cons an o ou es ima ion depended on S2
k(X∗), and i was
close o 1 i his k- a iance o he op imum (k−1)-dimensional e ex ep e-
sen a i es was small enough. No e ha S2
k(X, Pk) is he objec i e unc ion
o he weigh ed k-means algo i hm.
In his way, we showed ha la ge posi i e eigen alues o he no malized modu-
la i y ma ix a e esponsible o clus e s wi h high in a- and low in e -clus e
densi ies. Likewise, maximizing Qk(Pk) ins ead o minimizing o e Pk, small
nega i e eigen alues o he no malized modula i y ma ix a e esponsible o
clus e s wi h low in a- and high in e -clus e densi ies (see [9]). Ou idea is
ha aking in o accoun eigen alues om bo h ends o he no malized modu-
la i y spec um, we can eco e so-called egula clus e pai s. Fo his pu pose,
we use he no ion o olume egula i y o be in oduced in he nex sec ion.
3 No malized modula i y and olume egula i y
Wi h he no malized modula i y ma ix, he well-known Expande Mixing
Lemma ( o simple g aphs see, e.g., [17]) is o mula ed o edge-weigh ed
g aphs in he ollowing way (see [8]).
Lemma 1 P o ided Vol(V) = 1, o all X, Y ⊆V,
|w(X, Y )−Vol(X)Vol(Y)| ≤ kMDk·qVol(X)Vol(Y),
whe e kMDkdeno es he spec al no m o he no malized modula i y ma ix
o G= (V, W).
4
Since he spec al gap o Gis 1 −kMDk, a la ge spec al gap indica es small
disc epancy as a quasi- andom p ope y discussed in [15]. I he e is a gap no
a he ends o he spec um, we wan o pa i ion he e ices in o clus e s so
ha a ela ion simila o he abo e p ope y o he edge-densi ies be ween he
clus e pai s would hold. Fo his pu pose, we use a sligh ly modi ied e sion
o he olume egula i y’s no ion in oduced in [2].
De ini ion 2 Le G= (V, W)be an edge-weigh ed g aph wi h Vol(V)=1.
The disjoin pai A, B ⊆Vis α- olume egula i o all X⊆A,Y⊆Bwe
ha e
|w(X, Y )−ρ(A, B)Vol(X)Vol(Y)| ≤ αqVol(A)Vol(B),
whe e ρ(A, B) = w(A,B)
Vol(A)Vol(B)is he ela i e in e -clus e densi y o (A, B).
In he ideal k-clus e case, le us conside he ollowing gene alized andom
simple g aph model: gi en he pa i ion (V1, . . . , Vk) o V(|V|=n), e ices
i∈Vaand j∈Vba e connec ed wi h p obabili y pab, independen ly o each
o he , 1 ≤a, b ≤k. We can hink o he p obabili y pab as he in e -clus e
densi y o he pai (Va, Vb). Since gene alized andom g aphs can be iewed
as edge-weigh ed g aphs wi h a special block-s uc u e bu dened wi h andom
noise, based on [7], we a e able o gi e he ollowing spec al cha ac e iza ion
o hem. Fixing k, and ending wi h n o in ini y in such a way ha he clus e
sizes g ow a he same a e, he e exis s a posi i e numbe θ < 1, independen
o n, such ha o e e y 0 < τ < 1/2 he e a e exac ly k−1 eigen alues
o MDg ea e han θ−n−τ, while all he o he s a e a mos n−τin abso-
lu e alue. Fu he , he k- a iance o he e ex ep esen a i es cons uc ed
by he k−1 ans o med s uc u al eigen ec o s is O(n−2τ), and he clus e
pai s a e α- olume egula wi h any small α, almos su ely. No e ha gen-
e alized quasi andom g aphs de ined in [18] a e de e minis ic coun e pa s o
gene alized andom g aphs wi h he same spec al p ope ies.
Theo em 3 Le G= (V, W)be a connec ed edge-weigh ed g aph on n e -
ices, wi h gene alized deg ees d1, . . . , dnand deg ee ma ix D. Assume ha
Vol(V) = 1, and he e a e no dominan e ices, i.e., di= Θ(1/n),i=
1, . . . , n, as n→ ∞. Le he eigen alues o MD, enume a ed in dec easing
absolu e alues, be
1≥ |µ1| ≥ ··· ≥ |µk−1|> ε ≥ |µk| ≥ ··· ≥ |µn|= 0.
The pa i ion (V1, . . . , Vk)o Vis de ined so ha i minimizes he weigh ed
k- a iance S2
k(X∗)o he op imum e ex ep esen a i es – de ined in (2) –
ob ained as ow ec o s o he n×(k−1) ma ix X∗o column ec o s D−1/2ui,
whe e uiis he uni -no m eigen ec o co esponding o µi(i= 1, . . . , k −1).
Assume ha he e is a cons an 0< K ≤1
ksuch ha |Vi| ≥ Kn,i= 1, . . . , k.
Wi h he no a ion s=qS2
k(X∗), he (Vi, Vj)pai s a e O(√2ks +ε)- olume
egula (i6=j)and o he clus e s Vi(i= 1, . . . , k) he ollowing holds: o
5

all X, Y ⊂Vi,
|w(X, Y )−ρ(Vi)Vol(X)Vol(Y)|=O(√2ks +ε)Vol(Vi),
whe e ρ(Vi) = w(Vi,Vi)
Vol2(Vi)is he ela i e in a-clus e densi y o Vi.
No e ha , in Sec ion 2, we indexed he eigen alues o MDin non-inc easing
o de and deno ed hem by λ’s. The se o all λi’s is he same as ha o all
µi’s. None heless, we need a di e en no a ion o he eigen alues indexed in
dec easing o de o hei absolu e alues. Recall ha 1 canno be an eigen alue
o MDi Gis connec ed. Consequen ly, |µ1|= 1 can be i and only i µ1=−1,
i.e., i Gis bipa i e. Fo example, i he condi ions o he abo e heo em hold
wi h k= 2 and µ1=−1 (|µi| ≤ ε,i≥2), hen ou g aph is a bipa i e
expande discussed in [1] in de ails.
Fo he p oo we need he de ini ion o he cu no m o a ma ix (see e.g., [16])
and he ela ion be ween i and he spec al no m.
De ini ion 4 The cu no m o he eal ma ix Awi h ow-se Row and column-
se Col is
kAk= max
R⊂Row, C⊂Col X
i∈RX
j∈C
aij
.
Lemma 5 Fo e e y m×n eal ma ix A,
kAk≤√mnkAk,
whe e he igh hand side con ains he spec al no m, i.e. he la ges singula
alue o A.
PROOF.
kAk= max
x∈{0,1}m,y∈{0,1}n|xTAy|= max
x∈{0,1}m,y∈{0,1}n
(x
kxk)TA(y
kyk)·kxk·kyk|
≤√mn max
kxk=1,kyk=1 |xTAy|=√mnkAk,
since o x∈ {0,1}m,kxk ≤ √m, and o y∈ {0,1}n,kyk ≤ √n.2
The de ini ion o he cu no m and he esul o he abo e lemma na u ally
ex ends o symme ic ma ices wi h m=n, he spec al no m o which is he
maximum o absolu e alues o hei eigen alues.
PROOF. (Theo em 3). Recall ha he spec um o D−1/2WD−1/2di e s
om ha o MDonly in he ollowing: i con ains he eigen alue µ0= 1 wi h
6
co esponding uni -no m eigen ec o u0=√dins ead o he eigen alue 0 o
MDwi h he same eigen ec o . I Gis connec ed, 1 is a simple eigen alue. The
op imum (k−1)-dimensional ep esen a i es o he e ices a e ow ec o s o
he ma ix X∗= (x∗
1,...,x∗
k−1), whe e x∗
i=D−1/2ui(i= 1, . . . , k −1). The
ep esen a i es can as well be ega ded as k-dimensional ones, as inse ing he
ec o x∗
0=D−1/2u0=1will no change he k- a iance s2=S2
k(X∗). Assume
ha he minimum k- a iance is a ained on he k-pa i ion (V1, . . . , Vk) o he
e ices. By an easy analysis o a iance a gumen (see [5]) i ollows ha
s2=
k−1
X
i=0
dis 2(ui, F),(3)
whe e F=Span {D1/2z1,...,D1/2zk}wi h he so-called no malized pa i ion
ec o s z1,...,zko coo dina es zji =1
√Vol(Vi)i j∈Viand 0, o he wise
(i= 1, . . . , k). No e ha he ec o s D1/2z1,...,D1/2zk o m an o hono mal
sys em. By conside a ions p o ed in [5], we can ind ano he o hono mal
sys em 0,..., k−1∈Fsuch ha
s2≤
k−1
X
i=0 kui− ik2≤2s2(4)
( 0=u0, since u0∈F). We app oxima e he ma ix D−1/2WD−1/2=
Pn−1
i=0 µiuiuT
iby he ank kma ix Pk−1
i=0 µi i T
iwi h he ollowing accu acy
(in spec al no m):





n−1
X
i=0
µiuiuT
i−
k−1
X
i=0
µi i T
i



≤
k−1
X
i=0 |µi|·

uiuT
i− i T
i

+




n−1
X
i=k
µiuiuT
i




(5)
which can be es ima ed om abo e wi h Pk−1
i=0 sin αi+ε≤Pk−1
i=0 kui− ik+ε≤
√2ks+ε, whe e αiis he angle be ween uiand i, and o i , sin αi
2=1
2kui− ik
holds, i= 0, . . . , k −1.
Based on hese conside a ions and ela ion be ween he cu no m and he
spec al no m (see Lemma 5), he densi ies o be es ima ed in he de ining
o mula o olume egula i y can be w i en in e ms o s epwise cons an
ec o s in he ollowing way. The ec o s yi:= D−1/2 ia e s epwise cons an s
on he pa i ion (V1, . . . , Vk), i= 0, . . . , k −1. The ma ix Pk−1
i=0 λiyiyT
iis
he e o e a symme ic block-ma ix on k×kblocks belonging o he abo e
pa i ion o he e ices. Le ˆwab deno e i s en ies in he (a, b) block (a, b =
1, . . . , k). Using (5), he ank kapp oxima ion o he ma ix Wis pe o med
wi h he ollowing accu acy o he pe u ba ion E:
kEk=




W−D(
k−1
X
i=0
µiyiyT
i)D




=




D1/2(D−1/2WD−1/2−
k−1
X
i=0
µi i T
i)D1/2




.
7
The e o e, he en ies o W– o i∈Va,j∈Vb– can be decomposed as
wij =didjˆwab +ηij, whe e he cu no m o he n×nsymme ic e o ma ix
E= (ηij) es ic ed o Va×Vb(o he wise i con ains en ies all ze os) and
deno ed by Eab, is es ima ed as ollows:
kEabk≤nkEabk ≤ n·kD1/2
ak·(√2ks +ε)·kD1/2
bk
≤n·
u
u
c1
Vol(Va)
|Va|·
u
u
c1
Vol(Vb)
|Vb|·(√2ks +ε)
=c1·sn
|Va|·sn
|Vb|·qVol(Va)qVol(Vb)(√2ks +ε)
≤c1·1
KqVol(Va)qVol(Vb)(√2ks +ε)
=cqVol(Va)qVol(Vb)(√2ks +ε).
He e he diagonal ma ix Dacon ains he diagonal pa o D es ic ed o Va,
o he wise ze os, and he cons an cdoes no depend on n. Consequen ly, o
a, b = 1, . . . , k and X⊆Va,Y⊆Vb:
|w(X, Y )−ρ(Va, Vb)Vol(X)Vol(Y)|=
X
i∈XX
j∈Y
(didjˆwab +ηij)−Vol(X)Vol(Y)
Vol(Va)Vol(Vb)X
i∈VaX
j∈Vb
(didjˆwab +ηij)
=
X
i∈XX
j∈Y
ηij −Vol(X)Vol(Y)
Vol(Va)Vol(Vb)X
i∈VaX
j∈Vb
ηij≤2c(√2ks +ε)qVol(Va)Vol(Vb),
ha gi es he equi ed s a emen bo h in he a6=band a=bcase. 2
No e ha in he k= 2 special case, due o a heo em p o ed in [5], he
2- a iance o he op imum 1-dimensional ep esen a i es can be di ec ly es i-
ma ed om abo e by he gap be ween he wo la ges absolu e alue eigen-
alues o MD, and hence, he s a emen o Theo em 3 simpli ies, see [8]. Fo
a gene al k, we can make he ollowing conside a ions.
Assume ha he no malized modula i y spec um (wi h dec easing absolu e
alues) o G= (V, W) sa is ies
1≥ |µ1| ≥ ··· ≥ |µk−1| ≥ θ > ε ≥ |µk| ≥ ··· ≥ |µn|= 0.
Ou pu pose is o es ima e swi h he gap δ:= θ−ε. We will use he no a ion
o he p oo o Theo em 3 and apply he esul s o [4] o he pe u ba ion o
8
spec al subspaces o he symme ic ma ices
A=
n−1
X
i=0
µiuiuT
iand B=
k−1
X
i=0
µi i T
i
in he ollowing si ua ion. The subse s S1={µk, . . . , µn−1}and S2={µ0, . . . , µk−1}
o he eigen alues o D−1/2WD−1/2a e sepa a ed by an annulus, whe e dis (S1, S2) =
δ > 0. Deno e by PAand PB he p ojec ions on o he spec al subspaces o
Aand Bspanned by he eigen ec o s co esponding o he eigen alues in S1
and S2, espec i ely:
PA(S1) =
n−1
X
j=k
ujuT
j,PB(S2) =
k−1
X
i=0
i T
i.
Then Theo em VII.3.4 o [4] implies ha
kPAPBkF≤1
δkPA(A−B)PBkF,(6)
whe e k.kFdeno es he F obenius no m. On he le hand side, kPAPBkF=
qPk−1
i=0 sin2αi, and in iew o kui− ik= 2 sin αi
2and (4), his is be ween √3
2s
and s. On he igh hand side,
PAAPB−PABPB= (PAA)PB−PA(PBB) =
k−1
X
i=0
n−1
X
j=k
(µj−µi)uT
j(ui− i)uj T
i,
whe e he F obenius no m o he ank 1 ma ices uj T
iis 1, and he inne
p oduc uT
j(ui− i) is he smalle i he ui’s and he i’s a e he close (i=
1, . . . , k −1). The e o e, by he inequali y (6), sis he smalle i δis he la ge
and he |µj−µi|di e ences o i= 0, . . . , k −1; j=k, . . . , n −1 a e close
o δ. I |µk|=εis small, hen |µ1|,...,|µk−1|should be close o each o he
(µ0= 1 does no play an impo an ole because o u0= 0).
4 Tes abili y o he no malized modula i y spec um and eigen-
subspaces
Au ho s o [12] de ined he es abili y o simple g aph pa ame e s and p o ed
equi alen no ions o his es abili y. They also an icipa ed ha hei esul s
emain alid i hey conside weigh ed g aph sequences (Gn) wi h edge-weigh s
in he [0,1] in e al and no dominan e ex-weigh s αi(Gn)>0 (i= 1, . . . , n),
i.e., maxiαi(Gn)
αGn→0 as n→ ∞, whe e αGn=Pn
i=1 αi(Gn). To his end, in [11],
we sligh ly modi ied he de ini ion o a es able g aph pa ame e o weigh ed
g aphs in he ollowing way.
9
and he spec al decomposi ion o i s no malized modula i y ma ix uns in
polynomial ime in he educed numbe o he e ices. Unde he e ex- and
clus e -balance condi ions his me hod can gi e qui e good app oxima ions
o he mul iway cu s and helps us o ind he numbe o clus e s and iden i y
he clus e s uc u e. In addi ion, aking in o accoun bo h he posi i e and
nega i e, la ge absolu e alue eigen alues oge he wi h eigen ec o s, egula
cu s can also be de ec ed, as he in es iga ed spec al cha ac e is ics gi e good
es ima es o he olume egula i y’s cons an o he clus e pai s by Theo-
em 3. Such egula cu s a e o impo ance in social o biological ne wo ks,
e.g., i we wan o ind equally unc ioning synapses o he b ain.
Acknowledgemen s
We hank he anonymous e e ee o his/he cons uc i e commen s.
Re e ences
[1] Alon, N., 1986 Eigen alues and expande s, Combina o ica 6(1986), 83-96.
[2] Alon, N., Coja-Oghlan, A., Han, H., Kang, M., R¨odl, V., and Schach , M.,
Quasi- andomness and algo i hmic egula i y o g aphs wi h gene al deg ee
dis ibu ions, Siam J. Compu . 39 (6) (2010), 2336-2362.
[3] Az an, A. and Ghah amani, Z., Spec al me hods o au oma ic mul iscale da a
clus e ing, in P oceedings o he CVPR Con e ence (2006), pp. 190-197.
[4] Bha ia, R., Ma ix Analysis, Sp inge , New Yo k, 1997.
[5] Bolla, M. and Tusn´ady, G., Spec a and op imal pa i ions o weigh ed g aphs,
Disc e . Ma h. 128 (1994), 1-20.
[6] Bolla, M. and Moln´a -S´aska, G., Isope ime ic p ope ies o weigh ed g aphs
ela ed o Laplacian spec um and canonical co ela ions, S udia Sci. Ma h.
Hun. 39 (2002), 425-441.
[7] Bolla, M., Recognizing linea s uc u e in noisy ma ices, Lin. Alg. Appl. 402
(2005), 228-244.
[8] Bolla, M., Beyond he expande s, In e na ional Jou nal o Combina o ics,
Pape 787596 (2011).
[9] Bolla, M., Penalized e sions o he Newman–Gi an modula i y and hei
ela ion o mul iway cu s and k-means clus e ing, Physical Re iew E 84, 016108
(2011).
16

[10] Bolla, M., Spec a and s uc u e o weigh ed g aphs, Elec onic No es in Disc e .
Ma h. 38 (2011), 149-154.
[11] Bolla, M., K´oi, T., K ´amli, A., Tes abili y o minimum balanced mul iway cu
densi ies, Disc e . Appl. Ma h. 160 (2012), 1019–1027.
[12] Bo gs, C., Chayes, J. T., Lo ´asz, L., T.-S´os, V., and Vesz e gombi, K.,
Con e gen Sequences o Dense G aphs I: Subg aph F equencies, Me ic
P ope ies and Tes ing, Ad ances in Ma h. 219 (2008), 1801-1851.
[13] Bo gs, C., Chayes, J. T., Lo ´asz, L., T.-S´os, V., and Vesz e gombi, K.,
Con e gen Sequences o Dense G aphs II: Mul iway Cu s and S a is ical
Physics, Annals o Ma h. 176, 151–219.
[14] Chung, F., Spec al G aph Theo y, CBMS Regional Con e ence Se ies in
Ma hema ics 92, Ame ican Ma hema ical Socie y, 1997.
[15] Chung, F. and G aham, R., Quasi- andom g aphs wi h gi en deg ee sequences,
Random S uc u es and Algo i hms 12 (2008), 1-19.
[16] F ieze, A. and Kannan, R., Quick app oxima ion o ma ices and applica ions.
Combina o ica 19 (1999), 175–220.
[17] Hoo y, S., Linial, N., and Widge son, A., Expande g aphs and hei
applica ions, Bulle in (New se ies) o he Ame ican Ma hema ical Socie y 43
(4) (2006), 439-561.
[18] Lo ´asz, L. and T.-S´os, V., Gene alized quasi andom g aphs, J. Comb. Theo y
B. 98 (2008), 146-163.
[19] Lo ´asz L, L. and Szegedy, B., Fini ely o cible g aphons, J. Comb. Theo y B.
101 (2011), 269–301.
[20] Meil˘a, M. and Shi, J., Lea ning segmen a ion by andom walks, in P oceedings
o he NIPS (Neu al In o ma ion P ocessing Sys ems) 13 Con e ence, T. K.
Leen, T. G. Die e ich, and V. T esp eds, MIT P ess, Camb idge (2001), pp.
873-879.
[21] Newman, M. E. J., Finding communi y s uc u e in ne wo ks using he
eigen ec o s o ma ices, Physical Re iew E 74, 036104 (2006).
[22] Reicha d , J. and Bo nhold , S., Pa i ioning and modula i y o g aphs wi h
a bi a y deg ee dis ibu ion, Physical Re iew E 76, 015102(R) (2007).
[23] R´enyi, A., On measu es o dependence, Ac a Ma h. Acad. Sci. Hunga . 10
(1959), 441-451.
17