Community detection aims to discover cohesive groups in which people connect with each other closely in social networks. A variety of methods have been proposed to detect communities in social networks. However, there is still few work to make a comparative study on those methods. In this paper, we first introduce and compare several representative methods on community detection. Then we implement those methods with python and make a comparative analysis on different real world social networking data sets. The experimental results have shown that GN algorithm is suitable for small networks, while LPA algorithm has a better scalability. FU algorithm is of the best stability. This work could help researchers to understand the ideas of community detection methods better and select appropriate method on demand more easily.
SuZ., XuQ. and QiQ., Big data in mobile social networks: A qoeoriented framework, IEEE Network30(1) (2016), 52–57.
2.
ZhaoZ., LiC., ZhangY., HuangJ.Z., LuoJ., FengS. and FanJ., Identifying and analyzing popular phrases multi-dimensionally in social media data, International Journal of Data Warehousing & Mining11(3) (2015), 98–112.
3.
ZhaoZ., ZhangY., LiC., NingL. and FanJ., A system to manage and mine microblogging data, Journal of Intelligent & Fuzzy Systems33(1) (2017), 1–11.
4.
BuZ., ZhangC., XiaZ. and WangJ., A fast parallel modularity optimization algorithm (fpmqa) for community detection in on-line social network, Knowledge-Based Systems50(3) (2013), 246–259.
5.
XuY., XuH. and ZhangD., A novel disjoint community detection algorithm for social networks based on backbone degree and expansion, Expert Systems with Applications42(21) (2015), 8349–8360.
6.
ZhanQ., ZhangJ., YuP. and XieJ., Community detection for emerging social networks, WorldWideWeb-internet & Web Information Systems (2017), 1–33.
7.
FortunatoS., Community detection in graphs, Physics Reports486(35) (2010), 75–174.
8.
ZhaoZ., FengS., WangQ., HuangJ.Z., WilliamsG.J. and FanJ., Topic oriented community detection through social objects and link analysis in social networks, Knowledge-Based Systems26 (2012), 164–173.
9.
XuY., XuH., ZhangD. and ZhangY., Finding overlapping community from social networks based on community forest model, Knowledge-Based Systems109 (2016), 238–255.
10.
LiuD., JinD., HeD., HuangJ., YangJ. and YangB., Community mining in complex networks, Journal of Computer Research & Development50(10) (2013), 2140–2154.
11.
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) (2001), 7821–7826.
12.
NewmanM.E. and GirvanM., Finding and evaluating community structure in networks, Physical Review E Statistical Nonlinear & Soft Matter Physics69(2) (2004), 026113.
13.
AroraS., RaoS. and VaziraniU., Expander flows, geometric embeddings and graph partitioning, in: Thirty-Sixth ACM Symposium on Theory of Computing, 2004, pp. 222–231.
DhillonI.S., GuanY. and KulisB., Weighted graph cuts without eigenvectors a multilevel approach, IEEE Transactions on Pattern Analysis & Machine Intelligence29(29) (2007), 1944–1957.
16.
AndersenR., FanC. and LangK., Local graph partitioning using pagerank vectors, in: IEEE Symposium on Foundations of Computer Science, 2006, pp. 475–486.
17.
RadicchiF., CastellanoC., CecconiF., LoretoV. and ParisiD., Defining and identifying communities in networks, Proceedings of the National Academy of Sciences of the United States of America101(9) (2004), 2658–2663.
18.
LeskovecJ., LangK.J. and MahoneyM.W., Empirical comparison of algorithms for network community detection, (2010), pp. 631–640.
19.
TylerJ.R., WilkinsonD.M. and HubermanB.A., E-Mail as Spectroscopy: Automated Discovery of Community Structure within Organizations, SpringerNetherlands, 2003.
20.
ClausetA., NewmanM.E. and MooreC., Finding community structure in very large networks, Physical Review E Statistical Nonlinear & Soft Matter Physics70(2) (2004), 066111.
21.
NewmanM.E.J., Fast algorithm for detecting community structure in networks, Physical Review E Statistical Nonlinear & Soft Matter Physics69(6) (2004), 066133.
22.
BlondelV.D., GuillaumeJ.L., LambiotteR. and LefebvreE., Fast unfolding of communities in large networks, Journal of Statistical Mechanics Theory & Experiment2008(10) (2008), 155–168.
23.
RaghavanU.N., AlbertR. and KumaraS., Near linear time algorithm to detect community structures in large-scale networks, Physical Review E Statistical Nonlinear & Soft Matter Physics76(3) (2007), 036106.
24.
BarberM.J. and ClarkJ.W., Detecting network communities by propagating labels under constraints, Physical Review E Statistical Nonlinear & Soft Matter Physics80(2) (2009), 026129.
25.
RosvallM. and BergstromC.T., Maps of information flow reveal community structure in complex networks, Proceedings of the National Academy of Sciences USA (2007), 1118–1123.
26.
NewmanM.E., Finding community structure in networks using the eigenvectors of matrices, Physical Review E Statistical Nonlinear & Soft Matter Physics74(3) (2006), 036104.
27.
WangF., LiT., WangX., ZhuS. and DingC., Community discovery using nonnegative matrix factorization, Data Mining and Knowledge Discovery22(3) (2011), 493–521.
28.
YangJ. and LeskovecJ., Overlapping community detection at scale: A nonnegative matrix factorization approach, in: ACM International Conference onWeb Search and Data Mining, 2013, pp. 587–596.
29.
BakerC.G., HetmaniukU.L., LehoucqR.B. and ThornquistH.K., Anasazi software for the numerical solution of largescale eigenvalue problems, ACM Transactions on Mathematical Software36(3) (2009), 1–23.
