Image Processing Reference
In-Depth Information
mobile-data collection campaign to derive community structures in multi-layer graphs and
to make new link recommendations.
9. Appendix: Clustering evaluation measures
Let's define
C
=
{
c
1
,...,
c
M
}
and
Ψ
=
{
ψ
1
,...,.
ψ
M
}
as partitions containing detected clusters
c
i
and the ground truth clusters
ψ
i
, respectively. Quality of clustering algorithms may be
evaluated by different measures (Manning et al, 2008), in particular:
•Randindex:
Tru e Po s i t i ve
+
Tru e Ne g a t i ve
RI
=
Tru e Ne g a t i ve
;
(38)
Tru e Po s i t i ve
+
FalsePositive
+
FalseNegative
+
•Pu tytes :
M
m
=
1
max
1
n
(Ψ
)=
|ψ
m
∩
c
j
|
Purity
,
C
;
(39)
j
•
Normalized mutual information:
2
I
(
Ψ
,
C
)
NMI
(
C
,
Ψ
)=
,
(40)
H
(
Ψ
)+
H
(
C
))
where the mutual information
I
(
C
1
,
C
2
)
between the partitions
C
1
and
C
2
and their
(
C
i
)
entropies
H
are
log
nc
m
1
,
m
2
n
m
1
n
m
2
,
H
log
n
m
i
n
;
M
m
1
M
m
2
M
m
i
c
m
1
,
m
2
n
n
m
i
n
I
(
C
2
,
C
2
)=
(
C
i
)=
−
(41)
n
is total number of data points;
c
m
1
,
m
2
is the number of common samples in the
m
1
-th
cluster from
C
1
and the
m
2
-th cluster in the partition
C
2
;
n
m
i
is the number of samples in
the
m
i
-th cluster in the partition
C
i
. According to (41), max
NMI
(
C
1
,
C
2
)=
1if
C
1
=
C
2
.
10. References
Acebrón, J., Bonilla, L., Pérez-Vicente, C., Ritort, F., Spigler, R. (2005). The Kuramoto model: A
simple paradigm for synchronization phenomena.
Reviews of Modern Physics
,77(1),
pp. 137-185.
Albert, R. & Barabási, A.-L. (2002). Statistical mechanics of complex networks.
Reviews of
Modern Physics
, 74, pp. 47-97.
Arenas A., Díaz-Guilera, A., Pérez-Vicente, C. (2006). Synchronization reveals topological
scales in complex networks.
Physical Review Letters
, 96, 114102.
Arenas, A., Diaz-Guilera, A., Kurths, J., Moreno, Y. and Zhou, C. (2008). Synchronization in
complex networks,
Physics Reports
, 469, pp. 93-153.
Blondel, V., Guillaume, J.-L., Lambiotte, R. and Lefebvre, E. (2008). Fast unfolding of
communites in large networks.
Journal of Statistical Mechanics: Theory and Experiment
,
vol. 1742-5468, no. 10, pp. P10008+12.
Evans,
T. S. and Lambiotte R. (2009).
Line Graphs,
Link Partitions and Overlapping
Communities.
Physical Review
, E 80 016105.