Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Source code for networkx.generators.joint_degree_seq

#    Copyright (C) 2016-2019 by
#    Minas Gjoka
#
# Author:  Minas Gjoka (minas.gjoka@gmail.com)
"""Generate graphs with a given joint degree """
from __future__ import division

import networkx as nx
from networkx.utils import py_random_state

__all__ = ['is_valid_joint_degree',
'joint_degree_graph']

[docs]def is_valid_joint_degree(joint_degrees):
""" Checks whether the given joint degree dictionary is realizable
as a simple graph.

A *joint degree dictionary* is a dictionary of dictionaries, in
which entry joint_degrees[k][l] is an integer representing the
number of edges joining nodes of degree *k* with nodes of degree
*l*. Such a dictionary is realizable as a simple graph if and only
if the following conditions are satisfied.

- each entry must be an integer,
- the total number of nodes of degree *k*, computed by
sum(joint_degrees[k].values()) / k, must be an integer,
- the total number of edges joining nodes of degree *k* with
nodes of degree *l* cannot exceed the total number of possible edges,
- each diagonal entry joint_degrees[k][k] must be even (this is
a convention assumed by the :func:joint_degree_graph function).

Parameters
----------
joint_degrees :  dictionary of dictionary of integers
A joint degree dictionary in which entry joint_degrees[k][l]
is the number of edges joining nodes of degree *k* with nodes of
degree *l*.

Returns
-------
bool
Whether the given joint degree dictionary is realizable as a
simple graph.

References
----------
.. [1] M. Gjoka, M. Kurant, A. Markopoulou, "2.5K Graphs: from Sampling
to Generation", IEEE Infocom, 2013.
.. [2] I. Stanton, A. Pinar, "Constructing and sampling graphs with a
prescribed joint degree distribution", Journal of Experimental
Algorithmics, 2012.
"""

degree_count = {}
for k in joint_degrees:
if k > 0:
k_size = sum(joint_degrees[k].values()) / k
if not k_size.is_integer():
return False
degree_count[k] = k_size

for k in joint_degrees:
for l in joint_degrees[k]:
if not float(joint_degrees[k][l]).is_integer():
return False

if (k != l) and (joint_degrees[k][l] >
degree_count[k] * degree_count[l]):
return False
elif k == l:
if joint_degrees[k][k] > degree_count[k] * (degree_count[k] - 1):
return False
if joint_degrees[k][k] % 2 != 0:
return False

# if all above conditions have been satisfied then the input
# joint degree is realizable as a simple graph.
return True

def _neighbor_switch(G, w, unsat, h_node_residual, avoid_node_id=None):
""" Releases one free stub for saturated node w, while preserving
joint degree in graph G.

Parameters
----------
G : NetworkX graph
Graph in which the neighbor switch will take place.
w : integer
Node id for which we will execute this neighbor switch.
unsat : set of integers
Set of unsaturated node ids that have the same degree as w.
h_node_residual: dictionary of integers
Keeps track of the remaining stubs  for a given node.
avoid_node_id: integer
Node id to avoid when selecting w_prime.

Notes
-----
First, it selects *w_prime*, an  unsaturated node that has the same degree
as w. Second, it selects *switch_node*, a neighbor node of w that
is not  connected to *w_prime*. Then it executes an edge swap i.e. removes
(w,*switch_node*) and adds (*w_prime*,*switch_node*). Gjoka et. al. [1]
prove that such an edge swap is always possible.

References
----------
.. [1] M. Gjoka, B. Tillman, A. Markopoulou, "Construction of Simple
Graphs with a Target Joint Degree Matrix and Beyond", IEEE Infocom, '15
"""

if (avoid_node_id is None) or (h_node_residual[avoid_node_id] > 1):
# select unsatured node w_prime that has the same degree as w
w_prime = next(iter(unsat))
else:
# assume that the node pair (v,w) has been selected for connection. if
# - neighbor_switch is called for node w,
# - nodes v and w have the same degree,
# - node v=avoid_node_id has only one stub left,
# then prevent v=avoid_node_id from being selected as w_prime.

iter_var = iter(unsat)
while True:
w_prime = next(iter_var)
if w_prime != avoid_node_id:
break

# select switch_node, a neighbor of w, that is not connected to w_prime
w_prime_neighbs = G[w_prime]  # slightly faster declaring this variable
for v in G[w]:
if (v not in w_prime_neighbs) and (v != w_prime):
switch_node = v
break

# remove edge (w,switch_node), add edge (w_prime,switch_node) and update
# data structures
G.remove_edge(w, switch_node)
h_node_residual[w] += 1
h_node_residual[w_prime] -= 1
if h_node_residual[w_prime] == 0:
unsat.remove(w_prime)

[docs]@py_random_state(1)
def joint_degree_graph(joint_degrees, seed=None):
""" Generates a random simple graph with the given joint degree dictionary.

Parameters
----------
joint_degrees :  dictionary of dictionary of integers
A joint degree dictionary in which entry joint_degrees[k][l] is the
number of edges joining nodes of degree *k* with nodes of degree *l*.
seed : integer, random_state, or None (default)
Indicator of random number generation state.
See :ref:Randomness<randomness>.

Returns
-------
G : Graph
A graph with the specified joint degree dictionary.

Raises
------
NetworkXError
If *joint_degrees* dictionary is not realizable.

Notes
-----
In each iteration of the "while loop" the algorithm picks two disconnected
nodes *v* and *w*, of degree *k* and *l* correspondingly,  for which
joint_degrees[k][l] has not reached its target yet. It then adds
edge (*v*, *w*) and increases the number of edges in graph G by one.

The intelligence of the algorithm lies in the fact that  it is always
possible to add an edge between such disconnected nodes *v* and *w*,
even if one or both nodes do not have free stubs. That is made possible by
executing a "neighbor switch", an edge rewiring move that releases
a free stub while keeping the joint degree of G the same.

The algorithm continues for E (number of edges) iterations of
the "while loop", at the which point all entries of the given
joint_degrees[k][l] have reached their target values and the
construction is complete.

References
----------
..  [1] M. Gjoka, B. Tillman, A. Markopoulou, "Construction of Simple
Graphs with a Target Joint Degree Matrix and Beyond", IEEE Infocom, '15.

Examples
--------
>>> import networkx as nx
>>> joint_degrees = {1: {4: 1},
...                      2: {2: 2, 3: 2, 4: 2},
...                      3: {2: 2, 4: 1},
...                      4: {1: 1, 2: 2, 3: 1}}
>>> G=nx.joint_degree_graph(joint_degrees)
>>>
"""

if not is_valid_joint_degree(joint_degrees):
msg = 'Input joint degree dict not realizable as a simple graph'
raise nx.NetworkXError(msg)

# compute degree count from joint_degrees
degree_count = {k: sum(l.values()) // k for k, l in joint_degrees.items() if k > 0}

N = sum(degree_count.values())
G = nx.empty_graph(N)

# for a given degree group, keep the list of all node ids
h_degree_nodelist = {}

# for a given node, keep track of the remaining stubs
h_node_residual = {}

# populate h_degree_nodelist and h_node_residual
nodeid = 0
for degree, num_nodes in degree_count.items():
h_degree_nodelist[degree] = range(nodeid, nodeid + num_nodes)
for v in h_degree_nodelist[degree]:
h_node_residual[v] = degree
nodeid += int(num_nodes)

# iterate over every degree pair (k,l) and add the number of edges given
# for each pair
for k in joint_degrees:
for l in joint_degrees[k]:

# n_edges_add is the number of edges to add for the
# degree pair (k,l)

if (n_edges_add > 0) and (k >= l):

# number of nodes with degree k and l
k_size = degree_count[k]
l_size = degree_count[l]

# k_nodes and l_nodes consist of all nodes of degree k and l
k_nodes = h_degree_nodelist[k]
l_nodes = h_degree_nodelist[l]

# k_unsat and l_unsat consist of nodes of degree k and l that
# are unsaturated i.e. nodes that have at least 1 available stub
k_unsat = set(v for v in k_nodes if h_node_residual[v] > 0)

if k != l:
l_unsat = set(w for w in l_nodes if h_node_residual[w] > 0)
else:
l_unsat = k_unsat
n_edges_add = joint_degrees[k][l] // 2

while n_edges_add > 0:

# randomly pick nodes v and w that have degrees k and l
v = k_nodes[seed.randrange(k_size)]
w = l_nodes[seed.randrange(l_size)]

# if nodes v and w are disconnected then attempt to connect
if not G.has_edge(v, w) and (v != w):

# if node v has no free stubs then do neighbor switch
if h_node_residual[v] == 0:
_neighbor_switch(G, v, k_unsat, h_node_residual)

# if node w has no free stubs then do neighbor switch
if h_node_residual[w] == 0:
if k != l:
_neighbor_switch(G, w, l_unsat, h_node_residual)
else:
_neighbor_switch(G, w, l_unsat, h_node_residual,
avoid_node_id=v)

# add edge (v, w) and update data structures