Modularity Evaluation (ME) is usually used in community detection for evaluating the disjoint and overlapping communities. In this paper, two obvious defects of ME are revealed and proved, including the non-decreasing contribution of isolated nodes to modularity and lacking of appropriate measures on overlapping community. We also propose a new evaluation criterion, the USI-AUC, which is the Area Under the Curve (AUC), originated from link-prediction of Uniform-Structure-Information (USI) model. We test the new criterion on various datasets, and find that such criterion can avoid the issues exposed in ME.
GirvanM. and NewmanM.E.J., Community structure in social and biological networks,Proceedings of the National Academy of Sciences of the United States of America99(12) (2002), 7821–7826.
2.
FortunatoS., Community detection in graphs, Physics Reports486(3–5) (2009), 75–174.
3.
ChengL.KotoulasS.WardT.E and TheodoropoulosG., Robust and skew-resistant parallel joins in shared-nothing systems, in: ACM International Conference on Conference on Information and Knowledge Management, 2014, pp. 1399–1408.
4.
LiZ.WangR.S.ZhangS. and ZhangX.S., Modularity and community detection in bipartite networks, Computer Science, 2015.
5.
NewmanM.E.J., Fast algorithm for detecting community structure in networks, Physical Review E Statistical Nonlinear & Soft Matter Physics69(6) (2004), 066133–066133.
6.
NewmanM.E.J., Community detection in networks: Modularity optimization and maximum likelihood are equivalent, 2016.
7.
LangoneR.AlzateC. and SuykensJ.A.K., Kernel spectral clustering for community detection in complex networks, Proc of the IEEE World Congress on Computational Intelligence20 (2012), 1–8.
8.
HabashiS.GhanemN.M. and IsmailM.A., Enhanced community detection in social networks using active spectral clustering, in: The ACM Symposium2016, pp. 1178–1181.
9.
ChengQ.LiuZ.HuangJ. and ZhuC., Hierarchical clustering based on hyper-edge similarity for community detection, in: Ieee/wic/acm International Conferences on Web Intelligence and Intelligent Agent Technology, 2012, pp. 238–242.
10.
RaghavanU.N., R Albert and S Kumara, Near linear time algorithm to detect community structures in large-scale networks, Physical Review E Statistical Nonlinear & Soft Matter Physics76(3 Pt 2) (2007).
11.
LiuX. and MurataT., Advanced modularity-specialized label propagation algorithm for detecting communities in networks, Physica A Statistical Mechanics & Its Applications389(7) (2010), 1493–1500.
GregoryS., Finding overlapping communities in networks by label propagation, New Journal of Physics12(10) (2009), 2011–2024.
14.
AhnY.Y.BagrowJ.P. and LehmannS., Link communities reveal multiscale complexity in networks, Nature466(7307) (2010), 761–764.
15.
LancichinettiA.FortunatoS. and KertészJ., Detecting the overlapping and hierarchical community structure of complex networks, New Journal of Physics11(3) (2009), 19–44.
CollinsL.M. and DentC.W., Omega: A general formulation of the rand index of cluster recovery suitable for non-disjoint solutions, Multivariate Behavioral Research23(2) (1988), 231–242.
18.
GregoryS., Fuzzy overlapping communities in networks, Journal of Statistical Mechanics Theory & Experiment2(2) (2011), P02017.
19.
PizzutiC., Ga-net: A genetic algorithm for community detection in social networks, in: Parallel Problem Solving From Nature – PPSN X, International Conference Dortmund, Germany, September 13–17, 2008, Proceedings, 2008, pp. 1081–1090.
20.
NicosiaV.MangioniG.CarchioloV. and MalgeriM., Extending modularity definition for directed graphs with overlapping communities, 2008.
21.
ShenH.ChengX.CaiK. and HuM.B., Detect overlapping and hierarchical community structure in networks, Physica A Statistical Mechanics & Its Applications388(8) (2009), 1706–1712.
22.
ShenH.W.ChengX.Q. and GuoJ.F., Quantifying and identifying the overlapping community structure in networks, Journal of Statistical Mechanics Theory & Experiment2009(7) (2009), 07042.
23.
ZacharyW.W., An information flow model for conflict and fission in small groups, Journal of Anthropological Research33(4) (1977), 473.
24.
XieJ.KelleyS. and SzymanskiB.K., Overlapping community detection in networks: The state-of-the-art and comparative study, Acm Computing Surveys45(4) (2013), 115–123.
25.
DanonL.DÃazguileraA.DuchJ. and ArenasA., Comparing community structure identification, Journal of Statistical Mechanics Theory & Experiment2005(9) (2005), 09008.
26.
Valverde-RebazaJ. and De Andrade LopesA., Exploiting behaviors of communities of twitter users for link prediction, Social Network Analysis and Mining3(4) (2013), 1063–1074.
27.
Valverde-RebazaJ.ValejoA.BertonL.De Paulo FaleirosT. and De Andrade LopesA., A naive bayes model based on overlapping groups for link prediction in online social networks, in: The Acm/sigapp Symposium on Applied Computing, 2015, pp. 1136–1141.
28.
SoundarajanS. and HopcroftJ., Using community information to improve the precision of link prediction methods, in: Proceedings of the 21st International Conference Companion on World Wide Web, 2012, pp. 607–608.
29.
AaronC.CristopherM. and NewmanM.E.J., Hierarchical structure and the prediction of missing links in networks, Nature453(7191) (2008), 98–101.
30.
HollandP.W.LaskeyK.B. and LeinhardtS., Stochastic blockmodels: First steps, Social Networks5(2) (1983), 109–137.
31.
AiroldiE.M.BleiD.M.FienbergS.E. and XingE.P., Mixed membership stochastic blockmodels, Journal of Machine Learning Research9(5) (2008), 1981–2014.
32.
HanleyJ.A. and McneilB.J., The meaning and use of the area under a receiver operating characteristic (roc) curve, Radiology143(1) (1982), 29–36.
33.
LusseauD.SchneiderK.BoisseauO.J.HaaseP.SlootenE. and DawsonS.M., The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behavioral Ecology & Sociobiology54(4) (2003), 396–405.
34.
MartelotE.L. and HankinC., Multi-scale community detection using stability as optimisation criterion in a greedy algorithm, 2011.
35.
RonhovdeP. and NussinovZ., Local resolution-limit-free potts model for community detection, Physical Review E Statistical Nonlinear & Soft Matter Physics81(2) (2010), 387–395.
36.
ShiJ. and MalikJ., Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence22(8) (2000), 888–905.
37.
HespanhaP., An efficient matlab algorithm for graph partitioning, 2004.
38.
ReichardtJ. and BornholdtS., Statistical mechanics of community detection, Physical Review E Statistical Nonlinear & Soft Matter Physics74(2) (2006).
39.
BlondelV.D..GuillaumeJ.L.LambiotteR. and LefebvreE., Fast unfolding of community hierarchies in large networks, J Stat Mech, abs/0803.0476, 2008.
40.
HuangJ.SunH.LiuY.SongQ. and WeningerT., Towards online multiresolution community detection in large-scale networks, Plos One6(8) (2011), 492–492.
41.
DanonL.Diaz-GuileraA. and ArenasA., Effect of size heterogeneity on community identification in complex networks, Journal of Statistical Mechanics Theory & Experiment2006(11) (2006), 11010.
42.
ArenasA.FernandezA. and GomezS., Analysis of the structure of complex networks at different resolution levels, New Journal of Physics10(5) (2008), 4656–4658.
43.
KnuthD.E., The stanford graphbase: a platform for combinatorial computing, in: Acm/sigact-Siam Symposium on Discrete Algorithms, 25–27 January 1993, Austin, Texas, 1993, pp. 41–43.
44.
ColemanJ. and MenzelH., The diffusion of innovation among physicians, Sociometry20(20) (1977), 253–269.
45.
KolaczykE.D., Statistical Analysis of Network Data, Springer New York, 2009.
46.
DuchJ. and ArenasA., Community detection in complex networks using extremal optimization, Physical Review E Statistical Nonlinear & Soft Matter Physics72(2 Pt 2) (2005), 986–1023.
47.
BandyopadhyayS.ChowdharyG. and SenguptaD., Focs: Fast overlapped community search, IEEE Transactions on Knowledge & Data Engineering27(11) (2015), 2974–2985.
48.
LancichinettiA.FortunatoS. and RadicchiF., Benchmark graphs for testing community detection algorithms, Physical Review E Statistical Nonlinear & Soft Matter Physics78(2) (2008), 046110.
49.
ChengL. and KotoulasS., Efficient skew handling for outer joins in a cloud computing environment, IEEE Transactions on Cloud Computing, 2015, p. 1.
