what-when-how
In Depth Tutorials and Information
k
1
2
∑
∑
∑
=
,
=
=
λ
R
R u v
(
)
R u
( )
.
(4.4)
G
i
(
u v E
, ∈
)
u G
∈
i
=
1
Proof. he second equation is straightforward since every edge is counted twice in
the sum of node nonrandomness. For the third equation, denote
X
as (
x
1
,
x
2
,…,
x
k
)
where each column is an eigenvector of
A
:
A
x
i
=
λ
i
x
i
, and hence we have
k
∑
λ
" "
∑
∑
,
=
α α
=
=
R u v
(
)
a
T
trace X AX
(
T
)
uv
u
(
u v E
, ∈
)
u v
,
i
=
1
he foregoing result is elegant since we can use the sum of the first
k
eigenvalues
to determine the nonrandomness of the overall graph. Recall that
k
indicates the
number of communities in the graph. In this chapter we assume that the value of
k
is either specified by domain users or discovered by those graph partition methods.
here are many studies on how to partition a graph into
k
communities (refer to a
survey paper [6]).
All real networks lie somewhere between the extremes of complete order and
complete randomness. While the absolute nonrandomness measure
RG
can indi-
cate how random a graph
G
is, it is more desirable to give a relative measure so that
graphs with different size and density can be compared. One intuitive approach is
comparing the graph's nonrandomness value with the expectation of the nonran-
domness value of all random graphs generated by the ER model [11]. We can use
the standardized measure defined as
R
−
(
E R
R
)
∗
=
G
G
R
G
σ
(
)
G
where
E
(
RG
) and
σ
(
RG
) denote the expectation and standard deviation of the
graph nonrandomness under the ER model. Our heorem 1 shows the distribution
of
RG
.
heorem1
.
ForagraphGwithk
(>
n
)
communitieswhereeachcommunityisgener-
atedbytheERmodelwithparametern/kandp,R
G
hasanasymptoticallynormaldis-
tributionwithmean
(
n-2k
)
p+kandvariance2kp
(
1 - p
)
wherep
= 2
km/n
(
n-k
).
Proof: In
G
, each community has
n
/
k
nodes, and hence,
2
m
km
n n k
2
=
=
.
p
−
−
k
n
k
(
n
k
1
)
(
)
