what-when-how
In Depth Tutorials and Information
he third measure is the transitivity measure,
C
, which is one type of cluster-
ing coefficient measure and which characterizes the presence of local loops near a
vertex. It is formally defined as
C
= 3
N
Δ
/N
3
, where
N
∆
is the number of triangles and
N
3
is the number of connected triples.
he fourth measure is subgraph centrality,
SC
, which is used to quantify the
centrality of the subgraphs based on the vertex
i
[12]. It is formally defined as
SC
i
k
P
k
=
Σ
=
Σ
Σ
1
i
n
SC
1
i
n
∞
,
where
P
i
k
is the number of paths that start with
=
=
=
1
i
1
k
0
!
n
n
i
and end in
i
with length
k
.
hroughout this chapter, we focus on two important eigenvalues of the graph
spectrum. he irst one is the largest eigenvalue (
λ
1
) of the adjacency matrix
A
. he
eigenvalues of
A
encode information about the cycles of a network as well as its
diameter. Since
A
contains no self-loops, the sum over all eigenvalues
(
=
1
λ
is
Σ
i
n
)
i
Σ
i
=
1
λ λ
is equal to minus the number of edges,
zero. he sum of product pairs
(
)
i
j
and
Σ
i
≠ ≠
λ λ λ
is twice the number of triangles in G. he maximum degree,
chromatic number, clique number, and extent of branching in a connected graph are
all related to
λ
1
. In Reference 37, the authors studied how a virus propagates in a real
work and proved that the epidemic threshold for a network is closely related to
λ
1
.
he second one is the second eigenvalue (
μ
2
) of the Laplacian matrix
L
, which
is also called the algebraic connectivity of the graph. he eigenvalues of
L
encode
information about the tree structure of
G
. he spectrum of
L
contains a 0 for every
connected component. he multiplicity of 0 as an eigenvalue is equal to the num-
ber of components in
G
j k
i
j
k
Π
=
μ
and equals the number of spanning trees of
G
.
When
μ
2
is close to zero, the graph is almost disconnected. Its diameter is small if
the eigenvalue gap is large (i.e.,
μ
2
>>
μ
1
).
Many graph topological features can be expressed as an explicit function of
spectrum and eigenvectors. For example, the authors in Reference 12 show that the
subgraph centrality
SC
, which characterizes the participation of each node in all
subgraphs in a network, can be calculated mathematically from the spectra of the
adjacency matrix of the network,
SC
1
i
n
2
i
n
=
Σ
1
i
n
e
λ
.
he diameter of a general graph
i
=
1
n
is related to
μ
n
and
μ
2
and bounded by
⎡
⎤
−
cosh
−
1
(
n
1
2
2
)
≤
⎢
⎢
⎥
⎥
.
Diam G
(
)
(
)
μ
+
−
μ
cosh
−
1
n
n
⎢
⎥
μ
μ
Another example is the commute time [27] based on random walks on a graph
G, which can be calculated using the eigenvalues and eigenvectors of the normal
matrix
N
. Refer to Reference 30 for more relationships between the spectral and
real characteristics of graphs.
Many social network mining methods have been developed based on the
spectral characteristics. For example, the HITS algorithm [20], which detects the
authoritative/important individuals in the network, is based on eigenvectors of the
adjacency matrix; the maximal-cliques-finding algorithm developed in Reference
