OPEN ACCESS
The discovery of cohesive groups, cliques and communities within a network is one of the most studied topics in social network analysis. It attracted many researchers in sociology, biology, computer science, physics, criminology, etc. However, most of the studies in this area have focused on static networks while leaving aside the dynamic networks and even more those temporal. However, in these cases, issues such as evolution, the structure change and sometimes even behind the formation of these communities are interesting issues to address. Given the proliferation of social networks from the spatio-temporal data, we have to point out that the study of dynamic communities becomes a paramount challenge the since they are sometimes volatile and/or mutable. The objective of this article is to reviewing studies on communities detection. Afterwards, we highlight the limits of most communities detection approaches in order to point out how we can deal with them.
social networks analysis, community detection, dynamic networks
Asur S., Parthasarathy S., Ucar D. (2009). An event-based framework for characterizing the evolutionary behavior of interaction graphs. ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 3, no 4, p. 16.
Aynaud T., Fleury E., Guillaume J.-L., Wang Q. (2013). Communities in evolving networks: definitions, detection, and analysis techniques. In Dynamics on and of complex networks, volume 2, p. 159–200. Springer.
Aynaud T., Guillaume J.-L. (2010). Long range community detection. In Lawdn-latin-american workshop on dynamic networks, p. 4–p.
Blondel V. D., Guillaume J.-L., Lambiotte R., Lefebvre E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, vol. 2008, no 10, p. P10008.
Brandes U., Delling D., Gaertler M., Görke R., Hoefer M., Nikoloski Z. et al. (2006). On modularity-np-completeness and beyond. Citeseer.
Bródka P., Saganowski S., Kazienko P. (2013). Ged: the method for group evolution discovery in social networks. Social Network Analysis and Mining, vol. 3, no 1, p. 1–14.
Capocci A., Servedio V. D., Caldarelli G., Colaiori F. (2005). Detecting communities in large networks. Physica A: Statistical Mechanics and its Applications, vol. 352, no 2, p. 669–676.
Cazabet R. (2013). Détection de communautés dynamiques dans des réseaux temporels. Thèse de doctorat non publiée, Université Paul Sabatier-Toulouse III.
Cazabet R., Amblard F. (2011). Simulate to detect: a multi-agent system for community detection. In Web intelligence and intelligent agent technology (wi-iat), 2011 ieee/wic/acm international conference on, vol. 2, p. 402–408.
Cazabet R., Amblard F., Hanachi C. (2010). Detection of overlapping communities in dynamical social networks. In Social computing (socialcom), 2010 ieee second international conference on, p. 309–314.
Chan S.-Y., Hui P., Xu K. (2009). Community detection of time-varying mobile social networks. In Complex sciences, p. 1154–1159. Springer.
ChenW., Liu Z., Sun X.,Wang Y. (2010). A game-theoretic framework to identify overlapping communities in social networks. Data Mining and Knowledge Discovery, vol. 21, no 2, p. 224–240.
Coscia M., Giannotti F., Pedreschi D. (2011). A classification for community discovery methods in complex networks. Statistical Analysis and Data Mining, vol. 4, no 5, p. 512–546.
Csardi G., Nepusz T. (2006). The igraph software package for complex network research. InterJournal, Complex Systems, vol. 1695, no 5, p. 1–9.
Falkowski T., Barth A., Spiliopoulou M. (2008). Studying community dynamics with an incremental graph mining algorithm. AMCIS 2008 Proceedings, p. 29.
Fortunato S. (2010). Community detection in graphs. Physics reports, vol. 486, no 3, p. 75–174.
Fortunato S., Latora V., Marchiori M. (2004). Method to find community structures based on information centrality. Physical review E, vol. 70, no 5, p. 056104.
Girvan M., Newman M. E. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, vol. 99, no 12, p. 7821–7826.
Gori M., Pucci A., Roma V., Siena I. (2007). Itemrank: A random-walk based scoring algorithm for recommender engines. In Ijcai, vol. 7, p. 2766–2771.
Greene D., Doyle D., Cunningham P. (2010). Tracking the evolution of communities in dynamic social networks. In Advances in social networks analysis and mining (asonam), 2010 international conference on, p. 176–183.
Gregory S. (2010). Finding overlapping communities in networks by label propagation. New Journal of Physics, vol. 12, no 10, p. 103018.
Harenberg S., Bello G., Gjeltema L., Ranshous S., Harlalka J., Seay R. et al. (2014). Community detection in large-scale networks: a survey and empirical evaluation. Wiley Interdisciplinary Reviews: Computational Statistics, vol. 6, no 6, p. 426–439.
Haynes J., Perisic I. (2009). Mapping search relevance to social networks. In Proceedings of the 3rd workshop on social network mining and analysis, p. 2.
Heymann S. (2013). Exploratory link stream analysis for event detection. Thèse de doctorat non publiée, Université Pierre et Marie Curie-Paris VI.
Hopcroft J., Khan O., Kulis B., Selman B. (2004). Tracking evolving communities in large linked networks. Proceedings of the National Academy of Sciences, vol. 101, no suppl 1, p. 5249–5253.
Hui P., Sastry N. (2009). Real world routing using virtual world information. In Computational science and engineering, 2009. cse’09. international conference on, vol. 4, p. 1103–1108.
Jdidia M. B., Robardet C., Fleury E. (2007). Communities detection and analysis of their dynamics in collaborative networks. In Icdim, p. 744–749.
Jeffrey Travers S. M. (1969). An experimental study of the small world problem. Sociometry, vol. 32, no 4, p. 425-443.
Khatoon M., Banu W. A. (2015). A survey on community detection methods in social networks. International Journal of Education and Management Engineering (IJEME), vol. 5, no 1, p. 8.
Lancichinetti A., Fortunato S., Kertész J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, vol. 11, no 3, p. 033015.
Leung I. X., Hui P., Lio P., Crowcroft J. (2009). Towards real-time community detection in large networks. Physical Review E, vol. 79, no 6, p. 066107.
Li J., Huang L., Bai T., Wang Z., Chen H. (2012). Cdbia: a dynamic community detection method based on incremental analysis. In Systems and informatics (icsai), 2012 international conference on, p. 2224–2228.
Li J.,Wang X., Cui Y. (2014). Uncovering the overlapping community structure of complex networks by maximal cliques. Physica A: Statistical Mechanics and its Applications, vol. 415, p. 398–406.
Lin Y.-R., Chi Y., Zhu S., Sundaram H., Tseng B. L. (2009). Analyzing communities and their evolutions in dynamic social networks. ACM Transactions on Knowledge Discovery from Data (TKDD), vol. 3, no 2, p. 8.
Massen C. P., Doye J. P. (2005). Identifying communities within energy landscapes. Physical Review E, vol. 71, no 4, p. 046101.
Mitrovi´c M., Tadi´c B. (2009). Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneities. Physical Review E, vol. 80, no 2, p. 026123.
Mucha P. J., Richardson T., Macon K., Porter M. A., Onnela J.-P. (2010). Community structure in time-dependent, multiscale, and multiplex networks. science, vol. 328, no 5980, p. 876–878.
Nagpal A., Jatain A., Gaur D. (2013). Review based on data clustering algorithms. In Information & communication technologies (ict), 2013 ieee conference on, p. 298–303.
Newman M. E. (2004). Detecting community structure in networks. The European Physical Journal B-Condensed Matter and Complex Systems, vol. 38, no 2, p. 321–330.
Palla G., Barabási A.-L., Vicsek T. (2007). Quantifying social group evolution. Nature, vol. 446, no 7136, p. 664–667.
Palla G., Derényi I., Farkas I., Vicsek T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, vol. 435, no 7043, p. 814–818.
Papadopoulos S., Kompatsiaris Y., Vakali A., Spyridonos P. (2012). Community detection in social media. Data Mining and Knowledge Discovery, vol. 24, no 3, p. 515–554.
Pons P., Latapy M. (2005). Computing communities in large networks using random walks. In Computer and information sciences-iscis 2005, p. 284–293. Springer.
Porter M. A., Onnela J.-P., Mucha P. J. (2009). Communities in networks. Notices of the AMS, vol. 56, no 9, p. 1082–1097.
Raghavan U. N., Albert R., Kumara S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, vol. 76, no 3, p. 036106.
Reichardt J., Bornholdt S. (2004). Detecting fuzzy community structures in complex networks with a potts model. Physical Review Letters, vol. 93, no 21, p. 218701.
Roma G., Herrera P. (2010). Community structure in audio clip sharing. In Intelligent networking and collaborative systems (incos), 2010 2nd international conference on, p. 200–205.
Rosvall M., Axelsson D., Bergstrom C. T. (2009). The map equation. The European Physical Journal Special Topics, vol. 178, no 1, p. 13–23.
Rosvall M., Bergstrom C. T. (2008). Maps of random walks on complex networks reveal community structure. Proceedings of the National Academy of Sciences, vol. 105, no 4, p. 1118–1123.
Rosvall M., Bergstrom C. T. (2010). Mapping change in large networks. PloS one, vol. 5, no 1, p. e8694.
Schult D. A., Swart P. (2008). Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th python in science conferences (scipy 2008), vol. 2008, p. 11–16.
Shang J., Liu L., Xie F., Chen Z., Miao J., Fang X. et al. (2014). A real-time detecting algorithm for tracking community structure of dynamic networks. arXiv preprint arXiv:1407.2683.
Slanina F., Zhang Y.-C. (2005). Referee networks and their spectral properties. In Acta physica polonica b, p. 2797.
Son S.-W., Jeong H., Noh J. D. (2006). Random field ising model and community structure in complex networks. The European Physical Journal B-Condensed Matter and Complex Systems, vol. 50, no 3, p. 431–437.
Tantipathananandh C., Berger-Wolf T., Kempe D. (2007). A framework for community identification in dynamic social networks. In Proceedings of the 13th acm sigkdd international conference on knowledge discovery and data mining, p. 717–726.
Tong H., Faloutsos C., Pan J.-Y. (2008). Random walk with restart: fast solutions and applications. Knowledge and Information Systems, vol. 14, no 3, p. 327–346.
Wang Y.,Wu B., Du N. (2008). Community evolution of social network: feature, algorithm and model. arXiv preprint arXiv:0804.4356.
Weiss R. S., Jacobson E. (1955). A method for the analysis of the structure of complex organizations. American Sociological Review, vol. 20, no 6, p. 661–668.
Weng L., Menczer F., Ahn Y.-Y. (2013). Virality prediction and community structure in social networks. Scientific reports, vol. 3.
Whitbeck J., Amorim M. Dias de, Conan V., Guillaume J.-L. (2012). Temporal reachability graphs. In Proceedings of the 18th annual international conference on mobile computing and networking, p. 377–388.
Wilkinson D. M., Huberman B. A. (2004). A method for finding communities of related genes. proceedings of the national Academy of sciences, vol. 101, no suppl 1, p. 5241–5248.
Xie J., Szymanski B. K. (2012). Towards linear time overlapping community detection in social networks. In Advances in knowledge discovery and data mining, p. 25–36. Springer.
Xie J., Szymanski B. K., Liu X. (2011). Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In Data mining workshops (icdmw), 2011 ieee 11th international conference on, p. 344–349.
Xu K. S., Kliger M., Hero III A. O. (2011). Tracking communities in dynamic social networks. In Social computing, behavioral-cultural modeling and prediction, p. 219–226. Springer.
Yang B., Liu D., Liu J. (2010). Discovering communities from social networks: methodologies and applications. In Handbook of social network technologies and applications, p. 331–346. Springer.
Yang T., Chi Y., Zhu S., Gong Y., Jin R. (2011). Detecting communities and their evolutions in dynamic social networks-a bayesian approach. Machine learning, vol. 82, no 2, p. 157–189.
Yoon J., Blumer A., Lee K. (2006). An algorithm for modularity analysis of directed and weighted biological networks based on edge-betweenness centrality. Bioinformatics, vol. 22, no 24, p. 3106–3108.
Yulian N. (2011). Community detection in relation to the spread of epidemics. Mémoire de Master non publié, University of Oxford. Consulté sur http://people.maths.ox.ac.uk/porterm/research/yuli_Dissertation_final.pdf/