{ "info": { "author": "Chien-Chun Ni", "author_email": "saibalmars@gmail.com", "bugtrack_url": null, "classifiers": [ "License :: OSI Approved :: Apache Software License", "Operating System :: OS Independent", "Programming Language :: Python :: 3" ], "description": "# GraphRicciCurvature\nCompute Discrete Ricci curvature and Ricci flow on NetworkX graph.\n\n[![License](https://img.shields.io/badge/License-Apache%202.0-blue.svg)](https://opensource.org/licenses/Apache-2.0)\n\n-----\nThis work computes the **Ollivier-Ricci Curvature**[Ni], **Ollivier-Ricci Flow**[Ni2,Ni3] and **Forman-Ricci Curvature**(or **Forman curvature**)[Sreejith].\n\n

\n\n

\n\nCurvature is a geometric property to describe the local shape of an object. \nIf we draw two parallel paths on a surface with positive curvature like a sphere, these two paths move closer to each other while for a negative curved surface like saddle, these two paths tend to be apart.\n\nIn [Ni], we observe that the edge Ricci curvature play an important role in graph structure. An edge with positive curvature represents an edge within a cluster, while a negatively curved edge tents to be a bridge within clusters. Also, negatively curved edges are highly related to graph connectivity, with negatively curved edges removed from a connected graph, the graph soon become disconnected.\n\nRicci flow is a process to uniformized the edge Ricci curvature of the graph. For a given graph, the Ricci flow gives a \"Ricci flow metric\" on each edge as edge weights, such that under these edge weights, the Ricci curvature of the graph is mostly equal everywhere. In [Ni3], this \"Ricci flow metric\" is shown to be able to detect communities.\n\nBoth Ricci curvature and Ricci flow metric can be act as a graph fingerprint. Different graph gives different edge Ricci curvature distributions and different Ricci flow metric. \n\nVideo demonstration of Ricci flow for community detection:\n

\n\n\n\n

\n\n## Package Requirement\n\n* [NetworkX](https://github.com/networkx/networkx) (Based Graph library)\n* [CVXPY](https://github.com/cvxgrp/cvxpy) (LP solver for Optimal transportation)\n* [NumPy](https://github.com/numpy/numpy) (CVXPY support)\n* [POT](https://github.com/rflamary/POT) (For approximate Optimal transportation distance)\n\n* [NetworKit](https://github.com/kit-parco/networkit) (*Optional: for faster parallel shortest path computation*)\n\n\n## Installation\n\n### Installing via pip\n\n```bash\npip3 install [--user] GraphRicciCurvature\n```\n\n### Installing via pip (with NetworKit)\n\n```bash\npip3 install [--user] \"GraphRicciCurvature [faster_apsp]\" \n```\n- Notice that the NetworKit is not required. It is optional for faster all pair shortest path computation for larger graphs that NetworkX performs poorly. If the installation failed, please refer to [NetworKit' Installation instructions](https://github.com/networkit/networkit#installation-instructions). In most of the cast build this package from source is recommended.\n\n\n## Getting Started\n- See the jupyter notebook tutorial on [nbviewer](https://nbviewer.jupyter.org/github/saibalmars/GraphRicciCurvature/blob/master/notebooks/tutorial.ipynb) or [github](notebooks/tutorial.ipynb) for a walk through for the basic usage of Ricci curvature, Ricci flow, and Ricci flow for community detection.\n\n## Simple Example\n\n```python\nimport networkx as nx\nfrom GraphRicciCurvature.OllivierRicci import OllivierRicci\nfrom GraphRicciCurvature.FormanRicci import FormanRicci\n\n# import an example NetworkX karate club graph\nG = nx.karate_club_graph()\n\n# compute the Ollivier-Ricci curvature of the given graph G\norc = OllivierRicci(G, alpha=0.5, verbose=\"INFO\")\norc.compute_ricci_curvature()\nprint(\"Karate Club Graph: The Ollivier-Ricci curvature of edge (0,1) is %f\" % orc.G[0][1][\"ricciCurvature\"])\n\n# compute the Forman-Ricci curvature of the given graph G\nfrc = FormanRicci(G)\nfrc.compute_ricci_curvature()\nprint(\"Karate Club Graph: The Forman-Ricci curvature of edge (0,1) is %f\" % frc.G[0][1][\"formanCurvature\"])\n\n# -----------------------------------\n# Compute Ricci flow metric - Optimal Transportation Distance\nG = nx.karate_club_graph()\norc_OTD = OllivierRicci(G, alpha=0.5, method=\"OTD\", verbose=\"INFO\")\norc_OTD.compute_ricci_flow(iterations=10)\n\n```\n\nMore example in [example.py](example.py).\n\n----\n## Contact\n\nPlease contact [Chien-Chun Ni](http://www3.cs.stonybrook.edu/~chni/).\n\n\n-----\n## Reference\n\n[Ni]: Ni, C.-C., Lin, Y.-Y., Gao, J., Gu, X., and Saucan, E. 2015. \"Ricci curvature of the Internet topology\" (Vol. 26, pp. 2758\u20132766). Presented at the 2015 IEEE Conference on Computer Communications (INFOCOM), IEEE. [arXiv](https://arxiv.org/abs/1501.04138)\n\n[Ni2]: Ni, C.-C., Lin, Y.-Y., Gao, J., and Gu, X. 2018. \"Network Alignment by Discrete Ollivier-Ricci Flow\", Graph Drawing 2018, [arXiv](https://arxiv.org/abs/1809.00320)\n\n[Ni3]: Ni, C.-C., Lin, Y.-Y., Luo, F. and Gao, J. 2019. \"Community Detection on Networks with Ricci Flow\", Scientific Reports, [arXiv](https://arxiv.org/abs/1907.03993)\n\n[Sreejith]: Sreejith, R. P., Karthikeyan Mohanraj, J\u00fcrgen Jost, Emil Saucan, and Areejit Samal. 2016. \u201cForman Curvature for Complex Networks.\u201d Journal of Statistical Mechanics: Theory and Experiment 2016 (6). IOP Publishing: 063206. [arxiv](https://arxiv.org/abs/1603.00386)\n\n\n", "description_content_type": "text/markdown", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/saibalmars/GraphRicciCurvature", "keywords": "", "license": "", "maintainer": "", "maintainer_email": "", "name": "GraphRicciCurvature", "package_url": "https://pypi.org/project/GraphRicciCurvature/", "platform": "", "project_url": "https://pypi.org/project/GraphRicciCurvature/", "project_urls": { "Homepage": "https://github.com/saibalmars/GraphRicciCurvature" }, "release_url": "https://pypi.org/project/GraphRicciCurvature/0.2.1.1/", "requires_dist": [ "networkx", "numpy", "cvxpy", "pot", "networkit ; extra == 'faster_apsp'" ], "requires_python": "", "summary": "Compute discrete Ricci curvatures and Ricci flow on NetworkX graphs.", "version": "0.2.1.1" }, "last_serial": 5550636, "releases": { "0.1": [ { "comment_text": "", "digests": { "md5": "69e91d0f084554c97b7fc35036765ec6", "sha256": "5a4c849d76cd2fe5343d938a3b543551d4711292d357d1ce2985f28da2404ede" }, "downloads": -1, "filename": "GraphRicciCurvature-0.1-py3-none-any.whl", "has_sig": false, "md5_digest": "69e91d0f084554c97b7fc35036765ec6", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 14210, "upload_time": "2019-07-03T22:43:01", "url": "https://files.pythonhosted.org/packages/c8/ec/b0a75488e008eebe67b79738f6759be1aa793facce1f74f5349bc8916d77/GraphRicciCurvature-0.1-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "5958403c2e1de6fc04f701b8f7eee51b", "sha256": "a2ba04b57137e9d848a3331b98d6babade9e0fb1b3344f050738f7f44e1c72e5" }, "downloads": -1, "filename": "GraphRicciCurvature-0.1.tar.gz", "has_sig": false, "md5_digest": "5958403c2e1de6fc04f701b8f7eee51b", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 7557, "upload_time": "2019-07-03T22:43:04", "url": "https://files.pythonhosted.org/packages/4e/88/4eaa263865e1c21fb60c92e70398801fd6b11d2a308a146af9a383eba86b/GraphRicciCurvature-0.1.tar.gz" } ], "0.2": [ { "comment_text": "", "digests": { "md5": "e9d1b45d0c5c0de4680bd2fadea3f800", "sha256": "c71d5963b7f92f8a1f1b2d549d77e418b5754e620ef60ad4577027ca5ad26359" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2-py3-none-any.whl", "has_sig": false, "md5_digest": "e9d1b45d0c5c0de4680bd2fadea3f800", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 16750, "upload_time": "2019-07-15T08:14:48", "url": "https://files.pythonhosted.org/packages/cb/9f/a5f632f373bf2e0c519a679861de4f52611ce21e18403ea14d3122f7fe83/GraphRicciCurvature-0.2-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "2cc5eee7c7a2bd0494e12648bac79d9e", "sha256": "ed9ddff62e433e06767dc8a0d4a585f41f4a7c5ccab276258bbfe56001424df2" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2.tar.gz", "has_sig": false, "md5_digest": "2cc5eee7c7a2bd0494e12648bac79d9e", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 9085, "upload_time": "2019-07-15T08:14:50", "url": "https://files.pythonhosted.org/packages/64/c3/5e4704d9604b1f5ca39a2d14e9fca3da12b3630fab291f546b0495c5c99f/GraphRicciCurvature-0.2.tar.gz" } ], "0.2.1": [ { "comment_text": "", "digests": { "md5": "fcf98913716b4218c01470485d417edd", "sha256": "4c51b0b525059bc2547e9538eef8f68424ebc8b150dec19133a0944e5de67f20" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2.1-py3-none-any.whl", "has_sig": false, "md5_digest": "fcf98913716b4218c01470485d417edd", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 16946, "upload_time": "2019-07-18T11:15:36", "url": "https://files.pythonhosted.org/packages/65/7e/9644bb3f78db8d2aeb47176975e31adf8eb064a20a80b2722a2c3b91032b/GraphRicciCurvature-0.2.1-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "4e029ef8361e21f053ec5d4807affbb9", "sha256": "ca51a1c75541cc094ee5bce8d4c306132ee9de097269a7b35e196300d8ebf5a0" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2.1.tar.gz", "has_sig": false, "md5_digest": "4e029ef8361e21f053ec5d4807affbb9", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 9331, "upload_time": "2019-07-18T11:15:38", "url": "https://files.pythonhosted.org/packages/36/70/8d2f91f8c49ce1d4388ec82dc222bf7b2f22ed3089f37ad64aec639c7b7a/GraphRicciCurvature-0.2.1.tar.gz" } ], "0.2.1.1": [ { "comment_text": "", "digests": { "md5": "b994c881d89fc40aecf82c9eae2d72c2", "sha256": "75ffeddb967a034a8a48d44a03c67d9103ba81d4666ae685ecc37b8f821e9974" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2.1.1-py3-none-any.whl", "has_sig": false, "md5_digest": "b994c881d89fc40aecf82c9eae2d72c2", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 16981, "upload_time": "2019-07-18T11:37:48", "url": "https://files.pythonhosted.org/packages/29/39/6a069f14945c5459c193b842b604029f5aca1a5faaaff3dd672fbaca3ab5/GraphRicciCurvature-0.2.1.1-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "146744f57f68fd5b05189f282b6bf048", "sha256": "4d496957ab2d42ad3ded5f2247cb01274e94c1a56ff7cb2ce143a7ab7bb01d26" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2.1.1.tar.gz", "has_sig": false, "md5_digest": "146744f57f68fd5b05189f282b6bf048", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 9339, "upload_time": "2019-07-18T11:37:49", "url": "https://files.pythonhosted.org/packages/8c/84/67e06d609805bdd6fbc968585584f91674a45d10beeed008c73fa6dd6779/GraphRicciCurvature-0.2.1.1.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "b994c881d89fc40aecf82c9eae2d72c2", "sha256": "75ffeddb967a034a8a48d44a03c67d9103ba81d4666ae685ecc37b8f821e9974" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2.1.1-py3-none-any.whl", "has_sig": false, "md5_digest": "b994c881d89fc40aecf82c9eae2d72c2", "packagetype": "bdist_wheel", "python_version": "py3", "requires_python": null, "size": 16981, "upload_time": "2019-07-18T11:37:48", "url": "https://files.pythonhosted.org/packages/29/39/6a069f14945c5459c193b842b604029f5aca1a5faaaff3dd672fbaca3ab5/GraphRicciCurvature-0.2.1.1-py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "146744f57f68fd5b05189f282b6bf048", "sha256": "4d496957ab2d42ad3ded5f2247cb01274e94c1a56ff7cb2ce143a7ab7bb01d26" }, "downloads": -1, "filename": "GraphRicciCurvature-0.2.1.1.tar.gz", "has_sig": false, "md5_digest": "146744f57f68fd5b05189f282b6bf048", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 9339, "upload_time": "2019-07-18T11:37:49", "url": "https://files.pythonhosted.org/packages/8c/84/67e06d609805bdd6fbc968585584f91674a45d10beeed008c73fa6dd6779/GraphRicciCurvature-0.2.1.1.tar.gz" } ] }