Manipulate[
(*
The relevant parameters are;
n: number of nodes;
k: final average edges per node (graph average degree - can be decimal);
αvalue: caveman (α->0)/solaria (α->∞) propensity;pvalue: baseline probability for creating edges between "distant" nodes (the ones with no mutual friends);
Above parameters are set with controls in the external Manipulate. Changing one of above parameters triggers the recalculation of the graph;
Secondary derived parameters are;
M: total number of edges, where M=Round[((k n)/2),0];
iterations: total number of edges to be built after the substrate ring initial condition, where iterations=M-n=Round[((k n)/2),0]-n;
 *)
debug=False; (* with debug=True some partial data will be printed out during the main cycle to check the process;*)
(*debug=True;*) (* with debug=True some partial data will be printed out during the main cycle to check the process;*)
Clear@rmat;(*ramt: propensity matrix to establish a connection from node i to node j *)
Clear@mmat;(*"mutual friends" matrix. (Subscript[m, ij]) is the number of mutual friends between node i and node j. 
If i and j are directly connected than (Subscript[m, ij])=0 *)
Clear@matdyn; (* Indexed adjacency matrix of the graph during the mainloop. If matdyn[w][[i,j]]==0 then node i and node j are not linked at step w. If matdyn[w][[i,j]]==1 then node i and node j are linked at step w *)
Clear@newnode; (* node to be connected to the currently selected node (chosen in ransamloop) *)
If[k>n-1,k=n-1];
M=Round[((k n)/2)]; (* final number of edges in the graph *)
iterations=M-n; (* number of the main loop iterations needed to reach M edges after the initial graph (ring with k=2 and n edges*)
activenodes=Range[n]; (* list of the nodes that are not (yet) fully connected - updated during the main loop *)
fuconodes={}; (*list of the nodes that have become fully completed (that is linked to all the other nodes - updated during the main loop *)
onesmat=Table[1,{i,1,n},{j,1,n}]; (* a matrix filled with "1"s in every cell - useful for some matrix operation *)
ransamloop={};(* each node will be selected in random order, but once a node has been allowed to choose a new neighbour (newnode), it may not choose again until all other nodes have taken their turn once in turn. The choice will be a random choice weighted by the rmat propensity values. ransamloop is the sequence of nodes allowed to choose their new partners (newnode) and might be updated in each loop cycle whenever some node becomes completed after a new link is established *)
samfwdcleaned={}; (* forward part of ransamloop cleaned from fully completed nodes *)

(*construction of the node sequence to reach M edges, that is M-n iterations *)Table[ransamloop=Flatten@Append[ransamloop, RandomSample[Range[n]]],{s,1,Floor[(iterations/n)]+1}];
ransamloop=Take[ransamloop,iterations];
matdyn[0]=AdjacencyMatrix[CycleGraph[n]]; (* the starting graph is a simple ring graph *)
loopnodecomplete=False; (*boolean to track if the node chosen from ransamloop during the cycle has become a completed node *)
connodecomplete=False; (*boolean to track if the node linked to the node chosen from ransamloop during the cycle has become a completed node *)
regularizer[matr_]:=1-(matr+IdentityMatrix[Length[matr]]); (*This function builds a matrix that, if multiplied element-wise by an adjacency matrix or by the rmat matrix, sets the diagonal elements and the already connected nodes elements to 0 to exclude the possibility of "self connected nodes" and "already connected nodes" to be re-considered for new connections *)

(* here starts the main "Do" loop (from w=1 to iterations) *)
If[debug,Print[Column[{"======= INITIAL CONDITIONS: =======================",Row[{"ransamloop->",ransamloop," - length of ransamloop:"->Length[ransamloop]}]}]]];
(* begin of main loop *)
Do[
kprog=2+(2/n)(w-1);(* average graph degree at step w-1; unsure if to use the final (target) k instead, as Watts' book hints*)
progr=Round[N[(w/iterations)100],1];
loopnodecomplete=False;
connodecomplete=False;
todel1=0;todel2=0;samfwdcleaned={};toadd1={};toadd2={};
mmat=Table[Table[Total[matdyn[w-1][[j,All]]* matdyn[w-1][[i,All]]],{j,1,n}],{i,1,n}]*regularizer[matdyn[w-1]];
rmat=If[αvalue==0,Table[If[mmat[[i,j]]==0,pvalue,1],{i,1,n},{j,1,n}]*regularizer[matdyn[w-1]],(*else: αvalue<>0 *)((((MapThread[Min,{(mmat/kprog),onesmat},2]))^(αvalue))(1-pvalue)+pvalue)*regularizer[matdyn[w-1]]];
newnode=RandomChoice[rmat[[ransamloop[[w]],All]]->Range[n]];
matdyn[w]=ReplacePart[matdyn[w-1],{{newnode,ransamloop[[w]]},{ransamloop[[w]],newnode}}->1];(* in the following section there is the possible cleanup of fully completed nodes from ransamloop and the corresponding updates of fuconodes and activenodes *)
If[Total[matdyn[w][[ransamloop[[w]],All]]]==n-1,(* that would mean that node "ransamloop[[w]]" is complete *)
AppendTo[fuconodes,ransamloop[[w]]];loopnodecomplete=True(*,else: do nothing*)];If[Total[matdyn[w][[newnode,All]]]==n-1,(* that would mean that node "newnode" is complete *)
AppendTo[fuconodes,newnode];
connodecomplete=True(*,else: do nothing*)];.
If[loopnodecomplete,(*update activenodes and ransamloop *)
activenodes=DeleteCases[activenodes,ransamloop[[w]]];
todel1=Count[ransamloop[[w+1;;Length[ransamloop]]],ransamloop[[w]]];
samfwdcleaned=DeleteCases[ransamloop[[w+1;;Length[ransamloop]]],ransamloop[[w]]];
toadd1=RandomSample[activenodes,todel1];
ransamloop=Flatten@Join[ransamloop[[1;;w]],samfwdcleaned,toadd1](*,else: do nothing*)];
If[connodecomplete,(*update activenodes and ransamloop *)
activenodes=DeleteCases[activenodes,newnode];
todel2=Count[ransamloop[[w+1;;Length[ransamloop]]],newnode];
samfwdcleaned=DeleteCases[ransamloop[[w+1;;Length[ransamloop]]],newnode];
toadd2=RandomSample[activenodes,todel2];
ransamloop=Join[ransamloop[[1;;w]],samfwdcleaned,toadd2](*,else: do nothing*)];

(* loop print section in debug mode BEGIN ========================= *)
If[debug,Print[Column[{Print["==================================================="],Row[{"w = "<>ToString[w], "current ransamloop->"<>ToString@ransamloop[[w]],"length of ransamloop"->Length[ransamloop]},"; "],"kprog = "<>ToString[N[kprog]],Row[{"matdyn[w-1]->",MatrixForm[matdyn[w-1],TableHeadings->{Automatic,Automatic}],"mmat->",MatrixForm[mmat,TableHeadings->{Automatic,Automatic}],"  rmat->",MatrixForm[Round[rmat,0.01],TableHeadings->{Automatic,Automatic}](*,"  probmat->",*)(*MatrixForm[Round[probmat,0.001],TableHeadings->{Automatic,Automatic}]*)}],Row[{"Curr node, newnode->",{ransamloop[[w]],newnode}}],
Row[{"fuconodes->",fuconodes}],
Row[{"activenodes->",activenodes}],
Row[{"todel-> ","numtodel:"<>ToString[{todel1,todel2}]<>" ",{If[loopnodecomplete,ransamloop[[w]],""],If[connodecomplete,newnode,""]}}],
Row[{"toadd->",toadd1, toadd2}],
Row[{"samfwdcleaned->",samfwdcleaned}],
Row[{"forward sample->",ransamloop[[w+1;;iterations]]}]}]
]],
(*loop print section in debug mode END  ====================================== *)
{w,iterations}](* end of main loop *);Manipulate[Column[{Row[{"n="<>ToString[n],"(Subscript[k, f])="<>ToString[k],"α="<>ToString[αvalue],Row[{"p=",pvalue}]},", "],Row[{"MeanClusteringCoeff=="<>ToString[Round[MeanClusteringCoefficient[AdjacencyGraph[matdyn[t]]],0.01]],"L=MeanGraphDistance="<>ToString[Round[MeanGraphDistance[AdjacencyGraph[matdyn[t]]],0.01]]},", "],GraphPlot[matdyn[t],VertexLabeling->True,VertexCoordinateRules->Table[{s->{Cos[(π/2)-(s-1) ((2π)/(Length[matdyn[t]]))],Sin[(π/2)-(s-1) ((2π)/(Length[matdyn[t]]))]}},{s,1,n+1}][[All,1]],ImageSize->600]}],
{{t,iterations},0,iterations,1,Appearance->"Labeled"},TrackedSymbols:>{t}],
Row[{Framed[Column[{Row[{"Graph construction computation"},Alignment->Right,BaseStyle->{Small,Italic}],
Row[{Dynamic[ProgressIndicator[progr,{0,100},ImageSize->{100,7}]],Pane[Dynamic[ToString[progr]<>"%"],ImageSize->{30,10},Alignment->Center]}]}],FrameMargins->{{5,5},{5,5}},ContentPadding->False,FrameStyle->Red,Alignment->Right],
Control@{{αvalue,0.75,α},{0,0.5,0.75,1,1.5,2, 2.5, 3, 4, 5,8,15}},Control@{{pvalue,0.0001,p},{(10.^(-9)),0.0001,0.01,0.1,0.2,0.3,0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1}},Control@{{n,20},{10,15,20,25,30,40,50(* takes too long*)}},Control@{{k,Floor[(n/4)],(Subscript[k, f])},{Max[2,Floor[(n/10)]],Floor[(n/4)],Floor[(n/2)],Floor[((3n)/4)],n-1},ControlType->Setter}},"   "],TrackedSymbols:>{αvalue,pvalue,n,k}]