Information Technology Reference
In-Depth Information
Fig. 9.1
Neighborhoods in
the Jaccard method
In contrast to Newman's modularity method, the betweenness centrality method
is
divisive
. The process starts with a decomposition containing a single cluster
C
=
(
that is split into smaller clusters by removing edges before iterating on the newly
created clusters.
V
)
1. Begin with a single cluster decomposition
C
=(
V
)
.
(a) Compute betweenness centrality on the edges.
(b) Remove the edge with the maximum value. If edge removal disconnects a
cluster into two smaller clusters, then update the decomposition.
2. Repeat steps 1(a) and 1(b) until there are no more edges to remove.
3. Return the decomposition induced by a cut in the aggregation tree that maximizes
Q
(i.e., the best cut in terms of
Q
).
This divisive process may be again encoded using a binary tree to indicate the
nesting of the clusters. Additionally, the edge removal operation requires that the
betweenness centrality of the remaining edges be updated.
9.3.3
The Neighbors Method
The Jaccard and strength methods were developed by Auber, Chiricota, Jourdan,
and Melançon (
2003
) based on the extension of a metric designed by Jaccard (
1901
),
which was later generalized to weighted networks (
Amiel, Rozenblat, & Melançon
,
2005
).
The (weighted) “Jaccard metric” of an edge represents the (weighted) neighbor-
hood similarity of the extremities of the edge. Assume that we are given a weight
function on both nodes and edges, i.e., we are given the values
ω
(
v
)
and
ω
(
e
)
for
all nodes
v
. In our example, the weight
of a node would typically be the passenger traffic going through that node.
Let
∈
V
and edges
e
∈
E
of a graph
G
=(
V
,
E
)
denote the weight of the node
v
(passenger traffic going through node
v
).
Recall that
N
ω
(
v
)
(
v
)
and
N
(
u
)
denote the neighborhoods of
v
and
u
, respectively, in
G
(see Fig.
9.1
).
The weighted “Jaccard metric” of an edge
e
∑
n
∈
N
(
u
)
∩
N
(
v
)
ω
(
n
)
∑
n
∈
N
(
u
)
∪
N
(
v
)
ω
(
=(
u
,
v
)
is
jac
(
e
)=
.
n
)
Ahigh
jac
value suggests that
e
is likely to be in a community. The Jaccard
method is also a divisive method that maximizes
Q
.
(
e
)
Search WWH ::
Custom Search