Incremental methods for community detection in both fully and growing dynamic networks

[1]Y. Y. Ahn, J. P. Bagrow, S. Lehmann, Link communities reveal multi-scale complexity in networks, Nature, 466, 7307 (2010) 761–764. ⇒22210.1038/nature0918220562860Search in Google Scholar

[2]E. Akachar, B. Ouhbi, B. Frikh, A new algorithm for detecting communities in social networks based on content and structure information, International Journal of Web Information Systems, 2019. ⇒22210.1108/IJWIS-06-2019-0030Search in Google Scholar

[3]M. Ankerst, M. M. Breunig, H. P. Kriegel, J. Sander, OPTICS: Ordering Points To Identify the Clustering Structure, ACM Sigmod record, 28, 2 (1999) 49–60. ⇒22210.1145/304181.304187Search in Google Scholar

[4]M. Asadi, F. Ghaderi, Incremental community detection in social networks using label propagation method, 23rd Conference of Open Innovations Association (FRUCT), 2018, pp. 39–47. ⇒236, 237, 24310.23919/FRUCT.2018.8588023Search in Google Scholar

[5]J. Bagrow, E. Bollt, A local method for detecting communities, Physical review E, 72, 4 (2005) 46–108. ⇒22210.1103/PhysRevE.72.04610816383469Search in Google Scholar

[6]S. Bansal, S. Bhowmick, P. Paymal, Fast community detection for dynamic complex networks, Complex Networks, Springer, Berlin, Heidelberg, 2011, pp. 196–207. ⇒221, 232, 233, 24310.1007/978-3-642-25501-4_20Search in Google Scholar

[7]E. R. Barnes, An Algorithm for Partitioning the Nodes of a Graph, SIAM Journal on Algebraic and Discrete Methods,3, 4(1982) 541–550. ⇒22210.1137/0603056Search in Google Scholar

[8]S. Y. Bhat, M. Abulaish, HOCTracker: Tracking the evolution of hierarchical and overlapping communities in dynamic social networks, IEEE Transactions on Knowledge and Data engineering, 27, 4(2014) 1019–1013. ⇒239, 240, 24310.1109/TKDE.2014.2349918Search in Google Scholar

[9]V. D. Blondel, J. Guillaume, R. Lambiotte, E. Lefebvre, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, 2008, 10 (2008) P10008. ⇒222, 229, 232, 234, 238, 23910.1088/1742-5468/2008/10/P10008Search in Google Scholar

[10]F. Bouhatem, A. A. Ait El Hadj, F. Souam, Density-based Approach with Dual Optimization for Tracking Community Structure of Increasing Social Networks, International Journal on Artificial Intelligence Tools, 29, 01(2020) 2050002. ⇒221, 222, 223, 239, 240, 24310.1142/S0218213020500025Search in Google Scholar

[11]L. Boujlaleb, A. Idarrou, D. Mammass, Tracking community evolution in social networks, Journal of theoretical and applied information technology, 95, 22 (2017). ⇒221, 223Search in Google Scholar

[12]U. Brandes, D. Delling, M. Gaertler, R. Gorke, M. Hoefer, Z. Nikoloski, D. Wagner, On modularity clustering, IEEE transactions on knowledge and data engineering, 20, 2 (2007) 172–188. ⇒24210.1109/TKDE.2007.190689Search in Google Scholar

[13]P. Bródka, S. Saganowski, P. Kazienko, GED: the method for group evolution discovery in social networks, Social Network Analysis and Mining, 3, 1(2013), 1–14, ⇒224, 22610.1007/s13278-012-0058-8Search in Google Scholar

[14]R. Cazabet, F. Amblard, C. Hanachi, Detection of overlapping communities in dynamical social networks, IEEE second international conference on social computing, 2010, pp. 309–314. ⇒24110.1109/SocialCom.2010.51Search in Google Scholar

[15]D. Chakrabarti, R. Kumar, A. Tomkins, Evolutionary clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006, pp.554–560, ⇒221, 222, 22310.1145/1150402.1150467Search in Google Scholar

[16]W. H. Chong, L. N. Teow, An incremental batch technique for community detection, Proceedings of the 16th international conference on information fusion, 2013, pp. 750–757. ⇒232, 233, 243Search in Google Scholar

[17]A. Clauset, M. E. J. Newman, C. Moore, Finding community structure in very large networks, Physical review E, 70, 6 (2004) 066111. ⇒222, 229, 232, 23810.1103/PhysRevE.70.066111Search in Google Scholar

[18]M. Cordeiro, R. P. Sarmento, J. Gama, Dynamic community detection in evolving networks using locality modularity optimization, Social Network Analysis and Mining, 6, 1(2016) 15. ⇒232, 233, 24310.1007/s13278-016-0325-1Search in Google Scholar

[19]M. Coscia, G. Rossetti, F. Giannotti, D. Pedreschi, Demon: a local-first discovery method for overlapping communities, Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, 2012, pp. 615–623. ⇒24010.1145/2339530.2339630Search in Google Scholar

[20]M. Ester, H. P. Kriegel, J. Sander, X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, Proceedings of the 2nd International Conference on Knowledge Discovery and Data mining, 1996, pp. 226–231. ⇒222, 234Search in Google Scholar

[21]M. Ester, R. Wittmann, Incremental generalization for mining in a data warehousing environment, International Conference on Extending Database Technology, Springer, Berlin, Heidelberg,1998, pp. 135–149. ⇒221, 23410.1007/BFb0100982Search in Google Scholar

[22]T. S. Evans, R. Lambiotte, Line graphs, link partitions and overlapping communities, Physical review E, 80, 1 (2009) 016105. ⇒22210.1103/PhysRevE.80.016105Search in Google Scholar

[23]T. Falkowski, A. Barth, M. Spiliopoulou, Dengraph: A density-based community detection algorithm, IEEE/WIC/ACM International Conference on Web Intelligence (WI’07), 2007, pp. 112–115. ⇒23410.1109/WI.2007.74Search in Google Scholar

[24]C. M. Fiduccia, R. M. Mattheyses, A Linear-Time Heuristic for Improving Network Partitions, 19th Design Automation Conference, IEEE, 1982, pp. 175–181. ⇒22210.1109/DAC.1982.1585498Search in Google Scholar

[25]S. Fortunato, C. Castellano, Community structure in graphs, ArXiv preprint arXiv: 0712.2716, 2007. ⇒234Search in Google Scholar

[26]S. Fortunato, M. Barthelemy, Resolution limit in community detection, Proceedings of the national academy of sciences, 104, 1(2007) 36–41. ⇒24210.1073/pnas.0605965104Search in Google Scholar

[27]S. Fortunato, Community detection in graphs, Physics Reports, 486, 3(2010) 75–174. ⇒221, 22210.1016/j.physrep.2009.11.002Search in Google Scholar

[28]M. Girvan, M. E. J. Newman, Community structure in social and biological networks, Proceedings Of the National Academy Of Sciences, 99,12 (2002) 7821–7826. ⇒222, 225, 22710.1073/pnas.122653799Search in Google Scholar

[29]S. Gregory, Finding overlapping communities in networks by label propagation, New Journal of Physics, 12, 10 (2010) 103018. ⇒22310.1088/1367-2630/12/10/103018Search in Google Scholar

[30]J. Han, W. Li, L. Zhao, Z. Su, Y. Zou, W. Deng, Community detection in dynamic networks via adaptive label propagation, PloS one, 12, 11 (2017) e0188655. ⇒236, 237, 24310.1371/journal.pone.0188655Search in Google Scholar

[31]J. A. Hartigan, M. A. Wong, Algorithm AS 136: A K-Means Clustering Algorithm, Journal of the Royal Statistical Society, Series C, 28, 1(1979) 100–108. ⇒22210.2307/2346830Search in Google Scholar

[32]S. Heymann, Exploratory link stream analysis for event detection, Doctoral dissertation, Université Pierre et Marie Curie-Paris VI, Paris, 2013. ⇒225Search in Google Scholar

[33]A. Hinneburg, D. A. Keim, An E cient Approach to Clustering in Large Multimedia Databases with Noise, Knowledge Discovery and Data Mining, New York City, USA, 1998, pp. 58–65. ⇒222Search in Google Scholar

[34]J. Hopcroft, O. Khan, B. Kulis, B. Selman,Tracking evolving communities in large linked networks, Proceedings of the national academy of sciences of the United States of America, 101 (2004) 5249–5253. ⇒221, 222, 22310.1073/pnas.0307750100Search in Google Scholar

[35]B. Kaminski, T. Olczak, Artificial Benchmark for Community Detection (ABCD), Joint Mathematics Meetings (JMM), AMS, 2021. ⇒225, 227Search in Google Scholar

[36]H. Kanezashi, T. Suzumura, An incremental local-first community detection method for dynamic graphs, IEEE International Conference on Big Data (Big Data), 2016, pp. 3318–3325. ⇒221, 240, 241, 24310.1109/BigData.2016.7840991Search in Google Scholar

[37]R. Kannan, S. Vempala, A. Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), 51, 3(2004) 497–515. ⇒22710.1145/990308.990313Search in Google Scholar

[38]B.W. Kernighan, S. Lin, An e cient heuristic procedure for partitioning graphs, Bell System Technical Journal, 49, 2 (1970) 291–307. ⇒22210.1002/j.1538-7305.1970.tb01770.xSearch in Google Scholar

[39]A. Lancichinetti, S. Fortunato, F. Radicchi, Benchmark graphs for testing community detection algorithms, Physical review E, 78, 4 (2008) 046110. ⇒225, 226, 22710.1103/PhysRevE.78.04611018999496Search in Google Scholar

[40]F. Meng, F. Zhang, M. Zhu, Y. Xing, Z. Wang, J. Shi, Incremental density-based link clustering algorithm for community detection in dynamic networks, Mathematical Problems in Engineering, 2016. ⇒221, 234, 235, 24310.1155/2016/1873504Search in Google Scholar

[41]Z. Mu, M. Fanrong, Z. Yong, Density-based link clustering algorithm for overlapping community detection, Journal of computer research and development, 50, 12 (2013) 2520. ⇒234Search in Google Scholar

[42]K. Nath, S. Roy, Detecting intrinsic communities in evolving networks, Social Network Analysis and Mining, 9,1 (2019)1–15. ⇒223, 239, 240, 24310.1007/s13278-019-0552-3Search in Google Scholar

[43]M. E. J. Newman, M. Girvan, Finding and evaluating community structure in networks, Physical review E, 69, 2 (2004) 026113. ⇒222, 22710.1103/PhysRevE.69.02611314995526Search in Google Scholar

[44]M. E. Newman, Spectral methods for community detection and graph partitioning, Physical Review E, 88, 4 (2013) 042822. ⇒22210.1103/PhysRevE.88.04282224229240Search in Google Scholar

[45]M. E. Newman, Detecting community structure in networks, The European Physical Journal B-Condensed Matter and Complex Systems, 38, 2 (2004) 321–330. ⇒23110.1140/epjb/e2004-00124-ySearch in Google Scholar

[46]N. P. Nguyen, T. N. Dinh, Y. Xuan,, M. T. Thai, Adaptive algorithms for detecting community structure in dynamic social networks, Proceedings IEEE INFOCOM, 2011, pp. 2282–2290. ⇒221, 232, 233, 243Search in Google Scholar

[47]N. P. Nguyen, T. N. Dinh, S. Tokala, M. T. Thai, Overlapping communities in dynamic networks: their detection and mobile applications, Proceedings of the 17th annual international conference on Mobile computing and networking, 2011, pp. 85–96. ⇒234, 235, 24310.1145/2030613.2030624Search in Google Scholar

[48]G. Palla, A. L. Barabási, T. Vicsek, Quantifying social group evolution, Nature, 446, 7136 (2007) 664–667. ⇒22410.1038/nature0567017410175Search in Google Scholar

[49]F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, Defining And identifying communities in networks, Proceedings of the National Academy of Sciences, 101, 9 (2004) 2658–2663. ⇒222, 22710.1073/pnas.040005410136567714981240Search in Google Scholar

[50]U. N. Raghavan, R. Albert, R. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, 76, 3 (2007) 036106. ⇒222, 23610.1103/PhysRevE.76.03610617930305Search in Google Scholar

[51]W. M. Rand, Objective criteria for the evaluation of clustering methods, Journal of the American Statistical association, 66, 336 (1971) 846–850. ⇒22710.1080/01621459.1971.10482356Search in Google Scholar

[52]N. Schlitter, T. Falkowski, J. L¨assig, DenGraph-HO: a density-based hierarchical graph clustering algorithm, Expert Systems, 31, 5 (2014) 469–479. ⇒234, 235, 24310.1111/exsy.12046Search in Google Scholar

[53]N. Sengupta, M. Hamann, D. Wagner, Benchmark generator for dynamic overlapping communities in networks, IEEE International Conference on Data Mining (ICDM), 2017, pp. 415–424. ⇒225, 22710.1109/ICDM.2017.51Search in Google Scholar

[54]J. Shang, L. Liu, F. Xie, Z. Chen, J. Miao, X. Fang, C. Wu, A real-time detecting algorithm for tracking community structure of dynamic networks, ArXiv preprint arXiv: 1407.2683, 2014. ⇒238, 239, 243Search in Google Scholar

[55]J. Shang, L. Liu, X. Li, F. Xie, C. Wu, Targeted revision: A learning-based approach for incremental community detection in dynamic networks, Physica A: Statistical Mechanics and its Applications, 443, (2016)70–85. ⇒224, 233, 24310.1016/j.physa.2015.09.072Search in Google Scholar

[56]J. Shi, J. Malik, Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 8, (2000) 888–905. ⇒22210.1109/34.868688Search in Google Scholar

[57]Z. Sun, J. Sheng, B. Wang, A. Ullah, F. Khawaja, Identifying Communities in Dynamic Networks Using Information Dynamics, Entropy, 22, 4(2020) 425. ⇒223, 236, 237, 24310.3390/e22040425Search in Google Scholar

[58]M. Taka oli, F. Sangi, J. Fagnan, O. R. Z¨aıane, Community evolution mining in dynamic social networks, Procedia-Social and Behavioral Sciences, 22, (2011) 49–58. ⇒22410.1016/j.sbspro.2011.07.055Search in Google Scholar

[59]Y. Van Gennip, B. Hunter, R. Ahn, P. Elliott, K. Luh, M. Halvorson, .... and P. J. Brantingham, Community detection using spectral clustering on sparse geosocial data, SIAM Journal on Applied Mathematics, 73, 1, (2013) 67–83. ⇒22210.1137/120882093Search in Google Scholar

[60]D. R. White, F. Harary, M. Sobel, M. Becker,The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological Methodology, 31, 1(2001) p. 305–359. ⇒22210.1111/0081-1750.00098Search in Google Scholar

[61]J. Xie, B. K. Szymanski, Community detection using a neighborhood strength driven label propagation algorithm, IEEE Network Science Workshop, 2011, pp. 188–195. ⇒22310.1109/NSW.2011.6004645Search in Google Scholar

[62]J. Xie, B. K. Szymanski, Towards linear time overlapping community detection in social networks, Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, Berlin, Heidelberg, 2012, pp. 25–36. ⇒223, 23610.1007/978-3-642-30220-6_3Search in Google Scholar

[63]J. Xie, M. Chen, B. K. Szymanski, LabelrankT: Incremental community detection in dynamic networks via label propagation, Proceedings of the workshop on dynamic networks management and mining, 2013, pp. 25–32. ⇒235, 237, 24310.1145/2489247.2489249Search in Google Scholar

[64]J. Xie, B. K. Szymanski, Labelrank: A stabilized label propagation algorithm for community detection in networks, IEEE 2nd Network Science Workshop (NSW), 2013, pp. 138–143. ⇒23510.1109/NSW.2013.6609210Search in Google Scholar

[65]S. Yin, S. Chen, Z. Feng, K. Huang, D. He, P. Zhao, M. Y. Yang, Node-grained incremental community detection for streaming networks, IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI), 2016, pp. 585–592. ⇒221, 238, 239, 24310.1109/ICTAI.2016.0095Search in Google Scholar

[66]N. Yuruk, M. Mete, X. Xu, T. A. J. Schweiger, A Divisive Hierarchical Structural Clustering Algorithm for Networks, Seventh IEEE Int. Conf. on Data Mining Workshops (ICDMW 2007), Omaha, NE, 2007, pp. 441-448. ⇒22210.1109/ICDMW.2007.73Search in Google Scholar

[67]N. Yuruk, M. Mete, X. Xu, T. A. J. Schweiger, AHSCAN: Agglomerative Hierarchical Structural Clustering Algorithm for Networks, International Conference on Advances in Social Network Analysis and Mining, Athens, 2009, pp. 72–77. ⇒22210.1109/ASONAM.2009.74Search in Google Scholar

[68]N. Zarayeneh, A. Kalyanaraman, A fast and e cient incremental approach toward dynamic community detection, Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, 2019, pp. 9–16. ⇒238, 239, 24310.1145/3341161.3342877Search in Google Scholar

[69]Z. Zhao, C. Li, X. Zhang, F. Chiclana, E. H. Viedma, An incremental method to detect communities in dynamic evolving social networks, Knowledge-Based Systems, 163, 2019, pp. 404–415. ⇒24110.1016/j.knosys.2018.09.002Search in Google Scholar

[70]D. Zhuang, M. J. Chang, M. Li, DynaMo: Dynamic community detection by incrementally maximizing modularity, IEEE Transactions on Knowledge and Data Engineering, 2019. ⇒221, 233, 24310.1109/TKDE.2019.2951419Search in Google Scholar