# -*- coding: cp936 -*-
import random
import networkx as nx
from networkx.generators.classic import empty_graph
def powerlaw_cluster_graph(n, m, p, seed=None):
"""Holme and Kim algorithm for growing graphs with powerlaw
degree distribution and approximate average clustering.
Parameters
----------
n : int
the number of nodes
m : int
the number of random edges to add for each new node
p : float,
Probability of adding a triangle after adding a random edge
seed : int, optional
Seed for random number generator (default=None).
Notes
-----
The average clustering has a hard time getting above a certain
cutoff that depends on ``m``. This cutoff is often quite low. The
transitivity (fraction of triangles to possible triangles) seems to
decrease with network size.
It is essentially the Barabási–Albert (BA) growth model with an
extra step that each random edge is followed by a chance of
making an edge to one of its neighbors too (and thus a triangle).
This algorithm improves on BA in the sense that it enables a
higher average clustering to be attained if desired.
It seems possible to have a disconnected graph with this algorithm
since the initial ``m`` nodes may not be all linked to a new node
on the first iteration like the BA model.
Raises
------
NetworkXError
If ``m`` does not satisfy ``1 <= m <= n`` or ``p`` does not
satisfy ``0 <= p <= 1``.
References
----------
.. [1] P. Holme and B. J. Kim,
"Growing scale-free networks with tunable clustering",
Phys. Rev. E, 65, 026107, 2002.
"""
if m < 1 or n < m:
raise nx.NetworkXError(\
"NetworkXError must have m>1 and m
if p > 1 or p < 0:
raise nx.NetworkXError(\
"NetworkXError p must be in [0,1], p=%f"%(p))
if seed is not None:
random.seed(seed)
G=empty_graph(m) # add m initial nodes (m0 in barabasi-speak)
G.name="Powerlaw-Cluster Graph"
repeated_nodes=G.nodes() # list of existing nodes to sample from
# with nodes repeated once for each adjacent edge
source=m # next node is m
while source
possible_targets = _random_subset(repeated_nodes,m)
# do one preferential attachment for new node
target=possible_targets.pop()
G.add_edge(source,target)
repeated_nodes.append(target) # add one node to list for each new link
count=1
while count
if random.random()
neighborhood=[nbr for nbr in G.neighbors(target) \
if not G.has_edge(source,nbr) \
and not nbr==source]
if neighborhood: # if there is a neighbor without a link
nbr=random.choice(neighborhood)
G.add_edge(source,nbr) # add triangle
repeated_nodes.append(nbr)
count=count+1
continue # go to top of while loop
# else do preferential attachment step if above fails
target=possible_targets.pop()
G.add_edge(source,target)
repeated_nodes.append(target)
count=count+1
repeated_nodes.extend([source]*m) # add source node to list m times
source += 1
return G
def _random_subset(seq,m):
""" Return m unique elements from seq.
This differs from random.sample which can return repeated
elements if seq holds repeated elements.
:param seq:
:param m:
:return:
"""
targets=set()
while len(targets)
x=random.choice(seq)
targets.add(x)
return targets
if __name__=="__main__":
n=input(" the number of nodes:")
m=input("the number of random edges to add for each new node:")
p=input("Probability of adding a triangle after adding a random edge:")
g=powerlaw_cluster_graph(n, m, p, seed=None)
node = list(g.nodes())
edge = list(g.edges())
# with open('node.pickle', 'wb') as f:
# pickle.dump(node, f)
#with open('edge.pickle', 'wb') as f:
# pickle.dump(edge, f)
#print(node)
#print(edge)
#edge = list(edge)
fil = open('edge.txt', 'w')
for i in edge:
fil.write('{} {}\n'.format(*i))
fil.close()