cdlib icon indicating copy to clipboard operation
cdlib copied to clipboard
verified publisher icon GiulioRossetti

[Desiderata] Community Detection algorithms

Open GiulioRossetti opened this issue 4 years ago • 27 comments

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.

GiulioRossetti avatar Jun 04 '21 08:06 GiulioRossetti

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

BradKML avatar Jun 08 '21 03:06 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 avatar Jun 10 '21 11:06 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 avatar Jun 10 '21 11:06 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 avatar Jun 10 '21 11:06 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 avatar Jun 10 '21 11:06 BradKML

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

BradKML avatar Jun 22 '21 00:06 BradKML

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

BradKML avatar Jun 22 '21 00:06 BradKML

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

BradKML avatar Jun 22 '21 00:06 BradKML

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

BradKML avatar Jun 22 '21 01:06 BradKML

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

BradKML avatar Jun 22 '21 01:06 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 avatar Jun 22 '21 01:06 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 avatar Jun 22 '21 01:06 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 avatar Jun 22 '21 01:06 BradKML

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

BradKML avatar Jun 22 '21 01:06 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 avatar Jun 22 '21 02:06 BradKML

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

BradKML avatar Jun 22 '21 02:06 BradKML

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

BradKML avatar Jun 22 '21 02:06 BradKML

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

BradKML avatar Jun 22 '21 02:06 BradKML

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

BradKML avatar Sep 24 '21 05:09 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 avatar Oct 07 '21 17:10 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 avatar Oct 25 '21 06:10 BradKML

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

BradKML avatar Nov 01 '21 04:11 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 avatar Jan 19 '22 06:01 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

BradKML avatar Jan 19 '22 06:01 BradKML

  • 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 avatar Feb 28 '22 10:02 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)

Rose62130800101 avatar Feb 28 '22 10:02 Rose62130800101

@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.

GiulioRossetti avatar Feb 28 '22 12:02 GiulioRossetti