Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / generators / duplication.py @ 5cef0f13

History | View | Annotate | Download (5.21 KB)

1
# duplication.py - functions for generating graphs by duplicating nodes
2
#
3
# Copyright 2016-2019 NetworkX developers.
4
# Copyright (C) 2004-2019 by
5
# Aric Hagberg <hagberg@lanl.gov>
6
# Dan Schult <dschult@colgate.edu>
7
# Pieter Swart <swart@lanl.gov>
8
#
9
# This file is part of NetworkX.
10
#
11
# NetworkX is distributed under a BSD license; see LICENSE.txt for more
12
# information.
13
"""Functions for generating graphs based on the "duplication" method.
14

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

19
"""
20
import networkx as nx
21
from networkx.utils import py_random_state
22
from networkx.exception import NetworkXError
23

    
24
__all__ = ['partial_duplication_graph', 'duplication_divergence_graph']
25

    
26

    
27
@py_random_state(4)
28
def partial_duplication_graph(N, n, p, q, seed=None):
29
    """Returns a random graph using the partial duplication model.
30

31
    Parameters
32
    ----------
33
    N : int
34
        The total number of nodes in the final graph.
35

36
    n : int
37
        The number of nodes in the initial clique.
38

39
    p : float
40
        The probability of joining each neighbor of a node to the
41
        duplicate node. Must be a number in the between zero and one,
42
        inclusive.
43

44
    q : float
45
        The probability of joining the source node to the duplicate
46
        node. Must be a number in the between zero and one, inclusive.
47

48
    seed : integer, random_state, or None (default)
49
        Indicator of random number generation state.
50
        See :ref:`Randomness<randomness>`.
51

52
    Notes
53
    -----
54
    A graph of nodes is grown by creating a fully connected graph
55
    of size `n`. The following procedure is then repeated until
56
    a total of `N` nodes have been reached.
57

58
    1. A random node, *u*, is picked and a new node, *v*, is created.
59
    2. For each neighbor of *u* an edge from the neighbor to *v* is created
60
       with probability `p`.
61
    3. An edge from *u* to *v* is created with probability `q`.
62

63
    This algorithm appears in [1].
64

65
    This implementation allows the possibility of generating
66
    disconnected graphs.
67

68
    References
69
    ----------
70
    .. [1] Knudsen Michael, and Carsten Wiuf. "A Markov chain approach to
71
           randomly grown graphs." Journal of Applied Mathematics 2008.
72
           <https://doi.org/10.1155/2008/190836>
73

74
    """
75
    if p < 0 or p > 1 or q < 0 or q > 1:
76
        msg = "partial duplication graph must have 0 <= p, q <= 1."
77
        raise NetworkXError(msg)
78
    if n > N:
79
        raise NetworkXError("partial duplication graph must have n <= N.")
80

    
81
    G = nx.complete_graph(n)
82
    for new_node in range(n, N):
83
        # Add a new vertex, v, to the graph.
84
        G.add_node(new_node)
85

    
86
        # Pick a random vertex, u, already in the graph.
87
        src_node = seed.randint(0, new_node)
88

    
89
        # Join v and u with probability q.
90
        if seed.random() < q:
91
            G.add_edge(new_node, src_node)
92

    
93
        # For each neighbor of u...
94
        for neighbor_node in list(nx.all_neighbors(G, src_node)):
95
            # Add the neighbor to v with probability p.
96
            if seed.random() < p:
97
                G.add_edge(new_node, neighbor_node)
98
    return G
99

    
100

    
101
@py_random_state(2)
102
def duplication_divergence_graph(n, p, seed=None):
103
    """Returns an undirected graph using the duplication-divergence model.
104

105
    A graph of `n` nodes is created by duplicating the initial nodes
106
    and retaining edges incident to the original nodes with a retention
107
    probability `p`.
108

109
    Parameters
110
    ----------
111
    n : int
112
        The desired number of nodes in the graph.
113
    p : float
114
        The probability for retaining the edge of the replicated node.
115
    seed : integer, random_state, or None (default)
116
        Indicator of random number generation state.
117
        See :ref:`Randomness<randomness>`.
118

119
    Returns
120
    -------
121
    G : Graph
122

123
    Raises
124
    ------
125
    NetworkXError
126
        If `p` is not a valid probability.
127
        If `n` is less than 2.
128

129
    Notes
130
    -----
131
    This algorithm appears in [1].
132

133
    This implementation disallows the possibility of generating
134
    disconnected graphs.
135

136
    References
137
    ----------
138
    .. [1] I. Ispolatov, P. L. Krapivsky, A. Yuryev,
139
       "Duplication-divergence model of protein interaction network",
140
       Phys. Rev. E, 71, 061911, 2005.
141

142
    """
143
    if p > 1 or p < 0:
144
        msg = "NetworkXError p={0} is not in [0,1].".format(p)
145
        raise nx.NetworkXError(msg)
146
    if n < 2:
147
        msg = 'n must be greater than or equal to 2'
148
        raise nx.NetworkXError(msg)
149

    
150
    G = nx.Graph()
151

    
152
    # Initialize the graph with two connected nodes.
153
    G.add_edge(0, 1)
154
    i = 2
155
    while i < n:
156
        # Choose a random node from current graph to duplicate.
157
        random_node = seed.choice(list(G))
158
        # Make the replica.
159
        G.add_node(i)
160
        # flag indicates whether at least one edge is connected on the replica.
161
        flag = False
162
        for nbr in G.neighbors(random_node):
163
            if seed.random() < p:
164
                # Link retention step.
165
                G.add_edge(i, nbr)
166
                flag = True
167
        if not flag:
168
            # Delete replica if no edges retained.
169
            G.remove_node(i)
170
        else:
171
            # Successful duplication.
172
            i += 1
173
    return G