{
    "info": {
        "author": "Ping-Ko Chiu, Peter Diao, Olewasanmi Koyejo",
        "author_email": "pchiu5@illinois.edu, peter.z.diao@gmail.com, sanmi@illinois.edu",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 3 - Alpha",
            "Intended Audience :: Developers",
            "License :: OSI Approved :: MIT License",
            "Programming Language :: Python :: 2",
            "Programming Language :: Python :: 3",
            "Topic :: Scientific/Engineering :: Information Analysis"
        ],
        "description": "=======\nCutnorm\n=======\n\nApproximation via Gaussian Rounding and Optimization with Orthogonality Constraints\n-----------------------------------------------------------------------------------\n\nThis package computes the approximations to the cutnorm of matrices using some of the techniques detailed by Alon and Noar [ALON2004]_ and a fast optimization algorithm by Wen and Yin [WEN2013]_.\n\nRead the documentation_.\n\n.. _documentation: https://pingkoc.github.io/cutnorm/cutnorm.html\n\nInstallation\n------------\n\nUse pip_ to install the package.\nInstall from terminal as follows::\n\n  $ pip install cutnorm\n\n.. _pip: http://www.pip-installer.org/en/latest/\n\nExample Usage\n-------------\n\nGiven the adjacency matrices of two simple graphs A and B, we wish to compute a norm for the difference matrix (A - B) between the two graphs. An obvious display of the advantages of using a cutnorm over l1 norm is to consider the value of the norms on `Erdos-Renyi random graphs`_.\n\n.. _`Erdos-Renyi random graphs`: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model\n\nGiven two Erdos-Renyi random graphs with constant n and p=0.5, the edit distance (l1 norm) of the difference (after normalization) is 0.5 with large probability. An l1 norm of 1 implies the two matrices are completely different, 0 implies identity, and 0.5 is somewhere in between. However, these two graphs have the same global structure. As n approaches infinity, A and B converges to the same graphon object that is 0.5 everywhere. The edit distance fails as a notion of 'distance' between the two graphs in the perspective of global structural similarity as discussed by Lovasz [LOVASZ2009]_. The cutnorm is a measure of distance that reflects global structural similarity. In fact, the cutnorm of the difference for this example approaches 0 as n grows.\n\nBelow is an example of using the cutnorm package and tools. \n\n.. code:: python\n\n  import numpy as np\n  from cutnorm import compute_cutnorm, tools\n\n  # Generate Erdos Renyi Random Graph (Simple/Undirected)\n  n = 100\n  p = 0.5\n  erdos_renyi_a = tools.sbm.erdos_renyi(n, p, symmetric=True)\n  erdos_renyi_b = tools.sbm.erdos_renyi(n, p, symmetric=True)\n\n  # Compute l1 norm\n  normalized_diff = (erdos_renyi_a - erdos_renyi_b) / n**2\n  l1 = np.linalg.norm(normalized_diff.flatten(), ord=1)\n\n  # Compute cutnorm\n  cutn_round, cutn_sdp, info = compute_cutnorm(erdos_renyi_a, erdos_renyi_b)\n\n  print(\"l1 norm: \", l1)  # prints l1 norm value near ~0.5\n  print(\"cutnorm rounded: \",\n        cutn_round)  # prints cutnorm rounded solution near ~0\n  print(\"cutnorm sdp: \", cutn_sdp)  # prints cutnorm sdp solution near ~0\n\n----\n\n.. [ALON2004] Noga Alon and Assaf Naor. 2004. Approximating the cut-norm via Grothendieck's inequality. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (STOC '04). ACM, New York, NY, USA, 72-80. DOI: http://dx.doi.org/10.1145/1007352.1007371\n.. [WEN2013] Zaiwen Wen and Wotao Yin. 2013. A feasible method for optimization with orthogonality constraints. Math. Program. 142, 1-2 (December 2013), 397-434. DOI: https://doi.org/10.1007/s10107-012-0584-1\n.. [LOVASZ2009] Lovasz, L. 2009. Very large graphs. ArXiv:0902.0132 [Math]. Retrieved from http://arxiv.org/abs/0902.0132\n",
        "description_content_type": "",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/pingkoc/cutnorm",
        "keywords": "",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "cutnorm",
        "package_url": "https://pypi.org/project/cutnorm/",
        "platform": "",
        "project_url": "https://pypi.org/project/cutnorm/",
        "project_urls": {
            "Homepage": "https://github.com/pingkoc/cutnorm"
        },
        "release_url": "https://pypi.org/project/cutnorm/0.1.9/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "Cutnorm approximation via Gaussian Rounding and Optimization with Orthogonality Constraints",
        "version": "0.1.9"
    },
    "last_serial": 3841615,
    "releases": {
        "0.1.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "618070083a4c1871cc8ffd87c65ba243",
                    "sha256": "b3a1a284d8b537099409450edc564598b22d47b151a0c84ecf745344f6005bc9"
                },
                "downloads": -1,
                "filename": "cutnorm-0.1.1.tar.gz",
                "has_sig": false,
                "md5_digest": "618070083a4c1871cc8ffd87c65ba243",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 6442,
                "upload_time": "2018-01-22T04:29:49",
                "url": "https://files.pythonhosted.org/packages/4c/95/726a55ee20a5dc222b98712ac204a629f08ed287687df46703ceeb0e1afe/cutnorm-0.1.1.tar.gz"
            }
        ],
        "0.1.4": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "a5a07ae8f5c6415fb1ac6c5719ecf7a8",
                    "sha256": "81eb056b74af59c5a00d0118bc02f151823f607fff0cb54b0951250ef92135f1"
                },
                "downloads": -1,
                "filename": "cutnorm-0.1.4.tar.gz",
                "has_sig": false,
                "md5_digest": "a5a07ae8f5c6415fb1ac6c5719ecf7a8",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7504,
                "upload_time": "2018-01-24T21:25:27",
                "url": "https://files.pythonhosted.org/packages/8e/36/6fbc18e3f14e8093fe4e05b38dea56e534f4360ad56dfb5f6f2061968fa1/cutnorm-0.1.4.tar.gz"
            }
        ],
        "0.1.5": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "626c126a6516206d8a66e499a2daccde",
                    "sha256": "3a1d618ffae51b3be59078f08a265ac7a3a89fa49e6e17f69f1fb1e36c713902"
                },
                "downloads": -1,
                "filename": "cutnorm-0.1.5.tar.gz",
                "has_sig": false,
                "md5_digest": "626c126a6516206d8a66e499a2daccde",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 10063,
                "upload_time": "2018-01-25T00:10:12",
                "url": "https://files.pythonhosted.org/packages/e9/4a/ccd6627dffd0aaba67c7b47f9cbe46161c3cf056288c5d6a0bf2161bac3e/cutnorm-0.1.5.tar.gz"
            }
        ],
        "0.1.6": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "44d629b2957b848e534aa3e4e6d08b68",
                    "sha256": "3e75c4f1449ed4cbdf7cc225d4f579eb771e9679d82a0cee9f1e84bbf64dcaf1"
                },
                "downloads": -1,
                "filename": "cutnorm-0.1.6.tar.gz",
                "has_sig": false,
                "md5_digest": "44d629b2957b848e534aa3e4e6d08b68",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 10299,
                "upload_time": "2018-03-09T00:57:01",
                "url": "https://files.pythonhosted.org/packages/a5/5b/b2eb092fe0d835498cdd8e806c454e08277e895f4529f6aa90eac0562ca7/cutnorm-0.1.6.tar.gz"
            }
        ],
        "0.1.7": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "208bf0c74e1a6b5da6cb251743b962f6",
                    "sha256": "3a5fe321479aedc9b979ac86d7ebf772edb1e477b23640314c04db77fc8690b5"
                },
                "downloads": -1,
                "filename": "cutnorm-0.1.7.tar.gz",
                "has_sig": false,
                "md5_digest": "208bf0c74e1a6b5da6cb251743b962f6",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 13288,
                "upload_time": "2018-04-09T15:31:49",
                "url": "https://files.pythonhosted.org/packages/16/32/c6715fdb4f027502bdce4383aaa75ee311e725f97dbdacca4856c28361e4/cutnorm-0.1.7.tar.gz"
            }
        ],
        "0.1.8": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "88adcb2bd31bbfd3d7ea8571da7b5df2",
                    "sha256": "4ebc702732cb8d5004e848916bf9b9e1fe6b29dc197631f7816197fa2220a262"
                },
                "downloads": -1,
                "filename": "cutnorm-0.1.8.tar.gz",
                "has_sig": false,
                "md5_digest": "88adcb2bd31bbfd3d7ea8571da7b5df2",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 13189,
                "upload_time": "2018-04-09T15:45:01",
                "url": "https://files.pythonhosted.org/packages/93/e7/5cf68d2a63c3e9e1f4c5f6ffcc09701a6807ab03f0d48b9cac17e499caf3/cutnorm-0.1.8.tar.gz"
            }
        ],
        "0.1.9": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "dc7557dd67ccfe224accef854804618c",
                    "sha256": "227b7940fa8d7df64e5fc5629467c9511c7f1f3b5fd75bc32890fbd4e373e7c9"
                },
                "downloads": -1,
                "filename": "cutnorm-0.1.9.tar.gz",
                "has_sig": false,
                "md5_digest": "dc7557dd67ccfe224accef854804618c",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 13909,
                "upload_time": "2018-05-07T17:53:34",
                "url": "https://files.pythonhosted.org/packages/c1/d5/072190d7c916b8acf651e2127abd970541b8c58faf66198e76d259eec3e6/cutnorm-0.1.9.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "dc7557dd67ccfe224accef854804618c",
                "sha256": "227b7940fa8d7df64e5fc5629467c9511c7f1f3b5fd75bc32890fbd4e373e7c9"
            },
            "downloads": -1,
            "filename": "cutnorm-0.1.9.tar.gz",
            "has_sig": false,
            "md5_digest": "dc7557dd67ccfe224accef854804618c",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 13909,
            "upload_time": "2018-05-07T17:53:34",
            "url": "https://files.pythonhosted.org/packages/c1/d5/072190d7c916b8acf651e2127abd970541b8c58faf66198e76d259eec3e6/cutnorm-0.1.9.tar.gz"
        }
    ]
}