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: This function is called by:

SUBFUNCTIONS ^

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