| """ |
| Generators for some directed graphs. |
| |
| gn_graph: growing network |
| gnc_graph: growing network with copying |
| gnr_graph: growing network with redirection |
| scale_free_graph: scale free directed graph |
| |
| """ |
| # Copyright (C) 2006-2009 by |
| # Aric Hagberg <hagberg@lanl.gov> |
| # Dan Schult <dschult@colgate.edu> |
| # Pieter Swart <swart@lanl.gov> |
| # All rights reserved. |
| # BSD license. |
| __author__ ="""Aric Hagberg (hagberg@lanl.gov)\nWillem Ligtenberg (W.P.A.Ligtenberg@tue.nl)""" |
| |
| __all__ = ['gn_graph', 'gnc_graph', 'gnr_graph','scale_free_graph'] |
| |
| import random |
| |
| import networkx as nx |
| from networkx.generators.classic import empty_graph |
| from networkx.utils import discrete_sequence |
| |
| |
| def gn_graph(n,kernel=None,create_using=None,seed=None): |
| """Return the GN digraph with n nodes. |
| |
| The GN (growing network) graph is built by adding nodes one at a time with |
| a link to one previously added node. The target node for the link is |
| chosen with probability based on degree. The default attachment kernel is |
| a linear function of degree. |
| |
| The graph is always a (directed) tree. |
| |
| Parameters |
| ---------- |
| n : int |
| The number of nodes for the generated graph. |
| kernel : function |
| The attachment kernel. |
| create_using : graph, optional (default DiGraph) |
| Return graph of this type. The instance will be cleared. |
| seed : hashable object, optional |
| The seed for the random number generator. |
| |
| Examples |
| -------- |
| >>> D=nx.gn_graph(10) # the GN graph |
| >>> G=D.to_undirected() # the undirected version |
| |
| To specify an attachment kernel use the kernel keyword |
| |
| >>> D=nx.gn_graph(10,kernel=lambda x:x**1.5) # A_k=k^1.5 |
| |
| References |
| ---------- |
| .. [1] P. L. Krapivsky and S. Redner, |
| Organization of Growing Random Networks, |
| Phys. Rev. E, 63, 066123, 2001. |
| """ |
| if create_using is None: |
| create_using = nx.DiGraph() |
| elif not create_using.is_directed(): |
| raise nx.NetworkXError("Directed Graph required in create_using") |
| |
| if kernel is None: |
| kernel = lambda x: x |
| |
| if seed is not None: |
| random.seed(seed) |
| |
| G=empty_graph(1,create_using) |
| G.name="gn_graph(%s)"%(n) |
| |
| if n==1: |
| return G |
| |
| G.add_edge(1,0) # get started |
| ds=[1,1] # degree sequence |
| |
| for source in range(2,n): |
| # compute distribution from kernel and degree |
| dist=[kernel(d) for d in ds] |
| # choose target from discrete distribution |
| target=discrete_sequence(1,distribution=dist)[0] |
| G.add_edge(source,target) |
| ds.append(1) # the source has only one link (degree one) |
| ds[target]+=1 # add one to the target link degree |
| return G |
| |
| |
| def gnr_graph(n,p,create_using=None,seed=None): |
| """Return the GNR digraph with n nodes and redirection probability p. |
| |
| The GNR (growing network with redirection) graph is built by adding nodes |
| one at a time with a link to one previously added node. The previous |
| target node is chosen uniformly at random. With probabiliy p the link is |
| instead "redirected" to the successor node of the target. The graph is |
| always a (directed) tree. |
| |
| Parameters |
| ---------- |
| n : int |
| The number of nodes for the generated graph. |
| p : float |
| The redirection probability. |
| create_using : graph, optional (default DiGraph) |
| Return graph of this type. The instance will be cleared. |
| seed : hashable object, optional |
| The seed for the random number generator. |
| |
| Examples |
| -------- |
| >>> D=nx.gnr_graph(10,0.5) # the GNR graph |
| >>> G=D.to_undirected() # the undirected version |
| |
| References |
| ---------- |
| .. [1] P. L. Krapivsky and S. Redner, |
| Organization of Growing Random Networks, |
| Phys. Rev. E, 63, 066123, 2001. |
| """ |
| if create_using is None: |
| create_using = nx.DiGraph() |
| elif not create_using.is_directed(): |
| raise nx.NetworkXError("Directed Graph required in create_using") |
| |
| if not seed is None: |
| random.seed(seed) |
| |
| G=empty_graph(1,create_using) |
| G.name="gnr_graph(%s,%s)"%(n,p) |
| |
| if n==1: |
| return G |
| |
| for source in range(1,n): |
| target=random.randrange(0,source) |
| if random.random() < p and target !=0: |
| target=G.successors(target)[0] |
| G.add_edge(source,target) |
| |
| return G |
| |
| |
| def gnc_graph(n,create_using=None,seed=None): |
| """Return the GNC digraph with n nodes. |
| |
| The GNC (growing network with copying) graph is built by adding nodes one |
| at a time with a links to one previously added node (chosen uniformly at |
| random) and to all of that node's successors. |
| |
| Parameters |
| ---------- |
| n : int |
| The number of nodes for the generated graph. |
| create_using : graph, optional (default DiGraph) |
| Return graph of this type. The instance will be cleared. |
| seed : hashable object, optional |
| The seed for the random number generator. |
| |
| References |
| ---------- |
| .. [1] P. L. Krapivsky and S. Redner, |
| Network Growth by Copying, |
| Phys. Rev. E, 71, 036118, 2005k.}, |
| """ |
| if create_using is None: |
| create_using = nx.DiGraph() |
| elif not create_using.is_directed(): |
| raise nx.NetworkXError("Directed Graph required in create_using") |
| |
| if not seed is None: |
| random.seed(seed) |
| |
| G=empty_graph(1,create_using) |
| G.name="gnc_graph(%s)"%(n) |
| |
| if n==1: |
| return G |
| |
| for source in range(1,n): |
| target=random.randrange(0,source) |
| for succ in G.successors(target): |
| G.add_edge(source,succ) |
| G.add_edge(source,target) |
| |
| return G |
| |
| |
| def scale_free_graph(n, |
| alpha=0.41, |
| beta=0.54, |
| gamma=0.05, |
| delta_in=0.2, |
| delta_out=0, |
| create_using=None, |
| seed=None): |
| """Return a scale free directed graph. |
| |
| Parameters |
| ---------- |
| n : integer |
| Number of nodes in graph |
| alpha : float |
| Probability for adding a new node connected to an existing node |
| chosen randomly according to the in-degree distribution. |
| beta : float |
| Probability for adding an edge between two existing nodes. |
| One existing node is chosen randomly according the in-degree |
| distribution and the other chosen randomly according to the out-degree |
| distribution. |
| gamma : float |
| Probability for adding a new node conecgted to an existing node |
| chosen randomly according to the out-degree distribution. |
| delta_in : float |
| Bias for choosing ndoes from in-degree distribution. |
| delta_out : float |
| Bias for choosing ndoes from out-degree distribution. |
| create_using : graph, optional (default MultiDiGraph) |
| Use this graph instance to start the process (default=3-cycle). |
| seed : integer, optional |
| Seed for random number generator |
| |
| Examples |
| -------- |
| >>> G=nx.scale_free_graph(100) |
| |
| Notes |
| ----- |
| The sum of alpha, beta, and gamma must be 1. |
| |
| References |
| ---------- |
| .. [1] B. Bollob{\'a}s, C. Borgs, J. Chayes, and O. Riordan, |
| Directed scale-free graphs, |
| Proceedings of the fourteenth annual ACM-SIAM symposium on |
| Discrete algorithms, 132--139, 2003. |
| """ |
| |
| def _choose_node(G,distribution,delta): |
| cumsum=0.0 |
| # normalization |
| psum=float(sum(distribution.values()))+float(delta)*len(distribution) |
| r=random.random() |
| for i in range(0,len(distribution)): |
| cumsum+=(distribution[i]+delta)/psum |
| if r < cumsum: |
| break |
| return i |
| |
| if create_using is None: |
| # start with 3-cycle |
| G = nx.MultiDiGraph() |
| G.add_edges_from([(0,1),(1,2),(2,0)]) |
| else: |
| # keep existing graph structure? |
| G = create_using |
| if not (G.is_directed() and G.is_multigraph()): |
| raise nx.NetworkXError(\ |
| "MultiDiGraph required in create_using") |
| |
| if alpha <= 0: |
| raise ValueError('alpha must be >= 0.') |
| if beta <= 0: |
| raise ValueError('beta must be >= 0.') |
| if gamma <= 0: |
| raise ValueError('beta must be >= 0.') |
| |
| if alpha+beta+gamma !=1.0: |
| raise ValueError('alpha+beta+gamma must equal 1.') |
| |
| G.name="directed_scale_free_graph(%s,alpha=%s,beta=%s,gamma=%s,delta_in=%s,delta_out=%s)"%(n,alpha,beta,gamma,delta_in,delta_out) |
| |
| # seed random number generated (uses None as default) |
| random.seed(seed) |
| |
| while len(G)<n: |
| r = random.random() |
| # random choice in alpha,beta,gamma ranges |
| if r<alpha: |
| # alpha |
| # add new node v |
| v = len(G) |
| # choose w according to in-degree and delta_in |
| w = _choose_node(G, G.in_degree(),delta_in) |
| elif r < alpha+beta: |
| # beta |
| # choose v according to out-degree and delta_out |
| v = _choose_node(G, G.out_degree(),delta_out) |
| # choose w according to in-degree and delta_in |
| w = _choose_node(G, G.in_degree(),delta_in) |
| else: |
| # gamma |
| # choose v according to out-degree and delta_out |
| v = _choose_node(G, G.out_degree(),delta_out) |
| # add new node w |
| w = len(G) |
| G.add_edge(v,w) |
| |
| return G |
| |