Skip to main content

Dense subgraph discovery

Project description

dsd_pip

This package contains three algorithms that solve dense subgraph problem exactly or approximately, including Goldberg's max flow based algorithm [1], charikar's greedy peeling algorithm [2], and state-of-the-art flowless (greedy++) algorithm [3].

We also leverage all algorithms to find k-clique dense subgraph, given list of k-cliques in a certain graph. Remind this can be done with algorithms like KClist [5]. We follow [4] when contructing clique based max flow graph.

To install the package, run

pip install dsd

Check https://github.com/c752334430/dsd_pip/blob/main/dsd_package_demo.ipynb to see how to use the package.

[1] A. V. Goldberg. Finding a maximum density subgraph. University of California Berkeley, CA, 1984.

[2] M. Charikar. Greedy approximation algorithms for finding dense components in a graph. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 84–95. Springer, 2000

[3] Boob D., Gao Y., Peng R., Sawlani S., Tsourakakis C.~E., Wang D., Wang J., Flowless: Extracting Densest Subgraphs Without Flow Computations, arXiv e-prints, 2019.

[4] Shuguang Hu, Xiaowei Wu, and T-H. Hubert Chan. 2017. Maintaining Densest Subsets Efficiently in Evolving Hypergraphs. Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. Association for Computing Machinery, New York, NY, USA, 929–938. DOI:https://doi.org/10.1145/3132847.3132907

[5] Maximilien Danisch, Oana Balalau, and Mauro Sozio. 2018. Listing k-cliques in Sparse Real-World Graphs*. In Proceedings of the 2018 World Wide Web Conference (WWW '18). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 589–598. DOI:https://doi.org/10.1145/3178876.3186125

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

dsd-0.0.3.tar.gz (9.9 kB view details)

Uploaded Source

Built Distribution

dsd-0.0.3-py3-none-any.whl (9.3 kB view details)

Uploaded Python 3

File details

Details for the file dsd-0.0.3.tar.gz.

File metadata

  • Download URL: dsd-0.0.3.tar.gz
  • Upload date:
  • Size: 9.9 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.1 importlib_metadata/3.10.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.60.0 CPython/3.8.5

File hashes

Hashes for dsd-0.0.3.tar.gz
Algorithm Hash digest
SHA256 b86ef44b5fd569d264c81a3a3a672245b974c8580efc94e91e3ac533da205cdc
MD5 93c91dc58b65b930afae9dcaa1a2591a
BLAKE2b-256 8d62aa72b2c22ce260f72f1a9c551d8f606456fd65c351c84f89f6d9af4230bb

See more details on using hashes here.

File details

Details for the file dsd-0.0.3-py3-none-any.whl.

File metadata

  • Download URL: dsd-0.0.3-py3-none-any.whl
  • Upload date:
  • Size: 9.3 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.4.1 importlib_metadata/3.10.0 pkginfo/1.7.0 requests/2.25.1 requests-toolbelt/0.9.1 tqdm/4.60.0 CPython/3.8.5

File hashes

Hashes for dsd-0.0.3-py3-none-any.whl
Algorithm Hash digest
SHA256 2cd33f1c7d2804beb773462c565149eb0c182678cc5e2adc77ebf22cfe1b73df
MD5 27df01c03cc678812960ee20fcd8bf8b
BLAKE2b-256 ec3e9dc3e670424e8b871cc686dd4260242824da74b4bafa6cbe260375e29542

See more details on using hashes here.

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page