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
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
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
Algorithm | Hash digest | |
---|---|---|
SHA256 | b86ef44b5fd569d264c81a3a3a672245b974c8580efc94e91e3ac533da205cdc |
|
MD5 | 93c91dc58b65b930afae9dcaa1a2591a |
|
BLAKE2b-256 | 8d62aa72b2c22ce260f72f1a9c551d8f606456fd65c351c84f89f6d9af4230bb |
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
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2cd33f1c7d2804beb773462c565149eb0c182678cc5e2adc77ebf22cfe1b73df |
|
MD5 | 27df01c03cc678812960ee20fcd8bf8b |
|
BLAKE2b-256 | ec3e9dc3e670424e8b871cc686dd4260242824da74b4bafa6cbe260375e29542 |