Biology Reference
In-Depth Information
LS i
TS
2
DS i
TS
NC
Q s =
(11.6)
i =1
with IS i =
u,v∈V i
S ( u,v ) ,DS i =
u∈V i ,v∈V
S ( u,v ) and TS =
u,v∈V
S ( u,v ),
where NC is the number of clusters, IS i is the total similarity of vertices within
cluster i ; DS i is the total similarity between vertices in cluster i and any vertices
in the graph; TS is the total similarity between any two vertices in the graph;
S ( u,v ) is defined in (11.5); V is the vertex set of the graph and V i is the vertex
set of cluster i .
If we define
δ ( u,i )= 0 if u/
cluster i,
1 if u
cluster i,
then (11.6) is written as
u v S ( u, v ) δ ( u, i ) δ ( v, i )
2
u v S ( u, v ) δ ( u, i )
NC
u v S ( u, v )
u v S ( u, v )
Q s =
.
(11.7)
i =1
In other words, Q S is a measure of the similarity of a partition of the network
versus the similarity of the same partition if the network's vertices were randomly
connected. As with Newman's modularity, if we put all vertices either into one
cluster or place them in clusters randomly, Q S will be 0.
Referring again to the type II graph in Fig. 11.1 (b), the similarity between
the “hub” vertex ' a ' and its neighbors is quite low, despite the hub's high degree.
Likewise, the similarity between the “outlier” vertex ' h ' and its lone neighbor is
low. Table 11.1 summarizes Q N and Q S respectively for several possible parti-
tioning of the network in Fig. 11.2 (b).
Table 11.1. Q N and Q S for different clustering structures
Clustering Schedule
Q N
Q S
All vertices in one cluster
0.0
0.0
{a}, {b, c,d}, {e,f, g}, {h}
0.119835
0.343714
{
a, b, c,d
}
,
{
e,f, g
}
,
{
h
}
0.177686
0.312469
{a, b, c,d}, {e,f, g,h}
0.227273
0.289307
{b, c,d}, {a, e, f, g}, {h}
0.185950
0.368656
{b, c,d}, {a, e, f, g, h}
0.214876
0.321978
We acknowledge that preferring one graph partitioning over another may be
subjective; however, we think the original modularity definition classifies the
hub node ' a ' into the wrong cluster
and fails to segregate the out-
liner node ' h '. The proposed Similarity-based Modularity successfully detects the
{
a,b,c,d
}
Search WWH ::




Custom Search