See also Cluster validation for general clustering validation.

• Rand index
  • Omega index

Given ground truth, Mutual information is often used. An important, overlooked question is how good the ground truth is. Some work about tagged networks[^1][^2][^3].

Statistical significance of communities: http://www.pnas.org/content/108/18/7321.short ; http://www.plosone.org/article/info%3Adoi%2F10.1371%2Fjournal.pone.0018961

Overlapping community structure makes the problem harder. For instance, Mutual information should be extended to covers. There are two proposals[^4][^5]. There are other suggestions: using conductance of boundary nodes[^6].

An approach to use data[^7].

References #

• http://www.cse.chalmers.se/~moradi/Lic/SEA.pdf (http://sea2012.labri.fr/index.php?n=Main.Papers)
• http://arxiv.org/abs/1006.0375 - Information theoretic model validation for clustering

How can we define statistical significance? What will be the proper null models for community structure?

• http://pre.aps.org/abstract/PRE/v81/i4/e046110 - Statistical significance of communities in networks
  • http://arxiv.org/abs/1012.2363 - Finding statistically significant communities in networks
• http://prl.aps.org/abstract/PRL/v105/i22/e220601 - Significance Analysis and Statistical Mechanics: An Application to Clustering
• http://arxiv.org/abs/1110.0305 - Significant communities in large sparse networks

There are approaches to use online social network services such as Facebook (http://fellows-exp.com/).

• Comparing network covers using mutual information
• Defining and Evaluating Network Communities based on Ground-truth

• Community detection: effective evaluation on large social networks

  • [[https://github.com/conradlee/network-community-benchmark]]
  • http://sociograph.blogspot.com/2013/11/facebook-benchmark-utility-released-on.html

• A revisit to evaluating accuracy of community detection using the normalized mutual information

[^1]: Palla, Gergely; Farkas, Illés J; Pollner, Péter; Derényi, Imre; Vicsek, Tamás (2008). "Fundamental statistical features and self-similar properties of tagged networks". New Journal of Physics 10 (12): 123026. doi:10.1088/1367-2630/10/12/123026. ISSN 1367-2630

[^2]: Pollner, Péter; Palla, Gergely; Vicsek, Tamás (2010). "Clustering of tag-induced subgraphs in complex networks". Physica A: Statistical Mechanics and its Applications 389 (24): 5887–5894. doi:10.1016/j.physa.2010.09.012. ISSN 03784371.

[^3]: Tibély, Gergely; Pollner, Péter; Vicsek, Tamás; Palla, Gergely (2012). "Ontologies and tag-statistics". New Journal of Physics 14 (5): 053009. doi:10.1088/1367-2630/14/5/053009. ISSN 1367-2630.

[^4]: Lancichinetti, Andrea; Fortunato, Santo; Kertész, János (2009). "Detecting the overlapping and hierarchical community structure in complex networks". New Journal of Physics 11 (3): 033015. doi:10.1088/1367-2630/11/3/033015. ISSN 1367-2630.

[^5]: "Template:Citation error". http://arxiv.org/abs/1202.0425.

[^6]: "Evaluating Overlapping Communities with the Conductance of their Boundary Nodes". http://arxiv.org/abs/1206.3992.

[^7]: "Benchmarking community detection methods on social media data". http://arxiv.org/abs/1302.0739.

Incoming Links #

Related Articles (Article 0) #

• Cluster validation
• Community structure
• Rand index
• Similarity

Suggested Pages #

• 0.404 Clustering comparison
• 0.175 Network similarity
• 0.071 Clustering
• 0.037 Pajek
• 0.037 Dynamic community structure
• 0.025 Community detectability
• 0.025 Community
• 0.019 Community evolution
• 0.019 Stochastic block model
• 0.018 Link prediction
• More suggestions...