Information Technology Reference
In-Depth Information
The
modularity
measure
Q
of
the
decomposition
C
is
defined
as
Q
=
2
.
The weighting of the edges of a graph by a weight function
|
E
|
−
|
E
(
Ci
,∗
)
|
C
i
)=
|
E
(
C
i
)
|
∑
1
≤
i
≤
p
Q
(
C
i
)
where
Q
(
|
E
|
ω
:
E
→
R
can be
∑
e
∈
E
ω
(
e
)
−
∑
e
∈
E
(
Ci
,∗
)
ω
(
e
)
2
.
∑
e
∈
E
(
C
i
)
ω
(
e
)
accounted for by setting
Q
(
C
i
)=
∑
e
∈
E
ω
(
e
)
(
)
is used to judge the relevance and efficiency of a
decomposition in finding “natural clusters”. In particular, when
C
is obtained from
a decomposition
C
by merging two clusters
C
i
The modularity value
Q
C
,
(
)
C
j
, the modularity values
Q
C
and
can be used to judge whether the decomposition
C
is “better” than
C
(with
respect to
Q
). Let
C
)
(
Q
C
)
−
=
(
(
)
denote the increase in
Q
of this merging
operation on clusters
C
i
and
C
j
(which may be negative).
Newman's method is agglomerative, i.e., we begin with a decomposition
C
such
that clusters correspond to singleton sets containing a single node; larger clusters
are then formed by aggregating smaller ones.
Δ
j
Q
Q
Q
C
i
,
=(
,
,...,
C
|
V
|
)
1. Begin with a decomposition
C
, where each cluster
C
i
contains
a single node (and conversely, each node is included in a cluster).
2. Find the two clusters
C
i
C
1
C
2
,
C
j
with the largest
Δ
j
Q
values; merge these two
i
,
clusters.
3. Step 2 is repeated until a single cluster decomposition
C
=(
)
V
(containing all
nodes) is reached.
4. Return to the decomposition produced from a cut in the aggregation tree that
maximizes
Q
(i.e., the best cut in terms of
Q
).
Step 3 requires some explanation. The merging process may be described by a
tree to denote which clusters are merged and how clusters are nested. Each cluster
occupies a given level, depending on how far the cluster is from the root cluster
C
=
(
)
.A
cut
is obtained by selecting all the clusters at a given depth, for example,
d
.
The tree structure is designed such that clusters of a cut induce a decomposition
C
V
=
(
,
,...
)
. Step 3 thus consists of selecting the cut with the maximum modularity
among all possible cuts.
C
1
C
2
9.3.2
The Betweenness Centrality Method
The betweenness centrality method was developed by Newman and Girvan (
2004
)
based on edge betweenness centrality (see
Brandes
,
2001
).
Let
G
be a weighted graph: for the example considered, an integer
attribute is assigned to the edges that correspond to passenger traffic. We then
compute the weight of an edge by taking the inverse of the number of passengers.
Low weights correspond to a smaller “distance” between the nodes. The weights
may then be used to compute weights for paths in the graph by summing the weights
of the edges along a path. The (weighted) betweenness centrality metric of an edge
e
represents the number of weighted shortest paths containing this edge. A low
BC
=(
V
,
E
)
(
e
)
value suggests that
e
is likely to be in a community, whereas a high
BC
(
e
)
value
suggests that
e
is a mandatory passageway connecting distinct communities.
Search WWH ::
Custom Search