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.
Search WWH ::




Custom Search