Sage Journals: Discover world-class research

Abstract

With the rapid development of social network, community detection has caught lots of researcher’s attention. However, the existing methods are difficult to solve mass data in growing large-scale networks. In this paper, a two-step method is proposed to cope with large-scale networks based on the construction of community tree and the $N$ -players cooperative game process. In the first stage, the community tree is constructed to initialize community detection by the similarity of nodes. Next, it performs greatly for $N$ -players cooperative game to adjust and ensure the remaining nodes or spare communities. For the transmission of the stored structure of community tree, $N$ -players cooperative game theory (NC-GT) also exhibits the excellent performance on runtime. We make the evaluations on three synthetic networks and four real-world networks and the main indicates are the modularity, NMI etc. The results show NC-GT has a stable and efficient performance on large-scale compared to other algorithms. Besides, the proposed community tree provides a more convenient way to research the flexible actions on nodes, which makes it more suitable for the dynamic networks.

Keywords

Large-scale social networks multi-stage community tree N-players cooperative game community detection

Get full access to this article

View all access options for this article.

References

Wasserman

and Faust

, Social network analysis: Methods and applications[M]. Cambridge university press, 1994.

Brandes

Borgatti

S.P.

and Freeman

L.C.

, Maintaining the duality of closeness and betweenness centrality[J], Social Networks 44 (2016), 153–159.

Wei

Luo

et al., Knowle: a semantic link network based system for organizing large scale online news events[J], Future Generation Computer Systems 43 (2015), 40–50.

Newman

M.E.J.

, Modularity and community structure in networks[J], Proceedings of the National Academy of Sciences 103(23) (2006), 8577–8582.

Blondel

V.D.

Guillaume

J.L.

Lambiotte

et al., Fast unfolding of communities in large networks[J], Journal of Statistical Mechanics: Theory and Experiment (10) (2008), P10008.

Rosvall

and Bergstrom

C.T.

, Maps of random walks on complex networks reveal community structure[J], Proceedings of the National Academy of Sciences 105(4) (2008), 1118–1123.

Qian

and Yue

, Incremental attribute reduction algorithm for big data using MapReduce[J], Journal of Computational Methods in Sciences and Engineering 16(3) (2016), 641–652.

Guimera

Sales-Pardo

and Amaral

L.A.N.

, Modularity from fluctuations in random graphs and complex networks[J], Physical Review E 70(2) (2004), 025101.

Duch

and Arenas

, Community detection in complex networks using extremal optimization[J], Physical review E 72(2) (2005), 027104.

10.

Khomami

M.M.D.

Rezvanian

and Meybodi

M.R.

, Distributed learning automata-based algorithm for community detection in complex networks[J], International Journal of Modern Physics B 30(8) (2016), 1650042.

11.

Newman

M.E.J.

and Leicht

E.A.

, Mixture models and exploratory analysis in networks[J], Proceedings of the National Academy of Sciences 104(23) (2007), 9564–9569.

12.

Atzmueller

Doerfel

and Mitzlaff

, Description-oriented community detection using exhaustive subgroup discovery[J], Information Sciences 329 (2016), 965–984.

13.

Wang

Z.-X.

Z.-C.

Ding

X.-F.

and Tang

J.-H.

, Overlapping community detection based on node location analysis[J], Knowledge-Based Systems 105 (2016), 225–235.

14.

Jia

, A social networks routing algorithm of resisting sybil attack based on P2P, Journal of Computational Methods in Sciences and Engineering 6(4) (2016), 877–898.

15.

Song

Liu

et al., Particle swarm optimization algorithm based on parameter improvements[J], Journal of Computational Methods in Sciences and Engineering 17(3) (2017), 557–568.

16.

Zhang

Hei

Yang

et al., A memetic particle swarm optimization algorithm for community detection in complex networks[J], International Journal of Pattern Recognition and Artificial Intelligence 30(2) (2016), 1659003.

17.

Gregory

, Finding overlapping communities in networks by label propagation[J], New Journal of Physics 12(10) (2010), 103018.

18.

Leung

I.X.Y.

Hui

Lio

et al., Towards real-time community detection in large networks[J], Physical Review E 79(6) (2009), 066107.

19.

Lou

and Zhao

, Detecting community structure using label propagation with weighted coherent neighborhood propinquity[J], Physica A: Statistical Mechanics and its Applications 392(14) (2013), 3095–3105.

20.

Lancichinetti

and Fortunato

, Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J], Physical Review E 80(1) (2009), 016118.

21.

Lee

Reid

McDaid

et al., Detecting highly overlapping community structure by greedy clique expansion[J], arXiv preprint arXiv:1002.1827, 2010.

22.

Roth

A.E.

, The Shapley value: essays in honor of Lloyd S. Shapley[M]. Cambridge University Press, 1988.

23.

Lancichinetti

Fortunato

and Radicchi

, Benchmark graphs for testing community detection algorithms[J], Physical Review E 78(4) (2008), 046110.

24.

Jure

, Stanford large network dataset collection[OL]. http://snap.stanford.edu/data/index.html, 2013.

25.

Xie

Chen

and Szymanski

B.K.

, LabelrankT: Incremental community detection in dynamic networks via label propagation[C]//Proceedings of the Workshop on Dynamic Networks Management and Mining. ACM, 2013: 25–32.

A novel two-step community detection approach based on community tree and the N -players cooperative game in large-scale social networks

Abstract

Keywords

Get full access to this article

References