"""
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 math
import random
import networkx as nx
from networkx.generators.classic import empty_graph,cycle_graph
from networkx import MultiDiGraph
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
|