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.duplication

# duplication.py - functions for generating graphs by duplicating nodes
#
# Copyright 2016-2017 NetworkX developers.
# Copyright (C) 2004-2017 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
#
# This file is part of NetworkX.
#
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
# information.
"""Functions for generating graphs based on the "duplication" method.

These graph generators start with a small initial graph then duplicate
nodes and (partially) duplicate their edges. These functions are
generally inspired by biological networks.

"""
import random

import networkx as nx
from networkx.exception import NetworkXError

__all__ = ['partial_duplication_graph', 'duplication_divergence_graph']


[docs]def partial_duplication_graph(N, n, p, q, seed=None): """Return a random graph using the partial duplication model. Parameters ---------- N : int The total number of nodes in the final graph. n : int The number of nodes in the initial clique. p : float The probability of joining each neighbor of a node to the duplicate node. Must be a number in the between zero and one, inclusive. q : float The probability of joining the source node to the duplicate node. Must be a number in the between zero and one, inclusive. seed : int, optional Seed for random number generator (default=None). Notes ----- A graph of nodes is grown by creating a fully connected graph of size `n`. The following procedure is then repeated until a total of `N` nodes have been reached. 1. A random node, *u*, is picked and a new node, *v*, is created. 2. For each neighbor of *u* an edge from the neighbor to *v* is created with probability `p`. 3. An edge from *u* to *v* is created with probability `q`. This algorithm appears in [1]. This implementation allows the possibility of generating disconnected graphs. References ---------- .. [1] Knudsen Michael, and Carsten Wiuf. "A Markov chain approach to randomly grown graphs." Journal of Applied Mathematics 2008. <https://dx.doi.org/10.1155/2008/190836> """ if p < 0 or p > 1 or q < 0 or q > 1: msg = "partial duplication graph must have 0 <= p, q <= 1." raise NetworkXError(msg) if n > N: raise NetworkXError("partial duplication graph must have n <= N.") if seed is not None: random.seed(seed) G = nx.complete_graph(n) for new_node in range(n, N): # Add a new vertex, v, to the graph. G.add_node(new_node) # Pick a random vertex, u, already in the graph. src_node = random.randint(0, new_node) # Join v and u with probability q. if random.random() < q: G.add_edge(new_node, src_node) # For each neighbor of u... for neighbor_node in list(nx.all_neighbors(G, src_node)): # Add the neighbor to v with probability p. if random.random() < p: G.add_edge(new_node, neighbor_node) return G
[docs]def duplication_divergence_graph(n, p, seed=None): """Returns an undirected graph using the duplication-divergence model. A graph of `n` nodes is created by duplicating the initial nodes and retaining edges incident to the original nodes with a retention probability `p`. Parameters ---------- n : int The desired number of nodes in the graph. p : float The probability for retaining the edge of the replicated node. seed : int, optional A seed for the random number generator of :mod:`random` (default=None). Returns ------- G : Graph Raises ------ NetworkXError If `p` is not a valid probability. If `n` is less than 2. Notes ----- This algorithm appears in [1]. This implementation disallows the possibility of generating disconnected graphs. References ---------- .. [1] I. Ispolatov, P. L. Krapivsky, A. Yuryev, "Duplication-divergence model of protein interaction network", Phys. Rev. E, 71, 061911, 2005. """ if p > 1 or p < 0: msg = "NetworkXError p={0} is not in [0,1].".format(p) raise nx.NetworkXError(msg) if n < 2: msg = 'n must be greater than or equal to 2' raise nx.NetworkXError(msg) if seed is not None: random.seed(seed) G = nx.Graph() # Initialize the graph with two connected nodes. G.add_edge(0, 1) i = 2 while i < n: # Choose a random node from current graph to duplicate. random_node = random.choice(list(G)) # Make the replica. G.add_node(i) # flag indicates whether at least one edge is connected on the replica. flag = False for nbr in G.neighbors(random_node): if random.random() < p: # Link retention step. G.add_edge(i, nbr) flag = True if not flag: # Delete replica if no edges retained. G.remove_node(i) else: # Successful duplication. i += 1 return G