Information Technology Reference
In-Depth Information
they are in the same community. Here a normalized similarity function extended from
Jaccard index is defined as follows.
|
Γ
(
μ
)
Γ
(
ν
)
|
sm
(
μ
,
ν
)
=
(2)
|
Γ
(
μ
)
Γ
(
ν
)
|
•
DEFINITION 3 (
-NEIGHBORHOOD)
ε
A minimum similarity threshold is used to be a cut to the similarity value. In other
words, a node's
-neighborhood is selected from its neighbors through threshold
.
ε
ε
N
(
ν
)
=
{
ω
∈
Γ
(
ν
)
|
sm
(
ν
,
ω
)
≥
ε
}
(3)
ε
•
DEFINITION 4 (CORE NODE)
Core node represents a special node which have enough members in
ε
-neighborhood.
Cluster(core area) are grown up from the core node. Here
represents the minimum
μ
threshold of
-neighborhood of the core node.
ε
CORE
(
ν
)
⇔
|
N
(
ν
)
|
≥
μ
(4)
,
ε
μ
ε
•
DEFINITION 5 (DIRECT STRUCTURE REACHABILITY)
Core node is expanded to cluster(core area) according to the direct reach-ability rule
formulized in the following definition. Node
ω
is direct-connected to node
if and
ν
ω
ε
only if
ν
is a core node and
is in the
-neighborhood of
ν
.
DirREACH
(
ν
,
ω
)
⇔
CORE
(
ν
)
∧
ω
∈
N
(
ν
)
(5)
ε
,
μ
ε
,
μ
ε
2.2
Clustering Algorithm
In this sub-section, a basic structural clustering algorithm that searches for core areas
and isolated nodes in a network is discussed.
Firstly, all nodes are labeled as unclassified. For each node
that is unclassified,
ν
if node
is a core node, a new cluster_ID will be generated and all nodes which
satisfy direct reach-ability rule will be inserted into a seed queue, otherwise node
v
will be labeled as NOISE which means isolated node. Moreover, the cluster_ID will be
assigned to all the nodes appeared in the seed queue.
Secondly, node
y
is pick up from the top of the queue. If node
y
is a core node,
its unclassified neighborhood which satisfy the direct reach-ability rule will be added
to the queue. Then remove node
y
from the queue. The operation will be repeated
until the queue is empty.
Finally, the network is partitioned into some clusters(core areas) and isolated nodes.
The pseudocode of the algorithm is depicted as follows.
ν
