The discovery of underlying community structures plays a significant role in online social network (OSN) analysis. Many previous methods suffer from inaccuracy or incompleteness in community descriptions because of the multiple factors affecting OSNs and the high computational complexity caused by the large scale of these networks. We present a new community detection approach that focuses on two aspects. First, it relies on a combination of user interests and cohesiveness in describing community structures. Second, it introduces a multi-level community discovery algorithm for large-scale OSN datasets. The algorithm consists of three steps: (1) network coarsening based on the combination of two categories of properties, (2) stochastic inference to find an initial community assignment over the coarsest network and (3) projection and refinement of this assignment to obtain the final community detection result by solving a semi-supervised learning problem. The combination of user interests and cohesiveness leads to a complete and well-interpreted description of the communities embedded in OSNs, and the multi-level algorithm speeds up the computation process and improves the likelihood of finding the global optimal solution by reducing the parameter space. Experiments conducted on both synthetic and real datasets demonstrate the effectiveness and efficiency of our method.
KumarRNovakJTomkinsA. Structure and evolution of online social networks. In: YuPHanJFaloutsosC (eds) Link mining: models, algorithms, and applications. Berlin: Springer, 2010, pp. 337–357.
2.
AhnHParkJH. The structural effects of sharing function on Twitter networks: focusing on the retweet function. J Inf Sci2015; 41(3) 354–365.
3.
Hosseini-PozvehMZamanifarKNaghsh-NilchiAR. A community-based approach to identify the most influential nodes in social networks. J Inf Sci. Epub ahead of print 1February2016. DOI: 10.1177/0165551515621005.
4.
LancichinettiAFortunatoS. Community detection algorithms: a comparative analysis. Phys Rev E Stat Nonlin Soft Matter Phys2009; 80(2): 2142–2152.
5.
MisloveAMarconMGummadiKP. Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, San Diego, CA, 23–26 October 2007, pp. 29–42. New York: ACM.
6.
SalehiMRabieeHR. A measurement framework for directed networks. IEEE J Sel Area Commun2014; 31: 1007–1016.
7.
KwakHLeeCParkH. What is Twitter, a social network or a news media? In: Proceedings of the 19th international conference on world wide web, Raleigh, NC, 26–30 April 2010, pp. 591–600. New York: ACM.
8.
FortunatoS. Community detection in graphs. Phys Rep2009; 486(3–5): 75–174.
9.
MalliarosFDVazirgiannisM. Clustering and community detection in directed networks: a survey. Phys Rep2013; 533: 95–142.
10.
PapadopoulosSKompatsiarisYVakaliA. Community detection in Social Media. Data Min Knowl Discov2012; 24: 515–554.
11.
NewmanMEJGirvanM. Finding and evaluating community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys2004; 69(2 Pt 2): 026113.
12.
KernighanBWLinS. An efficient heuristic for partitioning graphs. Bell Syst Tech J1970; 49: 291–307.
13.
HastieTTibshiraniRFriedmanJ. The elements of statistical learning. New York: Springer, 2000.
14.
LuxburgUV. A tutorial on spectral clustering. Stat Comput2007; 17: 395–416.
15.
NewmanMEJ. Fast algorithm for detecting community structure in networks. Phys Rev E Stat Nonlin Soft Matter Phys2004; 69: 066133.
16.
PallaGDerényiIFarkasI. Uncovering the overlapping community structure of complex networks in nature and society. Nature2005; 435: 814–818.
17.
BlondelVDGuillaumeJLLambiotteR. Fast unfolding of communities in large networks. J Stat Mech Theory Exp2008; 2008(10): 155–168.
18.
NicosiaVMangioniGCarchioloV. Extending the definition of modularity to directed graphs with overlapping communities. J Stat Mech Theory Exp2008; 2009(3): 3166–3168.
19.
GregoryS. Finding overlapping communities in networks by label propagation. New J Phys2009; 12(10): 2011–2024.
20.
XieJSzymanskiBK. Towards linear time overlapping community detection in social networks. In: TanPNChawlaSHoCK. (eds) Advances in knowledge discovery and data mining (Lecture notes in computer science). Berlin: Springer, 2012, pp. 25–36.
21.
RosvallMBergstromCT. Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems. Plos ONE2011; 6: e18209.
22.
ChenWLiuZSunX. A game-theoretic framework to identify overlapping communities in social networks. Data Min Knowl Discov2010; 21(2): 224–240.
23.
McDaidAHurleyN. Detecting highly overlapping communities with model-based overlapping seed expansion. In: Proceedings of the 2010 international conference on advances in social networks analysis and mining, Odense, 9–11 August 2010, pp. 112–119. New York: IEEE Computer Society.
24.
BallBKarrerBNewmanMEJ. Efficient and principled method for detecting communities in networks. Phys Rev E Stat Nonlin Soft Matter Phys2011; 84(3 Pt 2): 109–134.
HofmannT. Probabilistic latent semantic indexing. In: Proceedings of the international ACM SIGIR conference on research and development in information retrieval, Berkeley, CA, 15–19 August 1999.
NewmanMEJLeichtEA. Mixture models and exploratory analysis in networks. Proc Natl Acad Sci USA2006; 104(23): 9564–9569.
29.
YangTJinRChiY. Combining link and content for community detection: a discriminative approach. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, Paris, 28 June–1 July 2009, pp. 927–936. New York: ACM.
30.
YangTChiYZhuSGongY. Directed network community detection: a popularity and productivity link model. In: Siam international conference on data mining, SDM 2010, Columbus, Ohio, USA, 29 April–May 1 2010, pp. 742–753. DBLP.
31.
ZhangHQiuBGilesCL. An LDA-based community structure discovery approach for large-scale social networks. In: Proceedings of the IEEE intelligence and security informatics, New Brunswick, NJ, 23–24 May 2007, pp. 200–207. New York: IEEE.
32.
NowickiKSnijdersTAB. Estimation and prediction for stochastic blockstructures. J Am Stat Associ2001; 96: 1077–1087.
33.
ShenHWChengXQGuoJF. Exploring the structural regularities in networks. Phys Rev E Stat Nonlin Soft Matter Phys2011; 84(5 Pt 2): 1175–1206.
GyengeÁSinkkonenJBenczúrAA. An efficient block model for clustering sparse graphs. In: Proceedings of workshop on mining & learning with graphs in conjunction with SIGKDD, Washington, DC, USA, 25–28 July 2010, pp. 62–69. ACM.
36.
KarypisGKumarV. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput1998; 20: 359–392.
37.
HendricksonBLelandRW. A multi-level algorithm for partitioning graphs. In: Proceedings of the IEEE/ACM SC95 conference, San Diego, CA, 8 December 1995, p. 28. New York: IEEE.
38.
WangFZhangC. Fast multilevel transduction on graphs. In: Proceedings of the 7th SIAM conference on data mining (SDM), Minneapolis, MN, 26–28 April 2007.
39.
LancichinettiAFortunatoS. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys Rev E Stat Nonlin Soft Matter Phys2009; 80(2): 145–148.
