Bibliography¶
CDlib
was developed for research purposes. Here you can find the complete list of papers that contributed to the algorithms and methods it exposes.
Algorithms¶
- Girvan-Newman: Girvan, Michelle, and Mark EJ Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences 99.12 (2002): 7821-7826.
- EM: Newman, Mark EJ, and Elizabeth A. Leicht. Mixture community and exploratory analysis in networks. Proceedings of the National Academy of Sciences 104.23 (2007): 9564-9569.
- SCAN: Xu, X., Yuruk, N., Feng, Z., & Schweiger, T. A. (2007, August). Scan: a structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 824-833)
- GDMP2: Chen, Jie, and Yousef Saad. Dense subgraph extraction with application to community detection. IEEE Transactions on Knowledge and Data Engineering 24.7 (2012): 1216-1230.
- Spinglass: Reichardt, Jörg, and Stefan Bornholdt. Statistical mechanics of community detection. Physical Review E 74.1 (2006): 016110.
- Eigenvector: Newman, Mark EJ. Finding community structure in networks using the eigenvectors of matrices. Physical review E 74.3 (2006): 036104.
- AGDL: Zhang, W., Wang, X., Zhao, D., & Tang, X. (2012, October). Graph degree linkage: Agglomerative clustering on a directed graph. In European Conference on Computer Vision (pp. 428-441). Springer, Berlin, Heidelberg.
- Louvain: Blondel, Vincent D., et al. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment 2008.10 (2008): P10008.
- Leiden: Traag, Vincent, Ludo Waltman, and Nees Jan van Eck. From Louvain to Leiden: guaranteeing well-connected communities. arXiv preprint arXiv:1810.08473 (2018).
- Rb_pots:
- Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74(1), 016110. 10.1103/PhysRevE.74.016110
- Leicht, E. A., & Newman, M. E. J. (2008). Community Structure in Directed Networks. Physical Review Letters, 100(11), 118703. 10.1103/PhysRevLett.100.118703
- Rber_pots: Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74(1), 016110. 10.1103/PhysRevE.74.016110
- CPM: Traag, V. A., Van Dooren, P., & Nesterov, Y. (2011). Narrow scope for resolution-limit-free community detection. Physical Review E, 84(1), 016114. 10.1103/PhysRevE.84.016114
- Significance_communities: Traag, V. A., Krings, G., & Van Dooren, P. (2013). Significant scales in community structure. Scientific Reports, 3, 2930. 10.1038/srep02930 <http://doi.org/10.1038/srep02930>
- Surprise_communities: Traag, V. A., Aldecoa, R., & Delvenne, J.-C. (2015). Detecting communities using asymptotical surprise. Physical Review E, 92(2), 022816. 10.1103/PhysRevE.92.022816
- Greedy_modularity: Clauset, A., Newman, M. E., & Moore, C. Finding community structure in very large networks. Physical Review E 70(6), 2004
- Infomap: Rosvall M, Bergstrom CT (2008) Maps of random walks on complex networks reveal community structure. Proc Natl Acad SciUSA 105(4):1118–1123
- Markov_clustering: Enright, Anton J., Stijn Van Dongen, and Christos A. Ouzounis. An efficient algorithm for large-scale detection of protein families. Nucleic acids research 30.7 (2002): 1575-1584.
- Walktrap: Pons, Pascal, and Matthieu Latapy. Computing communities in large networks using random walks. J. Graph Algorithms Appl. 10.2 (2006): 191-218.
- Label_propagation: Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical review E, 76(3), 036106.
- Async_fluid: Ferran Parés, Dario Garcia-Gasulla, Armand Vilalta, Jonatan Moreno, Eduard Ayguadé, Jesús Labarta, Ulises Cortés, Toyotaro Suzumura T. Fluid Communities: A Competitive and Highly Scalable Community Detection Algorithm.
- DER: M. Kozdoba and S. Mannor, Community Detection via Measure Space Embedding, NIPS 2015
- FRC_FGSN: Kundu, S., & Pal, S. K. (2015). Fuzzy-rough community in social networks. Pattern Recognition Letters, 67, 145-152.
- SBM_dl: Tiago P. Peixoto, Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models , Phys. Rev. E 89, 012804 (2014), DOI: 10.1103/PhysRevE.89.012804 [sci-hub, @tor], arXiv: 1310.4378.
- SBM_dl_nested: Tiago P. Peixoto, Hierarchical block structures and high-resolution model selection in large networks ,Physical Review X 4.1 (2014): 011047
- aslpa: Xie J, Szymanski B K, Liu X. Slpa: Uncovering Overlapping Communities in Social Networks via a Speaker-Listener Interaction Dynamic Process[C]. IEEE 11th International Conference on Data Mining Workshops (ICDMW). Ancouver, BC: IEEE, 2011: 344–349.
- belief: Zhang, Pan, and Cristopher Moore. “Scalable detection of statistically significant communities and hierarchies, using message passing for modularity.” Proceedings of the National Academy of Sciences 111.51 (2014): 18144-18149.
- chinesewhispers: Ustalov, D., Panchenko, A., Biemann, C., Ponzetto, S.P.: Watset: Local-Global Graph Clustering with Applications in Sense and Frame Induction. Computational Linguistics 45(3), 423–479 (2019)
- edmot: Li, Pei-Zhen, et al. “EdMot: An Edge Enhancement Approach for Motif-aware Community Detection.” Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.
- em: Newman, Mark EJ, and Elizabeth A. Leicht. Mixture community and exploratory analysis in networks. Proceedings of the National Academy of Sciences 104.23 (2007): 9564-9569.
- ga: Pizzuti, C. (2008). Ga-net: A genetic algorithm for community detection in social networks. In Inter conf on parallel problem solving from nature, pages 1081–1090.Springer.
- Demon:
- Coscia, M., Rossetti, G., Giannotti, F., & Pedreschi, D. (2012, August). Demon: a local-first discovery method for overlapping communities. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 615-623). ACM.
- Coscia, M., Rossetti, G., Giannotti, F., & Pedreschi, D. (2014). Uncovering hierarchical and overlapping communities with a local-first approach. ACM Transactions on Knowledge Discovery from Data (TKDD), 9(1), 6.
- Angel: Rossetti, G. (2019) Exorcising the Demon: Angel, Efficient Node-Centric Community Discovery. International Conference on Complex Networks and Their Applications. Springer, Cham.
- Node_perception: Sucheta Soundarajan and John E. Hopcroft. 2015. Use of Local Group Information to Identify Communities in Networks. ACM Trans. Knowl. Discov. Data 9, 3, Article 21 (April 2015), 27 pages. DOI=http://dx.doi.org/10.1145/2700404
- Overlapping_seed_set_expansion: Whang, J. J., Gleich, D. F., & Dhillon, I. S. (2013, October). Overlapping community detection using seed set expansion. In Proceedings of the 22nd ACM international conference on Conference on information & knowledge management (pp. 2099-2108). ACM.
- Kclique: Gergely Palla, Imre Derényi, Illés Farkas1, and Tamás Vicsek, Uncovering the overlapping community structure of complex networks in nature and society Nature 435, 814-818, 2005, doi:10.1038/nature03607
- LFM: Lancichinetti, Andrea, Santo Fortunato, and János Kertész. Detecting the overlapping and hierarchical community structure in complex networks New Journal of Physics 11.3 (2009): 033015.
- Lais2: Baumes, Jeffrey, Mark Goldberg, and Malik Magdon-Ismail. Efficient identification of overlapping communities. International Conference on Intelligence and Security Informatics. Springer, Berlin, Heidelberg, 2005.
- Congo: Gregory, Steve. A fast algorithm to find overlapping communities in networks. Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, Heidelberg, 2008.
- Conga: Gregory, Steve. An algorithm to find overlapping community structure in networks. European Conference on Principles of Data Mining and Knowledge Discovery. Springer, Berlin, Heidelberg, 2007.
- Lemon: Yixuan Li, Kun He, David Bindel, John Hopcroft Uncovering the small community structure in large networks: A local spectral approach. Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, 2015.
- SLPA: Xie Jierui, Boleslaw K. Szymanski, and Xiaoming Liu. Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. Data Mining Workshops (ICDMW), 2011 IEEE 11th International Conference on. IEEE, 2011.
- Multicom: Hollocou, Alexandre, Thomas Bonald, and Marc Lelarge. Multiple Local Community Detection. ACM SIGMETRICS Performance Evaluation Review 45.2 (2018): 76-83.
- Big_clam: Yang, J., & Leskovec, J. (2013, February). Overlapping community detection at scale: a nonnegative matrix factorization approach. In Proceedings of the sixth ACM international conference on Web search and data mining (pp. 587-596). ACM.
- damnf: Ye, Fanghua, Chuan Chen, and Zibin Zheng. “Deep autoencoder-like nonnegative matrix factorization for community detection.” Proceedings of the 27th ACM International Conference on Information and Knowledge Management. 2018.
- egonet splitter: Epasto, Alessandro, Silvio Lattanzi, and Renato Paes Leme. “Ego-splitting framework: From non-overlapping to overlapping clusters.” Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017.
- nmnf: Wang, Xiao, et al. “Community preserving network embedding.” Thirty-first AAAI conference on artificial intelligence. 2017.
- nnsed: Sun, Bing-Jie, et al. “A non-negative symmetric encoder-decoder approach for community detection.” Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2017.
- percomvc: Kasoro, Nathanaël, et al. “PercoMCV: A hybrid approach of community detection in social networks.” Procedia Computer Science 151 (2019): 45-52.
- wCommunity: Chen, D., Shang, M., Lv, Z., & Fu, Y. (2010). Detecting overlapping communities of weighted networks via a local algorithm. Physica A: Statistical Mechanics and its Applications, 389(19), 4177-4187.
- blmpa: Taguchi, Hibiki, Tsuyoshi Murata, and Xin Liu. BiMLPA: Community Detection in Bipartite Networks by Multi-Label Propagation. International Conference on Network Science. Springer, Cham, 2020.
- CPM bipartite: Barber, M. J. (2007). Modularity and community detection in bipartite networks. Physical Review E, 76(6), 066102. 10.1103/PhysRevE.76.066102
- syblinarity: Vasiliauskaite, V., Evans, T.S. Making communities show respect for order. Appl Netw Sci 5, 15 (2020). https://doi.org/10.1007/s41109-020-00255-5
- hierarchical_link_community: Ahn, Yong-Yeol, James P. Bagrow, and Sune Lehmann. Link communities reveal multiscale complexity in networks. nature 466.7307 (2010): 761.
- Eva: Citraro, S., & Rossetti, G. (2019, December). Eva: Attribute-Aware Network Segmentation. In International Conference on Complex Networks and Their Applications (pp. 141-151). Springer, Cham.
- iLouvain: Combe D., Largeron C., Géry M., Egyed-Zsigmond E. “I-Louvain: An Attributed Graph Clustering Method”. <https://link.springer.com/chapter/10.1007/978-3-319-24465-5_16> In: Fromont E., De Bie T., van Leeuwen M. (eds) Advances in Intelligent Data Analysis XIV. IDA (2015). Lecture Notes in Computer Science, vol 9385. Springer, Cham
- tiles: Rossetti, G., Pappalardo, L., Pedreschi, D., & Giannotti, F. (2017). Tiles: an online algorithm for community discovery in dynamic social networks. Machine Learning, 106(8), 1213-1241.
- lpam: Ponomarenko, A., Pitsoulis, L., and Shamshetdinov, M. (2021). Overlapping community detection in networks based on link partitioning and partitioning around medoids <https://arxiv.org/abs/1907.08731>
Evaluation measures¶
- Omega: Gabriel Murray, Giuseppe Carenini, and Raymond Ng. 2012. Using the omega index for evaluating abstractive algorithms detection. In Proceedings of Workshop on Evaluation Metrics and System Comparison for Automatic Summarization. Association for Computational Linguistics, Stroudsburg, PA, USA, 10-18.
- F1: Rossetti, G., Pappalardo, L., & Rinzivillo, S. (2016). A novel approach to evaluate algorithms detection internal on ground truth. In Complex Networks VII (pp. 133-144). Springer, Cham.
- NF1:
- Rossetti, G., Pappalardo, L., & Rinzivillo, S. (2016). A novel approach to evaluate algorithms detection internal on ground truth.
- Rossetti, G. (2017). : RDyn: graph benchmark handling algorithms dynamics. Journal of Complex Networks. 5(6), 893-912.
- Adjusted_rand_index: Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of classification, 2(1), 193-218.
- Adjusted_mutual_information: Vinh, N. X., Epps, J., & Bailey, J. (2010). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11(Oct), 2837-2854.
- Variation_of_information: Meila, M. (2007). Comparing clusterings - an information based distance. Journal of Multivariate Analysis, 98, 873-895. doi:10.1016/j.jmva.2006.11.013
- Overlapping_normalized_mutual_information_MGH: McDaid, A. F., Greene, D., & Hurley, N. (2011). Normalized mutual information to evaluate overlapping community finding algorithms.. arXiv preprint arXiv:1110.2515. Chicago
- Overlapping_normalized_mutual_information_LFK: Lancichinetti, A., Fortunato, S., & Kertesz, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015.
- Newman_girvan_modularity: Newman, M.E.J. & Girvan, M. Finding and evaluating algorithms structure in networks. Physical Review E 69, 26113(2004).
- Erdos_renyi_modularity: Erdos, P., & Renyi, A. (1959). On random graphs I. Publ. Math. Debrecen, 6, 290-297.
- Modularity_density: Li, Z., Zhang, S., Wang, R. S., Zhang, X. S., & Chen, L. (2008). Quantitative function for algorithms detection. Physical review E, 77(3), 036109.
- Z_modularity: Miyauchi, Atsushi, and Yasushi Kawase. Z-score-based modularity for algorithms detection in networks. PloS one 11.1 (2016): e0147805.
- Surprise & Significance: Traag, V. A., Aldecoa, R., & Delvenne, J. C. (2015). Detecting communities using asymptotical surprise .. Physical Review E, 92(2), 022816.
- average_internal_degree: Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences, 101(9), 2658-2663.
- conductance: Shi, J., Malik, J.: Normalized cuts and image segmentation. Departmental Papers (CIS), 107 (2000)
- cut_ratio: Fortunato, S.: Community detection in graphs. Physics reports 486(3-5), 75–174 (2010)
- edges_inside: Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences, 101(9), 2658-2663.
- expansion: Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences, 101(9), 2658-2663.
- internal_edge_density: Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., & Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences, 101(9), 2658-2663.
- normalized_cut: Shi, J., Malik, J.: Normalized cuts and image segmentation. Departmental Papers (CIS), 107 (2000)
- fraction_over_median_degree: Yang, J and Leskovec, J.: Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42(1), 181–213 (2015)
- max_odf: Flake, G.W., Lawrence, S., Giles, C.L., et al.: Efficient identification of web communities. In: KDD, vol. 2000, pp. 150–160 (2000)
- avg_odf: Flake, G.W., Lawrence, S., Giles, C.L., et al.: Efficient identification of web communities. In: KDD, vol. 2000, pp. 150–160 (2000)
- flake_odf: Flake, G.W., Lawrence, S., Giles, C.L., et al.: Efficient identification of web communities. In: KDD, vol. 2000, pp. 150–160 (2000)
- triangle_participation_ratio: Yang, J and Leskovec, J.: Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42(1), 181–213 (2015)
- link_modularity: Nicosia, V., Mangioni, G., Carchiolo, V., Malgeri, M.: Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics: Theory and Experiment 2009(03), 03024 (2009)
Researches using CDlib¶
So far it has been used to support the following research activities:
- Hubert, M. Master Thesis. (2020) Crawling and Analysing code review networks on industry and open source data
- Pister, A., Buono, P., Fekete, J. D., Plaisant, C., & Valdivia, P. (2020). Integrating Prior Knowledge in Mixed Initiative Social Network Clustering. arXiv preprint arXiv:2005.02972.
- Mohammadmosaferi, K. K., & Naderi, H. (2020). Evolution of communities in dynamic social networks: An efficient map-based approach. Expert Systems with Applications, 147, 113221.
- Cazabet, Remy, Souaad Boudebza, and Giulio Rossetti. “Evaluating community detection algorithms for progressively evolving graphs.” arXiv preprint arXiv:2007.08635 (2020).
- Citraro, Salvatore, and Giulio Rossetti. “Identifying and exploiting homogeneous communities in labeled networks.” Applied Network Science 5.1 (2020): 1-20.
- Citraro, Salvatore, and Giulio Rossetti. “Eva: Attribute-Aware Network Segmentation.” International Conference on Complex Networks and Their Applications. Springer, Cham, 2019.
- Rossetti, Giulio. “ANGEL: efficient, and effective, node-centric community discovery in static and dynamic networks.” Applied Network Science 5.1 (2020): 1-23.
- Jaiswal, Rajesh, and Sheela Ramanna. “Detecting Overlapping Communities Using Distributed Neighbourhood Threshold in Social Networks.” International Joint Conference on Rough Sets. Springer, Cham, 2020.
- Rossetti, Giulio. “Exorcising the Demon: Angel, Efficient Node-Centric Community Discovery.” International Conference on Complex Networks and Their Applications. Springer, Cham, 2019.