P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-06 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 17:15
6.6 Exercises 177- Modularity can be defined as
Q=1
2 m∑
ij[
Aij−didj
2 m]
δ(ci,cj), (6.52)whereciandcjare the communities forviandvj, respectively.
δ(ci,cj) (Kronecker delta) is 1 whenviandvjboth belong to the
same community (ci=cj), and 0 otherwise.
What is the range [α 1 ,α 2 ] for Q values? Provide examples for both
extreme values of the range and cases where modularity becomes
zero.
What are the limitations for modularity? Provide an example where
modularity maximization does not seem reasonable.
Find three communities in Figure6.8by performing modularity
maximization.- For Figure6.8:
Compute Jaccard and Cosine similarity between nodesv 4 and
v 8 , assuming that the neighborhood of a node excludes the node
itself.
Compute Jaccard and Cosine similarity when the node is included in
the neighborhood.
Community Evolution- What is the upper bound on densification factorα? Explain.
Community Evaluation- Normalized mutual information (NMI) is used to evaluate commu-
nity detection results when the actual communities (labels) are known
beforehand.
What are the maximum and minimum values for the NMI? Provide
details.
Explain how NMI works (describe the intuition behind it). - Compute NMI for Figure6.15.
- Why is high precision not enough? Provide an example to show that
both precision and recall are important. - Discuss situations where purity does not make sense.