dyvider
=======
**dyvider** is a small library implementing dynamic programming
algorithms for exact linear clustering in networks. Its algorithms
process networks whose nodes have positions in one dimension, and return
their optimal partition.
The theory and experiments exploring this code can be found in the paper
`"Exact and rapid linear clustering of networks with dynamic programming" <https://arxiv.org/abs/2301.10403>`__,
by `Alice Patania <https://alpatania.github.io/>`__, `Antoine Allard <https://antoineallard.github.io/>`__
and `Jean-Gabriel Young <https://jg-you.github.io/>`__.
Dependencies
------------
The only necessary dependency are
`networkx <https://networkx.org/>`__ and ``numpy``.
Quick tour
----------
The following minimal example first assigns scores to nodes with a
one-dimensional spectral embedding and then retrieves an optimal linear
clustering from this embedding using ``dyvider``.
.. code:: python
import networkx as nx
import dyvider as dy
import numpy as np
# create a graph
g = nx.stochastic_block_model([10, 10], [[0.5, 0.05], [0.05, 0.5]], seed=42)
# generate a 1-d embedding with the leading eigenvector of the modularity matrix
eigenvals, eigvenvecs = np.linalg.eig(nx.linalg.adjacency_matrix(g).todense())
score = {v: float(eigvenvecs[v, 0]) for v in g.nodes()}
# set the node positions
nx.set_node_attributes(g, score, 'score')
# run dyvider
g = dy.utilities.preprocess(g)
objective_function = dy.objectives.Modularity()
solution, Q = dy.algorithms.run(g, objective_function)
print(solution)
The expected output is:
.. code:: python
>>> [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]]
Our `tutorial <tutorial.ipynb>`__ goes into more detail and demonstrates
all the API calls.
Paper
-----
If you use this code, please consider citing:
“`Exact and rapid linear clustering of networks with dynamic programming <https://arxiv.org/abs/2301.10403>`__”
`Alice Patania <https://alpatania.github.io/>`__,
`Antoine Allard <https://antoineallard.github.io/>`__ and
`Jean-Gabriel Young <https://jg-you.github.io/>`__. arXiv:2301.10403.
Author information
------------------
Code by `Jean-Gabriel Young <https://jg-you.github.io>`__. Don’t
hesitate to get in touch at jean-gabriel.young@uvm.edu, or via the
`issues <https://github.com/jg-you/dyvider/issues>`__!
Raw data
{
"_id": null,
"home_page": "https://github.com/jg-you/dyvider",
"name": "dyvider",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "graphs,community detection,networks,inference",
"author": "Jean-Gabriel Young, Alice Patania",
"author_email": "jean-gabriel.young@uvm.edu",
"download_url": "https://files.pythonhosted.org/packages/f9/9c/973a0d2e32c9783c2dd96e952ee1b2508c774bc224f14d4068033ce03eaf/dyvider-0.3.tar.gz",
"platform": null,
"description": "dyvider\n=======\n\n**dyvider** is a small library implementing dynamic programming\nalgorithms for exact linear clustering in networks. Its algorithms\nprocess networks whose nodes have positions in one dimension, and return\ntheir optimal partition.\n\nThe theory and experiments exploring this code can be found in the paper\n`\"Exact and rapid linear clustering of networks with dynamic programming\" <https://arxiv.org/abs/2301.10403>`__, \nby `Alice Patania <https://alpatania.github.io/>`__, `Antoine Allard <https://antoineallard.github.io/>`__ \nand `Jean-Gabriel Young <https://jg-you.github.io/>`__.\n\n\nDependencies\n------------\n\nThe only necessary dependency are\n`networkx <https://networkx.org/>`__ and ``numpy``.\n\nQuick tour\n----------\n\nThe following minimal example first assigns scores to nodes with a\none-dimensional spectral embedding and then retrieves an optimal linear\nclustering from this embedding using ``dyvider``.\n\n.. code:: python\n\n import networkx as nx\n import dyvider as dy\n import numpy as np\n\n # create a graph\n g = nx.stochastic_block_model([10, 10], [[0.5, 0.05], [0.05, 0.5]], seed=42)\n\n # generate a 1-d embedding with the leading eigenvector of the modularity matrix\n eigenvals, eigvenvecs = np.linalg.eig(nx.linalg.adjacency_matrix(g).todense())\n score = {v: float(eigvenvecs[v, 0]) for v in g.nodes()}\n\n # set the node positions\n nx.set_node_attributes(g, score, 'score')\n\n # run dyvider\n g = dy.utilities.preprocess(g)\n objective_function = dy.objectives.Modularity()\n solution, Q = dy.algorithms.run(g, objective_function)\n\n print(solution)\n\nThe expected output is:\n\n.. code:: python\n\n >>> [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]] \n\nOur `tutorial <tutorial.ipynb>`__ goes into more detail and demonstrates\nall the API calls.\n\nPaper\n-----\n\nIf you use this code, please consider citing:\n\n\u201c`Exact and rapid linear clustering of networks with dynamic programming <https://arxiv.org/abs/2301.10403>`__\u201d \n`Alice Patania <https://alpatania.github.io/>`__,\n`Antoine Allard <https://antoineallard.github.io/>`__ and \n`Jean-Gabriel Young <https://jg-you.github.io/>`__. arXiv:2301.10403.\n\nAuthor information\n------------------\n\nCode by `Jean-Gabriel Young <https://jg-you.github.io>`__. Don\u2019t\nhesitate to get in touch at jean-gabriel.young@uvm.edu, or via the\n`issues <https://github.com/jg-you/dyvider/issues>`__!\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Rapid and exact partitioning algorithms for graphs embedded in one dimension.",
"version": "0.3",
"split_keywords": [
"graphs",
"community detection",
"networks",
"inference"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "f99c973a0d2e32c9783c2dd96e952ee1b2508c774bc224f14d4068033ce03eaf",
"md5": "88c07312695d3b34c0a01d5cf4730ea0",
"sha256": "9b11df48ebb6bac594a5b22eca744c04ddf3f7f8237518f69ba8cb086bcc4236"
},
"downloads": -1,
"filename": "dyvider-0.3.tar.gz",
"has_sig": false,
"md5_digest": "88c07312695d3b34c0a01d5cf4730ea0",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 13037,
"upload_time": "2023-01-26T04:54:14",
"upload_time_iso_8601": "2023-01-26T04:54:14.715953Z",
"url": "https://files.pythonhosted.org/packages/f9/9c/973a0d2e32c9783c2dd96e952ee1b2508c774bc224f14d4068033ce03eaf/dyvider-0.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-26 04:54:14",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "jg-you",
"github_project": "dyvider",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "dyvider"
}
JSON
