what-when-how
In Depth Tutorials and Information
and recipients of emails during the corresponding time periods. he semantics of
an edge (
u
,
v
) in such a graph is that there has been at least five e-mail communica-
tions between
u
and
v
. he synthetic data was generated using the ER model with
parameters
n
= 1000 and
p
= 0.2.
Table 4.1 shows graph statistics and graph nonrandomness values (calculated
using
RG
and
R
G
∗
) of various social networks. We can observe that the relative non-
randomness measures (
R
G
∗
) of real-world social networks are significantly greater than
zero, while that of the synthetic random graph is very close to zero. Using
R
G
∗
, we can
relatively compare the randomness of graphs with different sizes and densities. For
example, we can observe that the network of the dolphins contains less randomness
than the karate data since
R
G
∗
of the dolphins (1.61) is greater than that of the karate
data (1.22). Furthermore,
R
G
∗
also indicates to what extent the graph is different from
random graphs. For the karate graph, we have
R
∗
=
1 22
and
1
R
G
, which
indicates how less likely the karate graph is generated by the ER model. Similarly,
for the dolphins data, we have
R
∗
=
1 61
and
1
−
Φ
(
∗
)
= .
0 11
−
Φ
(
= .
R
G
.
he graph spectrum has been well investigated in the graph analysis field.
Chung and Graham indicated the use of the largest eigenvalue
λ
1
as an index of
the nonrandomness of the overall graph since the first eigenvalue of random graphs
characterizes the frequency of subgraphs [7]. Our analysis shows that
λ
1
may not be
an appropriate measure to quantify the graph nonrandomness for real-world social
networks since they usually contain more than one community. Actually, we can
see that the index of graph nonrandomness using
λ
1
is a special case of our proposed
measure
RG
with
k
= 1.
It has been shown that the eigenvectors of the Laplacian matrix and the normal
matrix are good indicators of community clusters [10, 28, 32, 38]. he diference
between our nonrandomness framework and those traditional spectral clustering
∗
)
0 054
Table 4.1
GraphNonrandomnessand
Characteristics
of
Various
Social
Networks
Network
n
m
RG
R
G
Synthetic
1000
99820
200
0.02
Karate
34
78
11.7
1.22
Dolphins
62
159
13.1
1.61
Polbooks
105
441
23.5
6.87
Enron
151
869
41.2
4.18
Netsci
1589
2742
38.5
128
Polblogs
1222
16714
134
187
