Community detection from networks is one of the long standing and challenging tasks in the field of complex network research. Detection of communities poses numerous challenges in terms of their overlapping and hierarchical nature, dynamics of networks and underlying communities, scalability of detection algorithms on large scale networks to mention a few. Traditional community detection methods are not readily scalable to large networks mainly due to the computation of global network metrics. This paper presents a novel scalable overlapping community detection approach for large scale networks by presenting a MapReduce framework based implementation of a density-based local community detection method. The method is divided in two stages where the first stage uses a MapReduce approach to identify a mutual-core connected subgraph of the underlying network. The second stage uses an existing connected component detection method, implemented via MapReduce, to identify connected components in the mutual-core connected subgraph generated in the first stage. A community is then taken as the union of the core-nodes in a connected component and the respective density-based neighborhood of each core-node in the connected component. The resulting approach is among the first scalable overlapping community detection methods proposed in literature.
C.Lam, Hadoop in action. Manning Publications Co.; 2010.
2.
S.Y.Bhat and M.Abulaish, HOCTracker: Tracking the evolution of hierarchical and overlapping communities in dynamic social networks, IEEE Transactions on Knowledge and Data Engineering27(4) (2015), 1019–1013.
3.
S.Y.Bhat and M.Abulaish, Analysis and mining of online social networks: Emerging trends and challenges, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery3(6) (2013), 408–444.
4.
M.E.Newman and M.Girvan, Finding and evaluating community structure in networks, Physical ReviewE69 (2004), 026113.
5.
D.Greene, D.Doyle and P.Cunningham, Tracking the evolution of communities in dynamic social networks. In Proceedings of the International Conference on Advances in Social Networks Analysis and Mining (ASONAM), Odense, Denmark, (2010), 176–183.
6.
A.Lancichinetti, S.Fortunato and J.Kertesz, Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physics11(3) (2009), 033015.
7.
W.W.Zachary, An information flow model for conflict and fission in small groups, Journal of Anthropological Research33(4) (1977), 452–473.
8.
M.Girvan and M.E.Newman, Community structure in social and biological networks. In Proceedings of the National Academy of Sciences99(12) (2002), 7821–7826.
9.
D.Lusseau, K.Schneider, O.J.Boisseau, P.Haase, E.Slooten and S.M.Dawson, The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations, Behavioral Ecology and Sociobiology54(4) (2003), 396–405.
10.
R.S.Burt, Social contagion and innovation: Cohesion versus structural equivalence, American Journal of Sociology92(6) (1987), 1287–1335.
11.
A.Lancichinetti and S.Fortunato, Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities, Physical ReviewE80 (2009), 016118.
12.
R.Cazabet, F.Amblard and C.Hanachi, Detection of overlapping communities in dynamical social networks. In Proceedings of the IEEE Second International Conference on Social Computing, Minneapolis, MN, USA, (2010), 309–314.
13.
I.Rytsareva, T.Chapman and A.Kalyanaraman, Parallel algorithms for clustering biological graphs on distributed and shared memory architectures, International Journal of High Performance Computing and Networking7(4) (2014), 241–257.
14.
J.Soman and A.Narang, Fast community detection algorithm with GPUs and multicore architectures. In Proceedings of the IEEE International Parallel & Distributed Processing Symposium, Anchorage, AK, USA, (2011), 568–579.
15.
S.H.Bae, D.Halperin, J.West, M.Rosvall and B.Howe, Scalable flow-based community detection for large-scale network analysis. In Proceedings of the IEEE 13th International Conference on Data Mining Workshops, Dallas, TX, USA, (2013), 303–310.
16.
J.Dean and S.Ghemawat, MapReduce: Simplified data processing on large clusters. Communications of the ACM, 51(1) (2008), 107–113.
17.
Y.Tian, A.Balmin, S.A.Corsten, S.Tatikonda and J.McPherson, From think like a vertex to think like a graph. In Proceedings of the VLDB Endowment7(3) (2013), 193–204.
18.
B.Bahmani, R.Kumar and S.Vassilvitskii, Densest subgraph in streaming and mapreduce. In Proceedings of the VLDB Endowment5(5) (2012), 454–465.
19.
Q.Li, Z.Wang, W.Wang, Y.Liu, P.Wang and T.Yu, LI-MR: A local iteration map/reduce model and its application to mine community structure in large-scale networks. In Proceedings of the IEEE 11th International Conference on Data Mining Workshops, Vancouver, BC, Canada, (2011), 174–179.
20.
S.Moon, J.G.Lee and M.Kang, Scalable community detection from networks by computing edge betweenness on mapreduce. In Proceedings of the International Conference on Big Data and Smart Computing, (2014), 145–148.
21.
J.Shi, W.Xue, W.Wang, Y.Zhang, B.Yang and J.Li, Scalable community detection in massive social networks using MapReduce, IBM Journal of Research and Development57(3/4) (2013), 1–12.
22.
D.Zhuang, Modularity-based dynamic community detection, arXiv:1709.08350; 2017.
23.
S.Fortunato, Community detection in graphs, Physics Reports486(3–5) (2010), 75–174.
24.
R.Kiveris, S.Lattanzi, V.Mirrokni, V.Rastogi and S.Vassilvitskii, Connected components in mapreduce and beyond. In Proceedings of the ACM Symposium on Cloud Computing, Seattle, WA, USA, (2014), 1–13.
25.
V.Rastogi, A.Machanavajjhala, L.Chitnis and A.D.Sarma, Finding connected components in map-reduce in logarithmic rounds. In Proceedings of the IEEE 29th International Conference on Data Engineering, Brisbane, QLD, Australia, (2013), 50–61.
26.
T.Seidl, B.Boden and S.Fries, CC-MR – finding connected components in huge graphs with MapReduce. In Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases, LNCS-7523, (2012), 458–473.
27.
A.Lulli, E.Carlini, P.Dazzi, C.Lucchese and L.Ricci, Fast connected components computation in large graphs by vertex pruning. IEEE Transactions on Parallel & Distributed Systems28 (2017), 760–773.
28.
R.Abdolazimi, H.Naderi and M.Sagharichian, Connected components of big graphs in fixed MapReduce rounds, Cluster Computing20(3) (2017), 2563–2574.
29.
G.Palla, A.L.Barabasi and T.Vicsek, Community dynamics in social networks, Fluctuation and Noise Letters7(3) (2007), L273–L287.
30.
G.Palla, I.Derenyi, I.Farkas and T.Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature435 (2005), 814–818.
31.
G.Palla, G.Tibely, E.Mones, P.Pollner and T.Vicsek, Hierarchical networks of scientific journals, Palgrave Communications 1, (2015), Art. No. 15016.
32.
C.Cherifi and H.Cherifi, Evaluating community detection algorithms: A multidimensional issue. In Proceedings of the NetSci Conference, Paris, France; 2018.
33.
G.K.Orman, V.Labatut and H.Cherifi, Comparative evaluation of community detection algorithms: A topological approach, Journal of Statistical Mechanics: Theory and Experiment2012(8) (2012), P08001.
34.
M.Jebabli, H.Cherifi, C.Cherifi and A.Hamouda, Overlapping community detection versus ground-truth in AMAZON co-purchasing network. In Proceedings of the 11th International Conference on Signal-Image Technology & Internet-Based Systems, Bangkok, Thailand, (2015), 328–336.
35.
J.Xie, S.Kelley and B.K.Szymanski, Overlapping community detection in networks: The state-of-the-art and comparative study, ACM Computing Surveys45(4) (2013), 43:1–43:35.
36.
J.Xie, B.K.Szymanski and X.Liu, SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In Proceedings of the IEEE 11th International Conference on Data Mining Workshops, Vancouver, BC, Canada, (2011), 344–349.
37.
M.Chen, Discovering community structure by optimizing community quality metrics, Doctoral Dissertation, Rensselaer Polytechnic Institute, Troy, NY, USA; 2015.
38.
L.Takac and M.Zabovsky, Data analysis in public social networks. In Proceedings of the International Scientific Conference & International Workshop on Present Day Trends of Innovations, Lomza, Poland, (2012), 1–6.
39.
R.Albert, H.Jeong and A.L.Barabasi, Internet: Diameter of the world-wide web, Nature401 (1999), 130–131.
40.
M.Azaouzi, D.Rhouma and L.B.Romdhane, Community detection in large-scale social networks: State-of-the-art and future directions, Social Network Analysis and Mining9(1) (2019), 9–23.
41.
C.Guo, J.Wang and Z.Zhang, Evolutionary community structure discovery in dynamic weighted networks, Physica A: Statistical Mechanics and its Applications413 (2014), 565–576.
42.
Y.Dong, Q.Zha, H.Zhang, G.Kou, H.Fujita, F.Chiclana and E.Herrera-Viedma, Consensus reaching in social network group decision making: Research paradigms and challenges, Knowledge-Based Systems162 (2018), 3–13.
43.
Y.Dong, M.Zhan, G.Kou, Z.Ding and H.Liang, A survey on the fusion process in opinion dynamics, Information Fusion43 (2018), 57–65.
44.
M.Azaouzi and L.B.Romdhane, An evidential influence-based label propagation algorithm for distributed community detection in social networks, Procedia Computer Science112 (2017), 407–416.
