With the growth of Internet and computer knowledge, more and more persons connect socially. People communicate with each other and express their views on social media, which may form a complex network of association. Entities in the social networks create a “relation structure” through several connections which produces a huge amount of information. This “relation structure” is the group or community that we are interested in research. Community detection is very imperative to disclose the structure of social networks, dig to people`s views, analyze the information dissemination and grasp as well as control the public sentiment. In recent years, with community detection becoming an essential field of social networks analysis, a large number of the academic literature suggested several approaches to community detection. In this paper, we first describe the concepts of the social network, community, community detection and criterions of community quality. Then we classify the methods of community detection into the following categories. And at last, we summarize and discuss these methods as well as the potential future directions of community detection.

Social Network Analysis, Community Detection, Graph Data, Massive Datasets, Disjoint Community Detection

[1] J. Bruhn, “The sociology of community connections,” Springer Science+Business Media B.V., 2011.
[2] S. Fortunato, “Community detection in graphs,” Physics Reports, vol. 486(3-5), p. 75 – 174, 2010.
[3] A. Lancichinetti and S. Fortunato, “Community detection algorithms: A comparative analysis,” Phys. Rev. E, 2009.
[4] L. G. S. R. J. H. R. S. K. P. S. Harenberg, G. Bello and N. Samatova, “Community detection in large-scale networks: a survey and empirical evaluation,” Wiley Interdisciplinary Reviews: Computational Statistics, vol. 6(6), p. 426–439, 2014.
[5] S. L. B.W. Kernighan, “An efficient heuristic procedure for partitioning graphs,” Bell System Technical Journal, vol. 49(2), pp. 291–307, 1970.
[6] A. Pothen, “Graph partitioning algorithms with applications to scientific computing,” Technical report.
[7] B. Bollob´as, “Modern graph theory,” Graduate texts in mathematics, 1998.
[8] J. Shi and J. Malik, “Normalized cuts and image segmentation,” IEEE Trans. Pattern Anal. Mach. Intel., vol. 22(8), p. 888–905, 2000.
[9] E. R. Barnes, “An algorithm for partitioning the nodes of a graph,” Technical Report RC 08690, 1981.
[10] W. E. Donath and A. J. Hoffman, “Lower bounds for the partitioning of graphs,” IBM J. Res. Dev., vol. 17(5), p. 420–425, 1973.
[11] A. Y. Ng and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” In Advances in Neural Information Processing Systems, vol. 14, p. 849–856, 2001.
[12] B. Nadler and M. Galun, “Fundamental limitations of spectral clustering methods,” Advances in Neural Information Processing Systems, vol. 19, 2007.
[13] J. B. MacQueen, “Some methods for classification and analysis of multivariate observations,” In L. M. L. Cam and J. Neyman, editors, Proc. of the fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281–297, 1967.
[14] J. C. Bezdek, “Pattern recognition with fuzzy objective function algorithms,” 1981.
[15] A. Hlaoui and S. Wang, “Median graph computation for graph clustering,” Soft Computing, vol. 10(1), pp. 47–53, 2006.
[16] R. T. T. Hastie and J. Friedman, “The elements of statistical learning,” Springer Series in Statistics, 2001.
[17] M. M. M. J. Rattigan and D. Jensen, “Graph clustering with network structure indices,” In Proceedings of the 24th International Conference on Machine Learning, ICML ’07, New York, NY, USA, ACM, pp. 783–790, 2007.
[18] D. M. W. J. R. Tyler and B. A. Huberman, “E-mail as a spectroscopy: Automated discovery of community structure within organizations,” In M. Huysman, E. Wenger, and V. Wulfs, editors, Proceedings of the First Iternational Conference on Communities and Technologies., 2003.
[19] M. E. J. Newman and M. Girvan, “Finding and evaluating community structure in networks,” Physical Review Edition, vol. 69, 2004.
[20] M. E. J. Newman, “Fast algorithm for detecting community structure in networks,” Phys. Rev. Edition, vol. 69:066133, 2004.
[21] B. Hughes, “Random walks and random environments: Random walks,” Number v. 1 in Oxford science publications, 1995.
[22] H. Zhou, “Distance, dissimilarity index, and network community structure,” Physical Review Edition, vol. 67(6):061901, 2003.
[23] R. Winkler, “An introduction to bayesian inference and decision,” International series in decision processes, 1972.
[24] M. E. J. Newman and E. A. Leicht, “Mixture models and exploratory analysis in networks,” Proceedings of the National Academy of Sciences, vol. 104(23), p. 9564–9569, 2007.
[25] R. A. U. N. Raghavan and S. Kumara, “Near linear time algorithm to detect community structures in large-scale networks,” Physics review Edition, vol. 76:036106, 2007.
[26] W. Rand, “Objective criteria for the evaluation of clustering methods,” Journal of the American Statistical Association, vol. 66(336):, pp. 846–850, 1971.
[27] A. D. J. Leskovec, K. J. Lang and M. W. Mahoney, “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters,” Internet Mathematics, vol. 6(1), p. 29–123, 2009.