# -*- coding: utf-8 -*-
# SPDX-FileCopyrightText: 2015-2023 Tanguy Fardet
# SPDX-License-Identifier: GPL-3.0-or-later
# nngt/generation/graph_connectivity.py
""" Connectivity generators for nngt.Graph """
from copy import deepcopy
import logging
import numpy as np
import nngt
from nngt.geometry.geom_utils import conversion_magnitude
from nngt.lib.connect_tools import (_set_options, _connect_ccs,
_independent_edges)
from nngt.lib.logger import _log_message
from nngt.lib.test_functions import (mpi_checker, mpi_random, deprecated,
on_master_process)
__all__ = [
'all_to_all',
'circular',
'distance_rule',
'erdos_renyi',
'fixed_degree',
'from_degree_list',
'gaussian_degree',
'newman_watts',
'price_scale_free',
'random_scale_free',
'sparse_clustered',
'watts_strogatz',
]
# do default import
from .connect_algorithms import *
# try to import multithreaded or mpi algorithms
using_mt_algorithms = False
if nngt.get_config("multithreading"):
logger = logging.getLogger(__name__)
try:
from .cconnect import *
using_mt_algorithms = True
_log_message(logger, "DEBUG",
"Using multithreaded algorithms compiled on install.")
nngt.set_config('multithreading', True, silent=True)
except Exception as e:
try:
import cython
import pyximport
try:
from mpi4py import MPI
comm = MPI.COMM_WORLD
comm.bcast(pyximport.install(language_level=3))
except:
if nngt.get_config("mpi"):
raise RuntimeError("Cannot safely compile with MPI.")
pyximport.install(language_level=3)
# wait for compilation to finish
nngt.lib.mpi_barrier()
if on_master_process():
from .cconnect import *
nngt.lib.mpi_barrier()
from .cconnect import *
using_mt_algorithms = True
_log_message(logger, "DEBUG", str(e) + "\n\tCompiled "
"multithreaded algorithms on-the-run.")
nngt.set_config('multithreading', True, silent=True)
except Exception as e2:
_log_message(
logger, "WARNING", str(e) + "\n\t" + str(e2) + "\n\t"
"Cython import failed, using non-multithreaded algorithms.")
nngt._config['multithreading'] = False
if nngt.get_config("mpi"):
try:
from .mpi_connect import *
nngt._config['mpi'] = True
except ImportError as e:
nngt._config['mpi'] = False
raise e
# ----------------------------- #
# Specific degree distributions #
# ----------------------------- #
[docs]
def all_to_all(nodes=0, weighted=True, directed=True, multigraph=False,
name="AllToAll", shape=None, positions=None, population=None,
**kwargs):
"""
Generate a graph where all nodes are connected.
.. versionadded:: 1.0
Parameters
----------
nodes : int, optional (default: None)
The number of nodes in the graph.
reciprocity : double, optional (default: -1 to let it free)
Fraction of edges that are bidirectional (only for directed graphs
-- undirected graphs have a reciprocity of 1 by definition)
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
Note
----
`nodes` is required unless `population` is provided.
Returns
-------
graph_all : :class:`~nngt.Graph`, or subclass
A new generated graph.
"""
nodes = nodes if population is None else population.size
graph_all = nngt.Graph(name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_all, population, shape, positions)
# add edges
if nodes > 1:
ids = np.arange(nodes, dtype=np.uint)
edges = _all_to_all(ids, ids, directed=directed, multigraph=multigraph)
graph_all.new_edges(edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_all._graph_type = "all_to_all"
return graph_all
[docs]
@mpi_random
def from_degree_list(degrees, degree_type='in', weighted=True,
directed=True, multigraph=False, name="DL",
shape=None, positions=None, population=None,
from_graph=None, **kwargs):
"""
Generate a random graph from a given list of degrees.
Parameters
----------
degrees : list
The list of degrees for each node in the graph.
degree_type : str, optional (default: 'in')
The type of the fixed degree, among ``'in'``, ``'out'`` or ``'total'``.
nodes : int, optional (default: None)
The number of nodes in the graph.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Returns
-------
graph_dl : :class:`~nngt.Graph`, or subclass
A new generated graph or the modified `from_graph`.
"""
# set node number and library graph
graph_dl = from_graph
nodes = len(degrees)
if "nodes" in kwargs:
assert kwargs["nodes"] == nodes, \
"Invalid `nodes` entry: the number of nodes should " \
"be ``len(degrees)``."
del kwargs["nodes"]
if graph_dl is not None:
nodes = graph_dl.node_nb()
graph_dl.clear_all_edges()
else:
nodes = population.size if population is not None else nodes
graph_dl = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_dl, population, shape, positions)
# add edges
ia_edges = None
if nodes > 1:
ids = np.arange(nodes, dtype=np.uint)
ia_edges = _from_degree_list(ids, ids, degrees, degree_type,
directed=directed, multigraph=multigraph)
# check for None if MPI
if ia_edges is not None:
graph_dl.new_edges(ia_edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_dl._graph_type = "from_{}_degree_list".format(degree_type)
return graph_dl
[docs]
@mpi_random
def fixed_degree(degree, degree_type='in', nodes=0, reciprocity=-1.,
weighted=True, directed=True, multigraph=False, name="FD",
shape=None, positions=None, population=None, from_graph=None,
**kwargs):
"""
Generate a random graph with constant in- or out-degree.
Parameters
----------
degree : int
The value of the constant degree.
degree_type : str, optional (default: 'in')
The type of the fixed degree, among ``'in'``, ``'out'`` or ``'total'``.
nodes : int, optional (default: None)
The number of nodes in the graph.
reciprocity : double, optional (default: -1 to let it free)
@todo: not implemented yet. Fraction of edges that are bidirectional
(only for directed graphs -- undirected graphs have a reciprocity of
1 by definition)
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
@todo: only for directed graphs for now. Whether the graph is directed
or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Note
----
`nodes` is required unless `from_graph` or `population` is provided.
If an `from_graph` is provided, all preexistant edges in the
object will be deleted before the new connectivity is implemented.
Returns
-------
graph_fd : :class:`~nngt.Graph`, or subclass
A new generated graph or the modified `from_graph`.
"""
# set node number and library graph
graph_fd = from_graph
if graph_fd is not None:
nodes = graph_fd.node_nb()
graph_fd.clear_all_edges()
else:
nodes = population.size if population is not None else nodes
graph_fd = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_fd, population, shape, positions)
# add edges
ia_edges = None
if nodes > 1:
ids = np.arange(nodes, dtype=np.uint)
ia_edges = _fixed_degree(
ids, ids, degree, degree_type, reciprocity=reciprocity,
directed=directed, multigraph=multigraph)
# check for None if MPI
if ia_edges is not None:
graph_fd.new_edges(ia_edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_fd._graph_type = "fixed_{}_degree".format(degree_type)
return graph_fd
[docs]
@mpi_random
def gaussian_degree(avg, std, degree_type='in', nodes=0, reciprocity=-1.,
weighted=True, directed=True, multigraph=False, name="GD",
shape=None, positions=None, population=None,
from_graph=None, **kwargs):
"""
Generate a random graph with constant in- or out-degree.
Parameters
----------
avg : float
The value of the average degree.
std : float
The standard deviation of the Gaussian distribution.
degree_type : str, optional (default: 'in')
The type of the fixed degree, among 'in', 'out' or 'total' (or the
full version: 'in-degree'...)
@todo: Implement 'total' degree
nodes : int, optional (default: None)
The number of nodes in the graph.
reciprocity : double, optional (default: -1 to let it free)
@todo: not implemented yet. Fraction of edges that are bidirectional
(only for directed graphs -- undirected graphs have a reciprocity of
1 by definition)
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
@todo: only for directed graphs for now. Whether the graph is directed
or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Returns
-------
graph_gd : :class:`~nngt.Graph`, or subclass
A new generated graph or the modified `from_graph`.
Note
----
`nodes` is required unless `from_graph` or `population` is provided.
If an `from_graph` is provided, all preexistant edges in the object
will be deleted before the new connectivity is implemented.
"""
# set node number and library graph
graph_gd = from_graph
if graph_gd is not None:
nodes = graph_gd.node_nb()
graph_gd.clear_all_edges()
else:
nodes = population.size if population is not None else nodes
graph_gd = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_gd, population, shape, positions)
# add edges
ia_edges = None
if nodes > 1:
ids = np.arange(nodes, dtype=np.uint)
ia_edges = _gaussian_degree(
ids, ids, avg, std, degree_type, reciprocity=reciprocity,
directed=directed, multigraph=multigraph)
# check for None if MPI
if ia_edges is not None:
graph_gd.new_edges(ia_edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_gd._graph_type = "gaussian_{}_degree".format(degree_type)
return graph_gd
# ----------- #
# Erdos-Renyi #
# ----------- #
[docs]
def erdos_renyi(density=None, nodes=0, edges=None, avg_deg=None,
reciprocity=-1., weighted=True, directed=True,
multigraph=False, name="ER", shape=None, positions=None,
population=None, from_graph=None, **kwargs):
"""
Generate a random graph as defined by Erdos and Renyi but with a
reciprocity that can be chosen.
Parameters
----------
density : double, optional (default: -1.)
Structural density given by `edges / nodes`:math:`^2`. It is also the
probability for each possible edge in the graph to exist.
nodes : int, optional (default: None)
The number of nodes in the graph.
edges : int (optional)
The number of edges between the nodes
avg_deg : double, optional
Average degree of the neurons given by `edges / nodes`.
reciprocity : double, optional (default: -1 to let it free)
Fraction of edges that are bidirectional (only for
directed graphs -- undirected graphs have a reciprocity of 1 by
definition)
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Returns
-------
graph_er : :class:`~nngt.Graph`, or subclass
A new generated graph or the modified `from_graph`.
Note
----
`nodes` is required unless `from_graph` or `population` is provided.
If an `from_graph` is provided, all preexistant edges in the
object will be deleted before the new connectivity is implemented.
"""
# set node number and library graph
graph_er = from_graph
if graph_er is not None:
nodes = graph_er.node_nb()
graph_er.clear_all_edges()
else:
nodes = population.size if population is not None else nodes
graph_er = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_er, population, shape, positions)
# add edges
ia_edges = None
if nodes > 1:
ids = range(nodes)
ia_edges = _erdos_renyi(ids, ids, density, edges, avg_deg, reciprocity,
directed, multigraph)
graph_er.new_edges(ia_edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_er._graph_type = "erdos_renyi"
return graph_er
# ----------------- #
# Scale-free models #
# ----------------- #
[docs]
def random_scale_free(in_exp, out_exp, nodes=0, density=None, edges=None,
avg_deg=None, reciprocity=0., weighted=True,
directed=True, multigraph=False, name="RandomSF",
shape=None, positions=None, population=None,
from_graph=None, **kwargs):
r"""
Generate a free-scale graph of given reciprocity and otherwise
devoid of correlations.
Parameters
----------
in_exp : float
Absolute value of the in-degree exponent :math:`\gamma_i`, such that
:math:`p(k_i) \propto k_i^{-\gamma_i}`
out_exp : float
Absolute value of the out-degree exponent :math:`\gamma_o`, such that
:math:`p(k_o) \propto k_o^{-\gamma_o}`
nodes : int, optional (default: 0)
The number of nodes in the graph.
density: double, optional
Structural density given by `edges / (nodes*nodes)`.
edges : int optional
The number of edges between the nodes
avg_deg : double, optional
Average degree of the neurons given by `edges / nodes`.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes. can contain multiple edges between two
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`)
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Returns
-------
graph_fs : :class:`~nngt.Graph`
Note
----
As reciprocity increases, requested values of `in_exp` and `out_exp`
will be less and less respected as the distribution will converge to a
common exponent :math:`\gamma = (\gamma_i + \gamma_o) / 2`.
Parameter `nodes` is required unless `from_graph` or `population` is
provided.
"""
# set node number and library graph
graph_rsf = from_graph
if graph_rsf is not None:
nodes = graph_rsf.node_nb()
graph_rsf.clear_all_edges()
else:
nodes = population.size if population is not None else nodes
graph_rsf = nngt.Graph(
name=name,nodes=nodes,directed=directed,**kwargs)
_set_options(graph_rsf, population, shape, positions)
# add edges
if nodes > 1:
ids = range(nodes)
ia_edges = _random_scale_free(ids, ids, in_exp, out_exp, density,
edges, avg_deg, reciprocity, directed, multigraph)
graph_rsf.new_edges(ia_edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_rsf._graph_type = "random_scale_free"
return graph_rsf
[docs]
def price_scale_free(m, c=None, gamma=1, nodes=0, reciprocity=0, weighted=True,
directed=True, multigraph=False, name="PriceSF",
shape=None, positions=None, population=None, **kwargs):
r'''
Generate a Price graph model (Barabasi-Albert if undirected).
Parameters
----------
m : int
The number of edges each new node will make.
c : double, optional (0 if undirected, else 1)
Constant added to the probability of a vertex receiving an edge.
gamma : double, optional (default: 1)
Preferential attachment power.
nodes : int, optional (default: None)
The number of nodes in the graph.
reciprocity : float, optional (default: 0)
Reciprocity of the graph (between 0 and 1). For directed graphs, this
will be the probability of the target node connecting back to the
source node when a new edge is added.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
Returns
-------
graph_price : :class:`~nngt.Graph` or subclass.
Note
----
`nodes` is required unless `population` is provided.
Notes
-----
The (generalized) Price network is either a directed or undirected graph
(the latter is better known as the Barabási-Albert network).
It is generated via a growth process, adding a new node at each step and
connecting it to :math:`m` previous nodes, chosen with probability:
.. math::
p \propto k^\gamma + c
where :math:`k` is the (in-)degree of the vertex.
We must therefore have :math:`c \ge 0` for directed graphs and
:math:`c > -1` for undirected graphs.
If the `reciprocity` :math:`r` is non-zero, each targeted node reciprocates
the connection with probability :math:`r`.
Expected reciprocity of the final graph is :math:`2r / (1 + r)`.
If :math:`\gamma=1`, and `reciprocity` is zero, the tail of resulting
in-degree distribution of the directed case is given by
.. math::
P_{k_{in}} \sim k_{in}^{-(2 + c/m)},
or for the undirected case
.. math::
P_{k} \sim k^{-(3 + c/m)}.
However, if :math:`\gamma \ne 1`, the in-degree distribution is not
scale-free.
'''
c = c if c is not None else 1 if directed else 0
# set node number and library graph
nodes = population.size if population is not None else nodes
graph_psf = nngt.Graph(
name=name, nodes=nodes, directed=directed, weighted=weighted,
**kwargs)
_set_options(graph_psf, population, shape, positions)
# add edges
if nodes > 1:
ids = range(nodes)
edges = _price_scale_free(ids, m, c, gamma, reciprocity, directed,
multigraph)
graph_psf.new_edges(edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_psf._graph_type = "price_scale_free"
return graph_psf
# -------------- #
# Circular graph #
# -------------- #
[docs]
def circular(coord_nb, reciprocity=1., reciprocity_choice="random", nodes=0,
weighted=True, directed=True, multigraph=False, name="Circular",
shape=None, positions=None, population=None, from_graph=None,
**kwargs):
'''
Generate a circular graph.
The nodes are placed on a circle and connected to their `coord_nb` closest
neighbours.
If the graph is directed, the number of connections depends on the value
of `reciprocity`: if ``reciprocity == 0.``, then only half of all possible
connections will be created, so that no bidirectional edges exist; on the
other hand, for ``reciprocity == 1.``, all possible edges are created; for
intermediate values of `reciprocity`, the number of edges increases
linearly as ``0.5*(1 + reciprocity / (2 - reciprocity))*nodes*coord_nb``.
Parameters
----------
coord_nb : int
The number of neighbours for each node on the initial topological
lattice (must be even).
reciprocity : double, optional (default: 1.)
Proportion of reciprocal edges in the graph.
reciprocity_choice : str, optional (default: "random")
How reciprocal edges should be chosen, which can be either "random" or
"closest". If the latter option is used, then connections
between first neighbours are rendered reciprocal first, then between
second neighbours, etc.
nodes : int, optional (default: None)
The number of nodes in the graph.
density: double, optional (default: 0.1)
Structural density given by `edges` / (`nodes`*`nodes`).
edges : int (optional)
The number of edges between the nodes
avg_deg : double, optional
Average degree of the neurons given by `edges` / `nodes`.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Returns
-------
graph_circ : :class:`~nngt.Graph` or subclass
'''
if multigraph:
raise ValueError("`multigraph` is not supported for circular graphs.")
# set node number and library graph
graph_circ = from_graph
if graph_circ is not None:
nodes = graph_circ.node_nb()
else:
nodes = population.size if population is not None else nodes
graph_circ = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_circ, population, shape, positions)
# add edges
if nodes > 1:
ids = range(nodes)
edges = _circular(ids, ids, coord_nb, reciprocity, directed,
reciprocity_choice=reciprocity_choice)
graph_circ.new_edges(edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_circ._graph_type = "circular"
return graph_circ
# ------------------ #
# Small-world models #
# ------------------ #
[docs]
def newman_watts(coord_nb, proba_shortcut=None, reciprocity_circular=1.,
reciprocity_choice_circular="random", nodes=0, edges=None,
weighted=True, directed=True, multigraph=False, name="NW",
shape=None, positions=None, population=None, from_graph=None,
**kwargs):
"""
Generate a (potentially small-world) graph using the Newman-Watts
algorithm.
For directed networks, the reciprocity of the initial circular network can
be chosen.
.. versionchanged:: 2.0
Added the `reciprocity_circular` and `reciprocity_choice_circular`
options.
Parameters
----------
coord_nb : int
The number of neighbours for each node on the initial topological
lattice (must be even).
proba_shortcut : double, optional
Probability of adding a new random (shortcut) edge for each existing
edge on the initial lattice.
If `edges` is provided, then will be computed automatically as
``edges / (coord_nb * nodes * (1 + reciprocity_circular) / 2)``
reciprocity_circular : double, optional (default: 1.)
Proportion of reciprocal edges in the initial circular graph.
reciprocity_choice_circular : str, optional (default: "random")
How reciprocal edges should be chosen in the initial circular graph.
This can be either "random" or "closest". If the latter option
is used, then connections between first neighbours are rendered
reciprocal first, then between second neighbours, etc.
nodes : int, optional (default: None)
The number of nodes in the graph.
edges : int (optional)
The number of edges between the nodes.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Returns
-------
graph_nw : :class:`~nngt.Graph` or subclass
Note
----
`nodes` is required unless `from_graph` or `population` is provided.
"""
if multigraph:
raise ValueError("`multigraph` is not supported for Watts-Strogatz.")
# set node number and library graph
graph_nw = from_graph
if graph_nw is not None:
nodes = graph_nw.node_nb()
else:
nodes = population.size if population is not None else nodes
graph_nw = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_nw, population, shape, positions)
# add edges
if nodes > 1:
ids = range(nodes)
ia_edges = _newman_watts(
ids, ids, coord_nb, proba_shortcut, reciprocity_circular,
reciprocity_choice_circular=reciprocity_choice_circular,
edges=edges, directed=directed)
graph_nw.new_edges(ia_edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_nw._graph_type = "watts_strogatz"
return graph_nw
[docs]
def watts_strogatz(coord_nb, proba_shortcut=None, reciprocity_circular=1.,
reciprocity_choice_circular="random", shuffle="random",
nodes=0, weighted=True, directed=True, multigraph=False,
name="WS", shape=None, positions=None, population=None,
from_graph=None, **kwargs):
"""
Generate a (potentially small-world) graph using the Watts-Strogatz
algorithm.
For directed networks, the reciprocity of the initial circular network can
be chosen.
.. versionadded:: 2.0
Parameters
----------
coord_nb : int
The number of neighbours for each node on the initial topological
lattice (must be even).
proba_shortcut : double, optional
Probability of adding a new random (shortcut) edge for each existing
edge on the initial lattice.
If `edges` is provided, then will be computed automatically as
``edges / (coord_nb * nodes * (1 + reciprocity_circular) / 2)``
reciprocity_circular : double, optional (default: 1.)
Proportion of reciprocal edges in the initial circular graph.
reciprocity_choice_circular : str, optional (default: "random")
How reciprocal edges should be chosen in the initial circular graph.
This can be either "random" or "closest". If the latter option
is used, then connections between first neighbours are rendered
reciprocal first, then between second neighbours, etc.
shuffle : str, optional (default: 'random')
Whether to shuffle only 'targets' (out-degree of all nodes remains
constant), 'sources' (in-degree remains constant), or randomly the
source or the target for each edge ('random') in the case of directed
graphs.
nodes : int, optional (default: None)
The number of nodes in the graph.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
Returns
-------
graph_nw : :class:`~nngt.Graph` or subclass
Note
----
`nodes` is required unless `from_graph` or `population` is provided.
"""
if multigraph:
raise ValueError("`multigraph` is not supported for Newman-Watts.")
# set node number and library graph
graph_nw = from_graph
if graph_nw is not None:
nodes = graph_nw.node_nb()
else:
nodes = population.size if population is not None else nodes
graph_nw = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_nw, population, shape, positions)
# add edges
if nodes > 1:
ids = range(nodes)
ia_edges = _watts_strogatz(
ids, ids, coord_nb, proba_shortcut, reciprocity_circular,
reciprocity_choice_circular, shuffle, directed=directed)
graph_nw.new_edges(ia_edges, check_duplicates=False,
check_self_loops=False, check_existing=False)
graph_nw._graph_type = "newman_watts"
return graph_nw
[docs]
def sparse_clustered(c, nodes=0, edges=None, avg_deg=None, connected=True,
rtol=None, exact_edge_nb=False, weighted=True,
directed=True, multigraph=False, name="FC", shape=None,
positions=None, population=None, from_graph=None,
**kwargs):
r'''
Generate a sparse random graph with given average clustering coefficient
and degree.
.. versionadded:: 2.5
The original algorithm is adapted from [newman-clustered-2003]_ and leads
to a graph with approximate clustering coefficient and number of edges.
.. warning::
This algorithm can only give reasonable results for sparse graphs and
will raise an error if the requested graph density is above `c`.
Nodes are distributed among :math:`\mu` overlapping groups of size
:math:`\nu` and, each time two nodes belong to a common group, they are
connected with a probability :math:`p = c`.
For sparse graphs, the average (in/out-)degree can be approximmated as
:math:`k = \mu p(\nu - 1)`, and the average clustering as:
.. math::
C^{(u)} = \frac{p \left[ p(\nu - 1) - 1 \right]}{k - 1}
for undirected graphs and
.. math::
C^{(d)} = \frac{p\mu \left[ p(2\nu - 3) - 1 \right]}{2k - 1 - p}
for all clustering modes in directed graphs.
From these relations, we compute :math:`\mu` and :math:`\nu` as:
.. math::
\nu^{(u)} = 1 + \frac{1}{p} + \frac{C^{(u)} (k - 1)}{p^2}
or
.. math::
\nu^{(d)} = \frac{3}{2} + \frac{1}{2p} +
\frac{C^{(u)} (2k - 1 - p)}{2p^2}
and
.. math::
\mu = \frac{k}{p (\nu - 1)}.
Parameters
----------
c : float
Desired value for the final average clustering in the graph.
nodes : int, optional (default: None)
The number of nodes in the graph.
edges : int, optional
The number of edges between the nodes
avg_deg : double, optional
Average degree of the neurons given by `edges / nodes`.
connected : bool, optional (default: True)
Whether the resulting graph must be connected (True) or may be
unconnected (False).
rtol : float, optional (default: not checked)
Tolerance on the relative error between the target clustering `c` and
the actual clustering of the final graph.
If the algorithm leads to a relative error greater than `rtol`, then
an error is raised.
exact_edge_nb : bool, optional (default: False)
Whether the final graph should have precisely the number of edges
required.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph should be directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two nodes.
name : string, optional (default: "ER")
Name of the created graph.
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D or 3D array containing the positions of the neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
**kwargs : keyword arguments
If connected is True, `method` can be passed to define how the
components should be connected among themselves. Available methods are
"sequential", where the components are connected sequentially, forming
a long thread and increasing the graph's diameter, "star-component",
where all components are connected to the largest one, and "random",
where components are connected randomly, or "central-node", where one
node from the largest component is chosen to reconnect all disconnected
components.
If not provided, defaults to "random".
Note
----
`nodes` is required unless `from_graph` or `population` is provided.
If `from_graph` is provided, all preexistent edges in the
object will be deleted before the new connectivity is implemented.
Returns
-------
graph_fc : :class:`~nngt.Graph`, or subclass
A new generated graph or the modified `from_graph`.
References
----------
.. [newman-clustered-2003] Newman, M. E. J. Properties of Highly
Clustered Networks, Phys. Rev. E 2003 68 (2).
:doi:`10.1103/PhysRevE.68.026121`, :arxiv:`cond-mat/0303183`.
'''
# get method
method = "star-component"
if "method" in kwargs:
method = kwargs.pop("method")
# set node number and library graph
graph_fc = from_graph
if graph_fc is not None:
nodes = graph_fc.node_nb()
graph_fc.clear_all_edges()
else:
nodes = population.size if population is not None else nodes
graph_fc = nngt.Graph(
name=name, nodes=nodes, directed=directed, **kwargs)
_set_options(graph_fc, population, shape, positions)
# compute average degree and set the number of nodes
if (avg_deg is None and edges is None) or None not in (avg_deg, edges):
raise ValueError("Either `avg_deg` or `edges` should be provided.")
# add edges
ia_edges = None
if nodes > 1:
k = edges / nodes if avg_deg is None else avg_deg
num_edges = int(k*nodes) if edges is None else edges
if k/nodes > c:
raise ValueError('Clustering cannot be lower than avg_deg/nodes, '
'or, equivalently, edges/nodes**2. Got '
'c = {} against {}.'.format(c, k/nodes))
def func_nu(p, directed):
if directed:
return np.around(
1.5 + 1/(2*p) + (2*k - 1 - p) * c / (2*p**2)).astype(int)
return np.around(1 + 1/p + (k - 1) * c / p**2).astype(int)
def func_mu(nu, p):
return k / (p * (nu - 1))
p = c
nu = func_nu(p, directed)
if nu >= nodes:
raise ValueError('Theoretical group size computed was '
'greater than the number of nodes.')
mu = func_mu(nu, p)
# assign the neurons to groups
n_to_g = {}
g_to_n = {}
rng = nngt._rng
gid = 0
# to minimize the number of groups, we start with distributed groups
for i in range(int(nodes / nu)):
g_to_n[gid] = list(range(nu*i, nu*(i+1)))
for j in range(nu*i, nu*(i+1)):
if j in n_to_g:
n_to_g[j].add(gid)
else:
n_to_g[j] = {gid}
gid += 1
if int(nodes / nu) * nu < nodes:
s = set(range(nu*gid, nodes))
# to minimize the number of disconnected components, we are going
# to fill the remaining nodes of s with previous nodes (one from
# each previous set until s is full) and assign a new random node
# to each of these previous sets
for g, ids in g_to_n.items():
# get a node from nodes
u = ids[0]
group = set(ids) - {u}
n_to_g[u] -= {g}
while len(group) < nu:
v = rng.choice(nodes, 1)[0]
group.add(v)
if len(group) == nu:
if v in n_to_g:
n_to_g[v] = n_to_g[v].union({g})
else:
n_to_g[v] = {g}
assert len(group) == nu
g_to_n[g] = list(group)
s.add(u)
if len(s) == nu:
break
g_to_n[gid] = list(s)
for j in s:
if j in n_to_g:
n_to_g[j].add(gid)
else:
n_to_g[j] = {gid}
gid += 1
# check that all nodes belong to a group
assert len(n_to_g) == nodes
if nu < nodes or mu > 1:
while gid < mu*nodes/nu:
ids = rng.choice(nodes, nu, replace=False)
g_to_n[gid] = ids
for i in ids:
if i in n_to_g:
n_to_g[i].add(gid)
else:
n_to_g[i] = {gid}
gid += 1
# generate the edges
edges = set()
for group, ids in g_to_n.items():
probas = rng.random(nu*(nu - 1))
count = 0
for i, u in enumerate(ids):
targets = list(ids[i + 1:])
if directed:
targets += list(ids[:i])
for v in targets:
prob = probas[count]
count += 1
if directed:
if prob < p and (u, v) not in edges:
edges.add((u, v))
elif prob < p:
if (u, v) not in edges and (v, u) not in edges:
edges.add((u, v))
graph_fc.new_edges(list(edges))
# final optional checks for connectedness and edge number
bridges = set()
cc, cmean = None, None
if connected:
# make the graph fully connected
cc = nngt.analysis.local_clustering(graph_fc)
cmean = cc.mean()
disconnected = True
while disconnected:
cids, hist = nngt.analysis.connected_components(graph_fc)
disconnected = len(hist) > 1
if not disconnected:
break
# connect nodes from separate connected components
if method == "star-component":
idx = np.argmax(hist)
idx_nodes = np.where(cids == idx)[0]
select_source = lambda x: rng.choice(len(x))
for i in (set(range(len(hist))) - {idx}):
u, _ = _connect_ccs(graph_fc, cids, idx, i, cc, c,
cmean, edges, bridges,
select_source=select_source)
if directed:
u_idx = np.where(idx_nodes == u)[0][0]
select_target = lambda x: u_idx
_connect_ccs(
graph_fc, cids, i, idx, cc, c, cmean, edges,
bridges, select_source=select_source,
select_target=select_target)
elif method == "random":
n = len(hist)
# almost surely connected random graph requires
# n*log(n) connections so we ask for half that to use as
# few edges as possible while limiting the number of loops
# since each iteration requires to compute the CCs
mult = max(1, int(0.5*np.ceil(np.log(n))))
sources = list(range(n))*mult
if directed and n > 2:
sources *= 2
targets = sources[::-1]
if n > 2:
rng.shuffle(targets)
cset = set()
for i in sources:
j = i
while i == j or (i, j) in cset:
j = rng.integers(0, len(hist))
_connect_ccs(graph_fc, cids, i, j, cc, c, cmean,
edges, bridges)
cset.add((i, j))
elif method == "sequential":
for i in range(1, len(hist)):
_connect_ccs(graph_fc, cids, i - 1, i, cc, c, cmean,
edges, bridges)
if directed:
_connect_ccs(graph_fc, cids, i, 0, cc, c, cmean, edges,
bridges)
elif method == "central-node":
idx = np.argmax(hist)
for i in (set(range(len(hist))) - {idx}):
_connect_ccs(graph_fc, cids, idx, i, cc, c, cmean,
edges, bridges)
if directed:
_connect_ccs(graph_fc, cids, i, idx, cc, c, cmean,
edges, bridges)
else:
raise ValueError("Invalid `method`: '" + method + "'.")
else:
cc = nngt.analysis.local_clustering(graph_fc)
cmean = cc.mean()
if exact_edge_nb:
proba = 1 - cc if cmean < c else cc
proba /= proba.sum()
while graph_fc.edge_nb() < num_edges:
# add edges
sources, targets = None, None
missing = num_edges - graph_fc.edge_nb()
if missing > 1:
sources = rng.choice(nodes, missing, p=proba)
targets = sources.copy()
rng.shuffle(targets)
else:
sources = [rng.choice(nodes)]
targets = [rng.choice(nodes)]
new_edges = []
for u, v in zip(sources, targets):
cond = (u, v) not in edges
if not directed:
cond *= (v, u) not in edges
if u != v and cond:
new_edges.append((u, v))
edges.add((u, v))
graph_fc.new_edges(new_edges)
check_ind_edges = True
count = 0
while graph_fc.edge_nb() > num_edges and count < 1000:
# remove edges
remove = graph_fc.edge_nb() - num_edges
sources, targets, chosen = [], [], None
# remove edges that do not belong to triangles if possible
if check_ind_edges:
ind_edges = \
_independent_edges(graph_fc).difference(bridges)
if ind_edges:
ind_edges = np.asarray(list(ind_edges))
if len(ind_edges) > remove:
chosen = rng.choice(len(ind_edges), remove,
replace=False)
else:
chosen = slice(None)
sources = list(ind_edges[chosen, 0])
targets = list(ind_edges[chosen, 1])
else:
check_ind_edges = False
if len(sources) < remove:
remaining = remove - len(sources)
proba = np.square(
graph_fc.get_degrees("out")).astype(float)
proba /= proba.sum()
sources.extend(rng.choice(nodes, remaining, p=proba))
proba = np.square(graph_fc.get_degrees("in")).astype(float)
proba /= proba.sum()
targets.extend(rng.choice(nodes, remaining, p=proba))
delete = []
for u, v in zip(sources, targets):
if (u, v) in edges and (u, v) not in bridges:
delete.append((u, v))
edges.discard((u, v))
elif not directed:
if (v, u) in edges and (v, u) not in bridges:
delete.append((v, u))
edges.discard((v, u))
graph_fc.delete_edges(delete)
count += 1
if count == 1000:
raise RuntimeError("Algorithm did not converge, try with "
"exact_edge_nb=False to avoid that issue.")
if rtol is not None:
cmean = nngt.analysis.local_clustering(graph_fc).mean()
err = np.abs(c - cmean) / c
if err > rtol:
raise RuntimeError("Relative error greater than `rtol`: "
"{} > {}".format(err, rtol))
graph_fc._graph_type = "fixed_clustering"
return graph_fc
# --------------------- #
# Distance-based models #
# --------------------- #
[docs]
@mpi_random
def distance_rule(scale, rule="exp", shape=None, neuron_density=1000.,
max_proba=-1., nodes=0, density=None, edges=None,
avg_deg=None, unit='um', weighted=True, directed=True,
multigraph=False, name="DR", positions=None, population=None,
from_graph=None, **kwargs):
r"""
Create a graph using a 2D distance rule to create the connection between
neurons. Available rules are linear and exponential.
Parameters
----------
scale : float
Characteristic scale for the distance rule. E.g for linear distance-
rule, :math:`P(i,j) \propto (1-d_{ij}/scale))`, whereas for the
exponential distance-rule, :math:`P(i,j) \propto e^{-d_{ij}/scale}`.
rule : string, optional (default: 'exp')
Rule that will be apply to draw the connections between neurons.
Choose among "exp" (exponential), "gaussian" (Gaussian), or
"lin" (linear).
shape : :class:`~nngt.geometry.Shape`, optional (default: None)
Shape of the neurons' environment. If not specified, a square will be
created with the appropriate dimensions for the number of neurons and
the neuron spatial density.
neuron_density : float, optional (default: 1000.)
Density of neurons in space (:math:`neurons \cdot mm^{-2}`).
nodes : int, optional (default: None)
The number of nodes in the graph.
p : float, optional
Normalization factor for the distance rule; it is equal to the
probability of connection when testing a node at zero distance.
density: double, optional
Structural density given by `edges` / (`nodes` * `nodes`).
edges : int, optional
The number of edges between the nodes
avg_deg : double, optional
Average degree of the neurons given by `edges` / `nodes`.
unit : string (default: 'um')
Unit for the length `scale` among 'um' (:math:`\mu m`), 'mm', 'cm',
'dm', 'm'.
weighted : bool, optional (default: True)
Whether the graph edges have weights.
directed : bool, optional (default: True)
Whether the graph is directed or not.
multigraph : bool, optional (default: False)
Whether the graph can contain multiple edges between two
nodes.
name : string, optional (default: "DR")
Name of the created graph.
positions : :class:`numpy.ndarray`, optional (default: None)
A 2D (N, 2) or 3D (N, 3) shaped array containing the positions of the
neurons in space.
population : :class:`~nngt.NeuralPop`, optional (default: None)
Population of neurons defining their biological properties (to create a
:class:`~nngt.Network`).
from_graph : :class:`Graph` or subclass, optional (default: None)
Initial graph whose nodes are to be connected.
"""
distance = []
# convert neuronal density in (mu m)^2
neuron_density *= conversion_magnitude(unit, 'mm')**2
# set node number and library graph
graph_dr = from_graph
if graph_dr is not None:
nodes = graph_dr.node_nb()
graph_dr.clear_all_edges()
else:
nodes = population.size if population is not None else nodes
# check shape
if shape is None:
h = w = np.sqrt(float(nodes) / neuron_density)
shape = nngt.geometry.Shape.rectangle(h, w)
if graph_dr is None:
graph_dr = nngt.SpatialGraph(
name=name, nodes=nodes, directed=directed, shape=shape,
positions=positions, **kwargs)
else:
Graph.make_spatial(graph_dr, shape, positions=positions)
positions = np.array(graph_dr.get_positions().T, dtype=np.float32)
# set options (graph has already been made spatial)
_set_options(graph_dr, population, None, None)
# add edges
ia_edges = None
conversion_factor = conversion_magnitude(shape.unit, unit)
if unit != shape.unit:
positions = np.multiply(conversion_factor, positions, dtype=np.float32)
if nodes > 1:
ids = np.arange(0, nodes, dtype=np.uint)
ia_edges = _distance_rule(
ids, ids, density, edges, avg_deg, scale, rule, max_proba, shape,
positions, directed, multigraph, distance=distance, **kwargs)
attr = {'distance': distance}
# check for None if MPI
if ia_edges is not None:
graph_dr.new_edges(ia_edges, attributes=attr,
check_duplicates=False, check_self_loops=False,
check_existing=False)
graph_dr._graph_type = "{}_distance_rule".format(rule)
return graph_dr
# -------------------- #
# Polyvalent generator #
# -------------------- #
_di_generator = {
"all_to_all": all_to_all,
"circular": circular,
"distance_rule": distance_rule,
"erdos_renyi": erdos_renyi,
"fixed_degree": fixed_degree,
"from_degree_list": from_degree_list,
"gaussian_degree": gaussian_degree,
"newman_watts": newman_watts,
"price_scale_free": price_scale_free,
"random_scale_free": random_scale_free,
"sparse_clustered": sparse_clustered,
"watts_strogatz": watts_strogatz,
}
[docs]
def generate(di_instructions, **kwargs):
'''
Generate a :class:`~nngt.Graph` or one of its subclasses from a ``dict``
containing all the relevant informations.
Parameters
----------
di_instructions : ``dict``
Dictionary containing the instructions to generate the graph. It must
have at least ``"graph_type"`` in its keys, with a value among
``"distance_rule", "erdos_renyi", "fixed_degree", "newman_watts",
"price_scale_free", "random_scale_free"``. Depending on the type,
`di_instructions` should also contain at least all non-optional
arguments of the generator function.
See also
--------
:mod:`~nngt.generation`
'''
graph_type = di_instructions["graph_type"]
instructions = deepcopy(di_instructions)
del instructions["graph_type"]
instructions.update(kwargs)
return _di_generator[graph_type](**instructions)