[Desiderata] Community Detection algorithms

[GiulioRossetti]

This Issue is a container for CD methods that CDlib users would like to see integrated into library future releases.

When adding a new algorithm to the issue please specify:

• Name
• Reference Paper
• Reference Implementation (if any), and programming language
• Graph supported: directed/undirected, weighted/unweighted, bipartite, temporal, attributed,...

Methods with existing python implementation (not leveraging on C/C++ dependencies) will be prioritized.

[BradKML]

• Generalized Louvain
• https://arxiv.org/abs/1804.03733
• https://github.com/michaelschaub/generalizedLouvain (MATLAB)
• Directed Network

[BradKML]

• OSLOM
• used in https://ccc.inaoep.mx/~ariel/A%20consensus%20graph%20clustering%20algorithm%20for%20directed%20networks.pdf and http://www.oslom.org/ and https://arxiv.org/abs/1012.2363
• Python library from Cytoscape https://github.com/idekerlab/cdoslom and https://pypi.org/project/oslom-runner/ (runner that requires a compiled C implementation)
• Directed Network

[BradKML]

• Community Detection in Social Networks Using Affinity Propagation with Adaptive Similarity Matrix
• https://www.liebertpub.com/doi/pdf/10.1089/big.2019.0143
• Can't Find Public Reference
• Undirected Netework

[BradKML]

• Role-based Label Propagation Algorithm for Community Detection
• https://arxiv.org/ftp/arxiv/papers/1601/1601.06307.pdf
• Can't Find Public Reference
• Undirected Network

[BradKML]

• Directed Louvain Algorithm
• https://hal.archives-ouvertes.fr/hal-01231784/document OR https://arxiv.org/pdf/1308.0971.pdf OR https://jmlr.org/papers/volume21/18-581/18-581.pdf OR https://hal.archives-ouvertes.fr/hal-01849601v2/document
• https://github.com/nicolasdugue/DirectedLouvain and https://github.com/graphology/graphology-communities-louvain#references
• Directed Graph as an alternative to Undirected Louvain

[BradKML]

• LexDFS
• https://arxiv.org/pdf/1410.2105.pdf
• No public references
• Undirected Unweighted Graph

[BradKML]

• LINCOM
• https://arxiv.org/pdf/1707.04459.pdf
• https://github.com/sna-lincom/LINCOM
• Undirected Unweighted Graph

[BradKML]

• Pregel
• https://kowshik.github.io/JPregel/pregel_paper.pdf
• No public reference
• Directed Graph

[BradKML]

• NetWalk
• http://www.mpikg.mpg.de/rl/P/archive/190.pdf
• No public reference
• Unknown if directed or undirected

[BradKML]

• A Local Method for Detecting Communities
• https://arxiv.org/pdf/cond-mat/0412482.pdf
• No public reference
• Unknown if directed or undirected

[BradKML]

• Community detection in complex networks using Extremal Optimization
• https://arxiv.org/pdf/cond-mat/0501368.pdf
• No public reference
• Unknown if directed or undirected

[BradKML]

• Finding communities in linear time: a physics approach
• https://arxiv.org/pdf/cond-mat/0310600.pdf
• No public reference
• Unknown if directed or undirected

[BradKML]

• Detecting Network Communities: a new systematic and efficient algorithm
• https://arxiv.org/pdf/cond-mat/0404652.pdf
• No public reference
• Unknown if directed or undirected

[BradKML]

• Community extraction for social networks
• https://www.pnas.org/content/108/18/7321
• No public reference
• Undirected Networks

[BradKML]

(side note) There is a list of existing algorithms that are in Python or Java in https://github.com/RapidsAtHKUST/CommunityDetectionCodes/blob/master/Survey/Overlapping-Community-Detection-Codes.md

Note : The only python implementation reported is for Demon (already in cdlib). Others are prevalently in C/C++

[BradKML]

• A link clustering based overlapping community detection algorithm
• https://www.sciencedirect.com/science/article/pii/S0169023X13000499
• No public reference
• Undirected Graph

[BradKML]

• SPAEM
• https://arxiv.org/pdf/0710.3422.pdf
• No public reference
• Undirected and Unweighted

[BradKML]

• SSDE-Cluster:
• https://ieeexplore.ieee.org/abstract/document/6113211/
• No public reference
• Unknown if directed or undirected

[BradKML]

• RankCom
• https://ieeexplore.ieee.org/document/7226696
• No public reference
• Directed Unweighted

[BradKML]

• BiMLPA
• https://link.springer.com/chapter/10.1007/978-3-030-38965-9_2
• https://github.com/marblet/BiMLPA
• Bipartite

Already implemented in CDlib

---

• Bilouvain
• https://journals.aps.org/pre/abstract/10.1103/PhysRevE.76.066102
• https://github.com/sknetwork-team/scikit-network and https://github.com/cbongiorno/Bipartite-Tools

• Bipartite

• Community Detection in Bipartite Networks with Stochastic Blockmodels
• https://arxiv.org/pdf/2001.11818.pdf
• https://github.com/junipertcy/bipartiteSBM

• Bipartite

• Overlapping Community Detection of Bipartite Networks Based on a Novel Community Density
• https://doi.org/10.3390/fi13040089
• No public reference

• Bipartite

• Bɪ-CомDᴇт: Community Detection in Bipartite Networks
• https://www.sciencedirect.com/science/article/pii/S1877050919313687
• No Public reference

• Bipartite

• Leiden
• https://github.com/vtraag/leidenalg/issues/27
• https://leidenalg.readthedocs.io/en/latest/multiplex.html#bipartite
• Bipartite

Already implemented in CDlib

---

• Modularity and community detection in bipartite networks
• https://arxiv.org/abs/0707.1616
• https://github.com/genisott/pycondor

• Bipartite

• bipartiteSBM-KL
• http://danlarremore.com/pdf/2014_LCJ_EfficientlyInferringCommunityStructureInBipartiteNetworks_PRE.pdf
• https://github.com/junipertcy/bipartiteSBM-KL

• Bipartite

• Efficiently inferring community structure in bipartite networks
• https://www.jstage.jst.go.jp/article/imt/5/1/5_1_184/_pdf
• https://github.com/junipertcy/bipartiteSBM-KL

• Bipartite

• Efficient bi-triangle counting for large bipartite networks
• https://dl.acm.org/doi/10.14778/3447689.3447702
• No reference

• Bipartite

• ComSim
• https://arxiv.org/pdf/1705.04863.pdf
• https://github.com/rtackx/ComSim

• Bipartite

• A method for detecting modules in quantitative bipartite networks
• https://besjournals.onlinelibrary.wiley.com/doi/10.1111/2041-210X.12139
• No ref
• Bipartite

[BradKML]

• A new Approach of Community Detection Based on seed node
• https://github.com/bheemnitd/Community-Detection-Based-On-Seed-Node/blob/master/%5BThesis%20PAPER%5D%20A%20new%20Approach%20of%20Community%20Detection%20Based%20on%20seed%20node.pdf
• https://github.com/bheemnitd/Community-Detection-Based-On-Seed-Node/blob/master/mynetworkx.ipynb
• Undirected, Unweighted

[BradKML]

• Anti-triangle centrality-based community detection in complex networks
• Not Known
• https://doi.org/10.1049/iet-syb.2013.0039
• Undirected & Unweighted

[BradKML]

• Hierarchical community Decoding Framework
• https://github.com/fanzheng10/HiDeF
• Zheng, F., Zhang, S., Churas, C. et al., HiDeF: identifying persistent structures in multiscale ‘omics data. Genome Biol 22, 21 (2021).
• Undirected

[BradKML]

• Weighted Weak Community Detection
• https://github.com/velicast/WMW
• Three papers:
  • Dynamic Structural Similarity on Graphs: https://arxiv.org/abs/1805.01419
  • Fast Heuristic Algorithm for Multi-Scale Hierarchical Community Detection: https://dl.acm.org/citation.cfm?doid=3110025.3110125
  • High-Quality Disjoint and Overlapping Community Structure in Large-Scale Complex Networks: https://arxiv.org/abs/1805.12238
• Undirected and Weighted

[Rose62130800101]

• Coverage Metric
• Conductance Metric
• Performance Metrics

. References:

• Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale

  • https://doi.org/10.1371/journal.pone.0159161.g002

• Gaertler M. (2005) Clustering. In: Brandes U., Erlebach T. (eds) Network Analysis. Lecture Notes in Computer Science, vol 3418. Springer, Berlin, Heidelberg. -https://doi.org/10.1007/978-3-540-31955-9_8

• Undirected and Unweighted Graph

[Rose62130800101]

As a result of the Community detection Algorithm we get a number of communities: For some comparison purposes we need the following 2 types of edges :

A number of internal and external edges of each community. like Cluster 1: internal edges = 5 and external edges are 3 (edges which both ends are present in the same community ) Clsuter 2 : internal edges = 7 and external = 4 (both ends are present in various communities knows as external edges)

[GiulioRossetti]

@Rose62130800101

Here's the documentation for the remote ground truth loading facility: https://cdlib.readthedocs.io/en/latest/reference/generated/cdlib.datasets.fetch_network_ground_truth.html#cdlib.datasets.fetch_network_ground_truth

You are encountering such error because the function you are using is not the proper one.

PS: next time open a new issue, do not add comments to an existing one having a different subject.