Description of selective

Home > matgraph > @graph > selective.m

selective

PURPOSE

selective(g,n,n0,d) --- selective attachment random graph

SYNOPSIS

function selective(g,n,n0,d)

DESCRIPTION

 selective(g,n,n0,d) --- selective attachment random graph
 overwrite g with a random graph with a degree-d selective attachment
 graph on n vertices starting with n0 isolated vertices.

 That is, we begin with n0 isolated vertices. We then add vertices one at
 a time. Each new vertex has d edges to previous vertices in the graph.
 These d edges are drawn at random (without replacement) with the
 probability of joining to a previous vertex u proportion to d(u)+1. The
 process ends when we have n vertices.

CROSS-REFERENCE INFORMATION

This function calls:

• add add --- add edge(s) to the graph
• clear_edges clear_edges(g) --- delete all edges of g
• deg deg: degree of a vertex or degree sequence
• resize resize(g,n) --- change the number of vertices in g to n
• rmxy rmxy(g) --- erase g's embedding

This function is called by:

SUBFUNCTIONS

• function c = weighted_choice(w)

SOURCE CODE

0001 function selective(g,n,n0,d)
0002 % selective(g,n,n0,d) --- selective attachment random graph
0003 % overwrite g with a random graph with a degree-d selective attachment
0004 % graph on n vertices starting with n0 isolated vertices.
0005 %
0006 % That is, we begin with n0 isolated vertices. We then add vertices one at
0007 % a time. Each new vertex has d edges to previous vertices in the graph.
0008 % These d edges are drawn at random (without replacement) with the
0009 % probability of joining to a previous vertex u proportion to d(u)+1. The
0010 % process ends when we have n vertices.
0011 
0012 clear_edges(g);
0013 resize(g,n);
0014 rmxy(g);
0015 
0016 for v=n0+1:n
0017     wt = deg(g);
0018     wt = wt + [ones(1,v-1),zeros(1,n-v+1)];
0019     for k=1:d
0020         u = weighted_choice( wt);
0021         add(g,v,u);
0022         wt(u) = 0;  % to avoid repetition
0023     end
0024 end
0025 
0026 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
0027 
0028 
0029 function c = weighted_choice(w)
0030 % weighted_choice(w) --- choose an integer at random according to weights.
0031 % w is a list of nonnegative real values
0032 % return an integer c between 1 and length(w) with probability proportional
0033 % to w(c).
0034 
0035 n = length(w);
0036 p = cumsum(w);
0037 p = p/p(n);
0038 c = sum(p<rand)+1;

---

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003